Bogglers Solutions

By Scott Kim|Sunday, September 01, 2002




Divided Alphabet








Divided Words

1. ABC IDEAS — BASE ACID — Chemistry
2. FOLDOUTS — LOUD SOFT — Acoustics
3. AIR TOWEL — OIL WATER — Cooking
4. FLUTE EARS — TRUE FALSE — Logic
5. USUAL DRAIN — RADIUS ULNA — Anatomy
6. BLEAK WITCH — BLACK WHITE — Photography
7. DOOR SEARCH — ORDER CHAOS — Dynamic Systems
8. NIFTY IONIZER — ZERO INFINITY — Mathematics
9. PAINT ALL MAN — PLANT ANIMAL — Biology
10. CAVALIER WEPT — WAVE PARTICLE — Physics of Light



Divided Roads

1. 2.


3. If every road is colored either red or blue, then of the five roads that start from a single town, at least three must be the same color— say, red. Then the three towns at the other ends of these three red roads have one red road. If you color the remaining roads red, you create a red triangle. If you color them blue, you create a blue triangle. So a triangle-free coloring is impossible.

This is a basic problem in Ramsey theory (named for mathematician Frank P. Ramsey) and is commonly known as the party problem. In any group of six people, there will always be either three people who all know each other, or three people who are mutual strangers. In the party problem, the six "cities" in the road diagram represent people. Red lines connect pairs of people who know each other, and blue lines connect pairs who don't. Ramsey theory was explored by the fascinating and singular mathematician Paul Erdös (pronounced "air-dish"), who is profiled in the documentary N Is a Number by George Csicsery. The film will air on PBS this month and is also available on video.

4. As shown in the diagram at right, you can color all but one road red or blue without forming any monochromatic triangles.


5. You can color as many as nine of the 15 roads without creating a triangle, as shown in the diagram below right.



6. Use the same reasoning as you used in problem 3, but apply it twice: From each town, there are 16 roads leading to 16 other towns. At least six of these roads must be the same color. Suppose they are black. Then the six towns at the ends of the six black roads each have a black road. The remaining roads that connect all these towns must be red or blue. But we know from problem 3 that when the roads between six towns are either red or blue, there must one all-red or all-blue triangle. In 1968 Kalbfleisch and Stanton showed that it is possible to connect 16 towns with roads of three colors without creating a monochromatic triangle; 16 is the maximum. Now here's an unsolved problem: What is the maximum number of cities that can be built connected by roads of four different colors without creating a single monochromatic triangle? So far, the answer has been narrowed to a range between 51 and 62.





Want to go back to the puzzle?

Got new solutions for the puzzle? Want to see other people's solutions? Talk to the puzzle master in his discussion forum at www.scottkim.com.


Comment on this article
ADVERTISEMENT

Discover's Newsletter

Sign up to get the latest science news delivered weekly right to your inbox!

ADVERTISEMENT
ADVERTISEMENT
Collapse bottom bar
DSC-JanFeb15
+

Log in to your account

X
Email address:
Password:
Remember me
Forgot your password?
No problem. Click here to have it emailed to you.

Not registered yet?

Register now for FREE. It takes only a few seconds to complete. Register now »