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.
(In reply to
hint by bubu)
The sequences below, for clockwise order (alternatively anti-clockwise), all start with the number 0, as that number is as good as any to start with. The next one clockwise could be a 3 or 4 or 5. After 0,3 could come a 6 or 7 or 8, as the 0 was already used. After 0,4 could come 1 or 7 or 8 or 9. After 0,5 could come 1, 2, 8 or 9.
All possible sequences are shown. They are in lexicographic order (ordered mainly by the digit after the 0, then by the next digit, etc.).
Take as an example the line
0 3 6 1 5 9 4 8
This line could not continue further, as 3, 4 and 5 were already used, and those would be the only numbers that could be adjacent to the 8.
The next sequence after the above changes in the 4th column, as the 4 could not be replaced by 5 or 6 as those had already been used. Proceeding backward, the 9 is already the highest number possible from the 5, and in turn, the 5 could not be replaced by 6, as 6 was used in this sequence previous to the 1. So the 1 is replaced by a 2, the next number available next to the 6. All the lowest possible choices are then made, to produce the next sequence:
0 3 6 2 5 1 4 7
Thus all the possibilities are accounted for.
Only a few of the sequences (56 out of the 286 sequences) actually go all the way to fill in 10 digits. But all of these end with 1, 2, 7, 8 or 9, none of which is legal to place next to the 0, as would be necessary on a circular layout.
Thus this is impossible.
0 3 6 1 4 7 2 5 8
0 3 6 1 4 7 2 5 9
0 3 6 1 4 8 5 2 7
0 3 6 1 4 8 5 9
0 3 6 1 4 9 5 2 7
0 3 6 1 4 9 5 8
0 3 6 1 5 2 7 4 8
0 3 6 1 5 2 7 4 9
0 3 6 1 5 8 4 7 2
0 3 6 1 5 8 4 9
0 3 6 1 5 9 4 7 2
0 3 6 1 5 9 4 8
0 3 6 2 5 1 4 7
0 3 6 2 5 1 4 8
0 3 6 2 5 1 4 9
0 3 6 2 5 8 4 1
0 3 6 2 5 8 4 7
0 3 6 2 5 8 4 9
0 3 6 2 5 9 4 1
0 3 6 2 5 9 4 7
0 3 6 2 5 9 4 8
0 3 6 2 7 4 1 5 8
0 3 6 2 7 4 1 5 9
0 3 6 2 7 4 8 5 1
0 3 6 2 7 4 8 5 9
0 3 6 2 7 4 9 5 1
0 3 6 2 7 4 9 5 8
0 3 6 9 4 1 5 2 7
0 3 6 9 4 1 5 8
0 3 6 9 4 7 2 5 1
0 3 6 9 4 7 2 5 8
0 3 6 9 4 8 5 1
0 3 6 9 4 8 5 2 7
0 3 6 9 5 1 4 7 2
0 3 6 9 5 1 4 8
0 3 6 9 5 2 7 4 1
0 3 6 9 5 2 7 4 8
0 3 6 9 5 8 4 1
0 3 6 9 5 8 4 7 2
0 3 7 2 5 1 4 8
0 3 7 2 5 1 4 9 6
0 3 7 2 5 1 6 9 4 8
0 3 7 2 5 8 4 1 6 9
0 3 7 2 5 8 4 9 6 1
0 3 7 2 5 9 4 1 6
0 3 7 2 5 9 4 8
0 3 7 2 5 9 6 1 4 8
0 3 7 2 6 1 4 8 5 9
0 3 7 2 6 1 4 9 5 8
0 3 7 2 6 1 5 8 4 9
0 3 7 2 6 1 5 9 4 8
0 3 7 2 6 9 4 1 5 8
0 3 7 2 6 9 4 8 5 1
0 3 7 2 6 9 5 1 4 8
0 3 7 2 6 9 5 8 4 1
0 3 7 4 1 5 2 6 9
0 3 7 4 1 5 8
0 3 7 4 1 5 9 6 2
0 3 7 4 1 6 2 5 8
0 3 7 4 1 6 2 5 9
0 3 7 4 1 6 9 5 2
0 3 7 4 1 6 9 5 8
0 3 7 4 8 5 1 6 2
0 3 7 4 8 5 1 6 9
0 3 7 4 8 5 2 6 1
0 3 7 4 8 5 2 6 9
0 3 7 4 8 5 9 6 1
0 3 7 4 8 5 9 6 2
0 3 7 4 9 5 1 6 2
0 3 7 4 9 5 2 6 1
0 3 7 4 9 5 8
0 3 7 4 9 6 1 5 2
0 3 7 4 9 6 1 5 8
0 3 7 4 9 6 2 5 1
0 3 7 4 9 6 2 5 8
0 3 8 4 1 5 2 6 9
0 3 8 4 1 5 2 7
0 3 8 4 1 5 9 6 2 7
0 3 8 4 1 6 2 5 9
0 3 8 4 1 6 2 7
0 3 8 4 1 6 9 5 2 7
0 3 8 4 7 2 5 1 6 9
0 3 8 4 7 2 5 9 6 1
0 3 8 4 7 2 6 1 5 9
0 3 8 4 7 2 6 9 5 1
0 3 8 4 9 5 1 6 2 7
0 3 8 4 9 5 2 6 1
0 3 8 4 9 5 2 7
0 3 8 4 9 6 1 5 2 7
0 3 8 4 9 6 2 5 1
0 3 8 4 9 6 2 7
0 3 8 5 1 4 7 2 6 9
0 3 8 5 1 4 9 6 2 7
0 3 8 5 1 6 2 7 4 9
0 3 8 5 1 6 9 4 7 2
0 3 8 5 2 6 1 4 7
0 3 8 5 2 6 1 4 9
0 3 8 5 2 6 9 4 1
0 3 8 5 2 6 9 4 7
0 3 8 5 2 7 4 1 6 9
0 3 8 5 2 7 4 9 6 1
0 3 8 5 9 4 1 6 2 7
0 3 8 5 9 4 7 2 6 1
0 3 8 5 9 6 1 4 7 2
0 3 8 5 9 6 2 7 4 1
0 4 1 5 2 6 3 7
0 4 1 5 2 6 3 8
0 4 1 5 2 6 9
0 4 1 5 2 7 3 6 9
0 4 1 5 2 7 3 8
0 4 1 5 8 3 6 2 7
0 4 1 5 8 3 6 9
0 4 1 5 8 3 7 2 6 9
0 4 1 5 9 6 2 7 3 8
0 4 1 5 9 6 3 7 2
0 4 1 5 9 6 3 8
0 4 1 6 2 5 8 3 7
0 4 1 6 2 5 9
0 4 1 6 2 7 3 8 5 9
0 4 1 6 3 7 2 5 8
0 4 1 6 3 7 2 5 9
0 4 1 6 3 8 5 2 7
0 4 1 6 3 8 5 9
0 4 1 6 9 5 2 7 3 8
0 4 1 6 9 5 8 3 7 2
0 4 7 2 5 1 6 3 8
0 4 7 2 5 1 6 9
0 4 7 2 5 8 3 6 1
0 4 7 2 5 8 3 6 9
0 4 7 2 5 9 6 1
0 4 7 2 5 9 6 3 8
0 4 7 2 6 1 5 8 3
0 4 7 2 6 1 5 9
0 4 7 2 6 3 8 5 1
0 4 7 2 6 3 8 5 9
0 4 7 2 6 9 5 1
0 4 7 2 6 9 5 8 3
0 4 7 3 6 1 5 2
0 4 7 3 6 1 5 8
0 4 7 3 6 1 5 9
0 4 7 3 6 2 5 1
0 4 7 3 6 2 5 8
0 4 7 3 6 2 5 9
0 4 7 3 6 9 5 1
0 4 7 3 6 9 5 2
0 4 7 3 6 9 5 8
0 4 7 3 8 5 1 6 2
0 4 7 3 8 5 1 6 9
0 4 7 3 8 5 2 6 1
0 4 7 3 8 5 2 6 9
0 4 7 3 8 5 9 6 1
0 4 7 3 8 5 9 6 2
0 4 8 3 6 1 5 2 7
0 4 8 3 6 1 5 9
0 4 8 3 6 2 5 1
0 4 8 3 6 2 5 9
0 4 8 3 6 2 7
0 4 8 3 6 9 5 1
0 4 8 3 6 9 5 2 7
0 4 8 3 7 2 5 1 6 9
0 4 8 3 7 2 5 9 6 1
0 4 8 3 7 2 6 1 5 9
0 4 8 3 7 2 6 9 5 1
0 4 8 5 1 6 2 7 3
0 4 8 5 1 6 3 7 2
0 4 8 5 1 6 9
0 4 8 5 2 6 1
0 4 8 5 2 6 3 7
0 4 8 5 2 6 9
0 4 8 5 2 7 3 6 1
0 4 8 5 2 7 3 6 9
0 4 8 5 9 6 1
0 4 8 5 9 6 2 7 3
0 4 8 5 9 6 3 7 2
0 4 9 5 1 6 2 7 3 8
0 4 9 5 1 6 3 7 2
0 4 9 5 1 6 3 8
0 4 9 5 2 6 1
0 4 9 5 2 6 3 7
0 4 9 5 2 6 3 8
0 4 9 5 2 7 3 6 1
0 4 9 5 2 7 3 8
0 4 9 5 8 3 6 1
0 4 9 5 8 3 6 2 7
0 4 9 5 8 3 7 2 6 1
0 4 9 6 1 5 2 7 3 8
0 4 9 6 1 5 8 3 7 2
0 4 9 6 2 5 1
0 4 9 6 2 5 8 3 7
0 4 9 6 2 7 3 8 5 1
0 4 9 6 3 7 2 5 1
0 4 9 6 3 7 2 5 8
0 4 9 6 3 8 5 1
0 4 9 6 3 8 5 2 7
0 5 1 4 7 2 6 3 8
0 5 1 4 7 2 6 9
0 5 1 4 7 3 6 2
0 5 1 4 7 3 6 9
0 5 1 4 7 3 8
0 5 1 4 8 3 6 2 7
0 5 1 4 8 3 6 9
0 5 1 4 8 3 7 2 6 9
0 5 1 4 9 6 2 7 3 8
0 5 1 4 9 6 3 7 2
0 5 1 4 9 6 3 8
0 5 1 6 2 7 3 8 4 9
0 5 1 6 2 7 4 8 3
0 5 1 6 2 7 4 9
0 5 1 6 3 7 2
0 5 1 6 3 7 4 8
0 5 1 6 3 7 4 9
0 5 1 6 3 8 4 7 2
0 5 1 6 3 8 4 9
0 5 1 6 9 4 7 2
0 5 1 6 9 4 7 3 8
0 5 1 6 9 4 8 3 7 2
0 5 2 6 1 4 7 3 8
0 5 2 6 1 4 8 3 7
0 5 2 6 1 4 9
0 5 2 6 3 7 4 1
0 5 2 6 3 7 4 8
0 5 2 6 3 7 4 9
0 5 2 6 3 8 4 1
0 5 2 6 3 8 4 7
0 5 2 6 3 8 4 9
0 5 2 6 9 4 1
0 5 2 6 9 4 7 3 8
0 5 2 6 9 4 8 3 7
0 5 2 7 3 6 1 4 8
0 5 2 7 3 6 1 4 9
0 5 2 7 3 6 9 4 1
0 5 2 7 3 6 9 4 8
0 5 2 7 3 8 4 1 6 9
0 5 2 7 3 8 4 9 6 1
0 5 2 7 4 1 6 3 8
0 5 2 7 4 1 6 9
0 5 2 7 4 8 3 6 1
0 5 2 7 4 8 3 6 9
0 5 2 7 4 9 6 1
0 5 2 7 4 9 6 3 8
0 5 8 3 6 1 4 7 2
0 5 8 3 6 1 4 9
0 5 8 3 6 2 7 4 1
0 5 8 3 6 2 7 4 9
0 5 8 3 6 9 4 1
0 5 8 3 6 9 4 7 2
0 5 8 3 7 2 6 1 4 9
0 5 8 3 7 2 6 9 4 1
0 5 8 3 7 4 1 6 2
0 5 8 3 7 4 1 6 9
0 5 8 3 7 4 9 6 1
0 5 8 3 7 4 9 6 2
0 5 8 4 1 6 2 7 3
0 5 8 4 1 6 3 7 2
0 5 8 4 1 6 9
0 5 8 4 7 2 6 1
0 5 8 4 7 2 6 3
0 5 8 4 7 2 6 9
0 5 8 4 7 3 6 1
0 5 8 4 7 3 6 2
0 5 8 4 7 3 6 9
0 5 8 4 9 6 1
0 5 8 4 9 6 2 7 3
0 5 8 4 9 6 3 7 2
0 5 9 4 1 6 2 7 3 8
0 5 9 4 1 6 3 7 2
0 5 9 4 1 6 3 8
0 5 9 4 7 2 6 1
0 5 9 4 7 2 6 3 8
0 5 9 4 7 3 6 1
0 5 9 4 7 3 6 2
0 5 9 4 7 3 8
0 5 9 4 8 3 6 1
0 5 9 4 8 3 6 2 7
0 5 9 4 8 3 7 2 6 1
0 5 9 6 1 4 7 2
0 5 9 6 1 4 7 3 8
0 5 9 6 1 4 8 3 7 2
0 5 9 6 2 7 3 8 4 1
0 5 9 6 2 7 4 1
0 5 9 6 2 7 4 8 3
0 5 9 6 3 7 2
0 5 9 6 3 7 4 1
0 5 9 6 3 7 4 8
0 5 9 6 3 8 4 1
0 5 9 6 3 8 4 7 2
DECLARE SUB place (p!)
DIM SHARED posn(9), taken(9), ct9
OPEN "arrng345.txt" FOR OUTPUT AS #2
posn(0) = 0
place 1
PRINT ct9
CLOSE
END
SUB place (p)
didOne = 0: deadEnd = 0
FOR i = 1 TO 9
IF taken(i) = 0 THEN
IF ABS(i - posn(p - 1)) > 2 AND ABS(i - posn(p - 1)) < 6 THEN
taken(i) = 1
posn(p) = i
didOne = 1
IF p = 9 THEN
IF i > 2 AND i < 6 THEN
FOR j = 0 TO 9
PRINT posn(j);
PRINT #2, posn(j);
NEXT
PRINT
PRINT #2,
ELSE
deadEnd = 1
END IF
ELSE
place p + 1
END IF
taken(i) = 0
END IF
END IF
NEXT
IF didOne = 0 THEN
ct9 = ct9 + 1
FOR j = 0 TO p - 1
PRINT posn(j);
PRINT #2, posn(j);
NEXT
PRINT
PRINT #2,
END IF
IF deadEnd THEN
ct9 = ct9 + 1
FOR j = 0 TO p
PRINT posn(j);
PRINT #2, posn(j);
NEXT
PRINT
PRINT #2,
END IF
END SUB
|
|
Posted by Charlie
on 2007-10-16 16:03:43 |
re: hint (spoiler)
