Is it possible to place the numbers 0,1,2,3,4,5,6,7,8,9 (not necessarily in this order) in a circle such that the difference between any two neighboring numbers is 3, 4 or 5?
If it is possible, show how; if it is impossible, prove that to be the case.
First, a few points:
* if we prove that the 3,4,5 constraint forces a cycle with fewer than 10 numbers then the solution is impossible, since the solution as stated is a cycle of 10 numbers.
* every number must be adjacent to exactly two other numbers
OK, consider 1 and 9, which both must be adjacent to two of 4,5,6. They can't be adjacent to the same pair or that would make a cycle of four, but they must have at least one common member because there are only three choices for potentially four adjacent spots, so part of the chain must contain A1B9C where A,B,C are distinct members of {4,5,6}.
A similar argument applies to 0 and 8, which both must be adjacent to 3,4,5. Another part of the chain, then, must be D0E8F where D,E,F are distinct members of {3,4,5}
Taken together, these two fragments require that two of ABC and DEF are equal (to 4 and 5). Now, B can't match anything sandwiched between 1 and 9 nor can E, so A and C must match D and F (it doesn't matter if A=D and C=F or A=F and C=D.) Unfortunatly, that creates a cycle: A1B9C0E8A (if A=F and C=D, for example). It is a cycle, however, that does not include 2 or 7 and so is not a solution.
Since the requirement forces a cycle that fails to include 2 or 7, there is no solution and this proposed placement is impossible.

Posted by Paul
on 20071016 20:33:58 