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

 Arrange with 3-4-5 difference (Posted on 2007-10-16)
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.

 See The Solution Submitted by K Sengupta Rating: 4.0000 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 re: hint (spoiler) | Comment 2 of 7 |
(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
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
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

 Search: Search body:
Forums (0)