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 A-1-B-9-C 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 D-0-E-8-F 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: A-1-B-9-C-0-E-8-A (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 2007-10-16 20:33:58