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