[seqfan] Numbers in a circle

N. J. A. Sloane njas at research.att.com
Mon Dec 6 23:18:52 CET 2010


Numbers in a circle

Enough about licenses! Here is a problem that has been keeping 
me awake at night: Fix a positive integer L, say 10.
Is there a directed circle of L numbers,
all in the range 1 thru L, not necessarily all distinct,
with the property that a(n+1) tells you how far back around the circle
you have to go before you see another copy of a(n)?

Here's an example which doesn't quite work, 
but which will explain what I'm looking for:
(The "arrows" are just to show the direction.)

         ->
          1
       2     6
      2        2 |
    ^ 4        4 v
    |  2     1
          4
          <-

You see 10 numbers around a circle, arranged clockwise. Here L is 10.

Start with the 1 at the top. 
That this is 1 tells you that the previous term, 2, 
can also be found 1 step back.
The "2" at 10 o'clock tells you that the "2" at 9:30 o'clock is matched by
another 2 2 steps back, and indeed it is (the latter 2 being at 7 o'clock).
The 4 at 9 o'clock says that the term before it, 2, has a mate 4 steps back,
and it does.

If the terms are labeled a(0) through a(L-1), going
clockwise around the circle, then for all n, a(n+1) 
is the number of steps back round the circle before 
you see another a(n).

If a(n) only appears once, then a(n+1)=L, and conversely.

The condition fails for the 1 at 5 o'clock, and for the 2 at 2:30 o'clock
(which should be 10 since the 6 is unique)

The only solution I know, of any length L, is a circle with L 1's.
The problem is to show that there are no other solutions!
Can anyone help?

[I've tried a few things: for example, let A be the matrix
in which A_{i,j} is the number of times there is an i immediately
followed by a j. The sum of the i-th row is the number
of i's in the loop. The sum j A_{i,j} is L, for any i.
The matrix A has a lot of nice properies. Doesn't seem
to lead anywhere though.]

This question arises when one tries to analyze sequence A181391 
and its generalizations.

Neil





More information about the SeqFan mailing list