Hello!
>Arrange 0 to 9 in a circular fashion such that the difference
>between any adjacent two numbers is either 3, or 4 or 5.
0 has almost 1 neighbours in [4,5,6]
1 has 2 neighbours in [4,5,6]
2 has almost 1 neighbours in [4,5,6]
8 has almost 1 neighbours in [4,5,6]
9 has 2 neighbours in [4,5,6]
==
4+5+6 have totally almost 7 neighbours -> impossible
>I accidently solved the problem using only 1 to 9. That puzzle
>has 6 solutions, one of them special. Can you find it?
159483726 is special!
Somebody probably solved general cases of this.
Juha
-------------------------------------------------------------
The 6 solutions for arranging 1-9 in a circular fashion so that each digit
is adjacent to digits which differ from it by 3, 4, or 5 are:
415962738
615948372
514962738
614958372
416952738
516948372
They fall into three pairs which are equivalent if 1 and 9 are swapped.
Note that each solution consists of x1x9x where the xes are 4, 5, and 6
in some order, combined with the string 2738 in the only orientation that
works at both ends. The first part is forced by 1 and 9 only being able to
be next to 4, 5, and 6; the other is forced because 2 can only be next to 7
and an end of the first string which contains 5 or 6, and likewise for
8 with 3 and an end of the string which contains 4 or 5.
The 159483726 solution is special because all the differences are 4 or 5.
Using 0-9, the problem is unsolvable because 0, 1, 8, and 9 must
be adjacent to only 3, 4, 5, and 6. Each digit needs two adjacent digits,
so this uses up all eight sides of 3, 4, 5, and 6. However, if we do this,
we will form a loop of eight digits which does not contain 2 or 7.
Joseph DeVincentis
-----------------------------------------------------------------
I'm pretty sure the "special" solution is 1-6-2-7-3-8-4-9-5 - By skipping every other number, it counts 1-9.
Proof that 0-9 will not work:
Assume first that 2 and 7 are not consecutive. If this is true, none of 0,1,2,7,8, or 9 can be next to each other. As we only have four other numbers (3,4,5, and 6), we don't have enough numbers left to separate every pair - we have four, we need six.
So 2 must be next to 7. Still, we need to separate five "units" (2-7,0,1,8,9) and only four numbers remaining to separate them. Since we need five more numbers to separate all five units, no ring can be formed.
- Matt Elder
-------------------------------------------------------------------------
The six solutions for 1 through 9:
1-4-9-6
| |
5 2
| |
8--3--7
1-4-8-3
| |
5 7
| |
9--6--2
1-5-2-7
| |
6 3
| |
9--4--8
1-5-9-4
| |
6 8
| |
2--7--3
1-4-8-3
| |
6 7
| |
9--5--2
1-4-9-5
| |
6 8
| |
2--7--3
Alan Lemm
-------------------------------------------------------------
Ed,
Here are the solutions to your modified problem (1-9):
148372596
148372695
149627385
149583726
152738496
159483726
I believe the last one is the special one you were referring to; it has
no differences of 3.
I wrote a quick program to confirm that there's no solution when you
try the puzzle with 0-9, but I had trouble coming up with a logical
reason why there is no solution...
Nathan Stohler