All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Ten Colors (Posted on 2004-03-05)
Albinia consists of two states: Alexton and Brighton. Each road in Albinia connects two towns from Alexton and Brighton respectively. It is known that no town is connected with more than 10 others.

Prove that it is possible to color all roads in Albinia, using 10 colors, in such a way that no two adjacent roads would be the same color (we call two roads adjacent if they leave the same town).

 No Solution Yet Submitted by Aaron Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Harder than it looks at first sight. | Comment 1 of 6

The proposition to be proved seems counter-intuitive.  Suppose there are a subset of 10 towns on each side, and each is connected to each of the others in these subsets, so there are ten roads of each of the 10 allowed colors.

Now remove two roads of the same color, say color 10.  Then add another town on one side of the divide and connect it to the two towns on the other side which had a road removed.  The only color available at either of these towns is color 10, but the two new roads can't both be color 10.  In order for the proposition to be true, we must prove it's possible to reassign the whole remainder of the network so as to free up different colors at these two towns.

 Posted by Charlie on 2004-03-05 09:41:46

 Search: Search body:
Forums (1)