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

Home > Just Math
Arrange with 3-4-5 difference (Posted on 2007-10-16) Difficulty: 3 of 5
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
            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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information