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  <jscholes@kalva.demon.co.uk> 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