From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math,rec.puzzles
Subject: Re: Russian 87 puzzle
Date: 16 Nov 1998 18:24:58 GMT
John Scholes wrote:
>(a) Can you arrange the numbers 0, 1, ... , 9 on the circumference of a
>circle, so that the difference between every pair of adjacent numbers is
>3, 4 or 5? For example, we can arrange the numbers 0, 1, ... , 6 thus:
>0, 3, 6, 2, 5, 1, 4.
>
>(b) What about the numbers 0, 1, ... , 13?
brainless SPOILER follows
I'm not sure what structure we're supposed to see here. The answers are
(a) "no" and (b) "yes", but I only know this by brute-force computation.
In an absolutely brainless way I defined a Maple procedure to take an
initial segment s and try to complete it to a permutation of {0, ..., N-1}:
complete:=proc(s)
local j, k, x, U;
k := nops(s);
if k = N then RETURN({s}) fi;
x := s[k];
U := {};
for j from 3 to 5 do
if j < x then
if not member(x - j, s) then
U := U union complete([op(s), x - j])
fi
fi;
if x < N - j then
if not member(x + j, s) then
U := U union complete([op(s), x + j])
fi
fi
od;
RETURN(U):
end:
This doesn't check that the sequence is correct _on the circle_, so we
ferret out the right ones:
loopy:=proc(S)
local U, u;
U := {};
for u in S do if member(u[N], {3, 4, 5}) then U := U union {u} fi od;
RETURN(U):
end:
So what's possible and what's not?
for N from 1 to 14 do
lin:=complete([0]): circ:=loopy(lin):
lprint(N, nops(lin), nops(circ));
if nops(circ)>0 then print(circ[1]):fi:
od:
Here's the output (it took a few minutes to generate):
1 1 0
2 0 0
3 0 0
4 0 0
5 0 0
6 0 0
7 2 2
[0, 4, 1, 5, 2, 6, 3]
8 18 10
[0, 3, 6, 2, 7, 4, 1, 5]
9 54 12
[0, 3, 7, 2, 6, 1, 4, 8, 5]
10 56 0
11 24 0
12 24 0
13 56 0
14 232 30
[0, 3, 8, 12, 9, 13, 10, 7, 11, 6, 2, 5, 1, 4]
A trivial adjustment of the program allows us to tighten the requirements
on our sequences; for example, I asked for sequences which actually keep
the differences in {3,4} instead; now there are fewer:
7 2 2
[0, 4, 1, 5, 2, 6, 3]
the other is: [0, 3, 6, 2, 5, 1, 4]
8 4 0
9 0 0
14 11 2
[0, 3, 7, 11, 8, 12, 9, 13, 10, 6, 2, 5, 1, 4]
other: [0, 4, 1, 5, 2, 6, 10, 13, 9, 12, 8, 11, 7, 3]
Evidently there's a pattern here; let's keep the run going:
15 20 0
16 8 0
17 4 0
18 4 0
19 8 0
20 20 0
21 84 4
[0, 4, 1, 5, 2, 6, 10, 14, 18, 15, 19, 16, 20, 17, 13, 9, 12, 8, 11, 7, 3]
[0, 3, 7, 11, 8, 12, 9, 13, 17, 20, 16, 19, 15, 18, 14, 10, 6, 2, 5, 1, 4]
[0, 3, 7, 10, 13, 17, 20, 16, 19, 15, 18, 14, 11, 8, 12, 9, 6, 2, 5, 1, 4]
[0, 4, 1, 5, 2, 6, 9, 12, 8, 11, 14, 18, 15, 19, 16, 20, 17, 13, 10, 7, 3]
Yours in thoughtless computation,
dave