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.)
 10 x 10 -- A Start | Comment 3 of 6 |
When there are 10 towns in each of states A and B, with each A-town Ai connected to each B-town Bj by a road of color c, i,j,c=0,...,9, the conditions of the problem can be satisfied by choosing c=c(i,j)=i+j mod 10. When the states have no more than 10 towns, we can, as necessary, just delete towns from the 10 x 10 case. When a  state has more than 10 towns, perhaps we can again fall back on the 10 x 10 case by choosing 10 primary towns and allocating the roads of the nonprimary towns to suitable primary towns.
 Posted by Richard on 2004-03-05 13:26:18

 Search: Search body:
Forums (0)