[Integers Arranged: Q & Puzzle]

[Kennedy]

For what's it worth, here are a few more terms:

31: 23642
32: 36616
35: 140500

Kennedy

----- Original Message -----
From: "Christian G. Bower" <bowerc at usa.net>
To: "seqfan" <seqfan at ext.jussieu.fr>
Sent: Tuesday, November 26, 2002 1:13 AM
Subject: Re: [Integers Arranged: Q & Puzzle]


> Leroy Quet <qqquet at mindspring.com> wrote:
>
> > This seems like something that MUST have been thought about before.
>
> > For a positive integer, n, take all of the distinct integers 1 to n.
> > Place them along an integer number-line such that:
> > (Or you can imagine placing n marbles, labeled 1 to n, into a row of
> > boxes, one marble per box, such that...)
>
> > 1 is placed anywhere along the line.
> > (m+1) is placed m steps (integer-positions or boxes) exactly from m,
> > for 1 <= m <= n-1.
> > n is placed as to be n steps from 1.
> > No two placed-integers share a position
> > (ie. no more than one marble per box).
> > (But some positions may be without any placed-integer,
> > ie. some boxes may be empty.)
>
> > First, the question: How many solutions are there for any given n?
>
> Note that the last marble is 1 +/- 2 +/- 3 +/- ... +/- (n-1) units from
> the starting position in either direction. Thus there are no solutions
> for n == 1 or 2 mod 4 as the distance will either be odd when n is even or
> vice versa. For other values we have:
>
> 3,4:   2
> 7,8:   2
> 11:   10
> 12:   14
> 15:   36
> 16:   40
> 19:  134
> 20:  258
> 23:  702
> 24: 1040
> 27: 4170
> 28: 5996
>
> My algorithm is not particularly clever. All I do is at each phase is move
> right or left, going through all 2^(n-1) possibilities.
>
> Should the EIS entry be: 0,0,2,2,0,0,2,2,0,0,10,14,... or should we
> delete the zeros and (perhaps also) half the numbers?
>
> This also suggests two other problems.
>
> A. Drop the requirement that each box have at most one marble, then this
> becomes the number of ways to write:
>
> +/- n = +/- 1 +/- 2 +/- 3 +/- ... +/- (n-1)
>
> which begins:
>
> 3,4:   2
> 7:     8
> 8:    14
> 11:   70
> 12:  124
> 15:  722
> 16: 1314
>
> A063865
> (and this suggests including the 0s in the sequence)
>
> B. Drop the requirement that marbles 1 and n be n apart.
>
> which begins:
>
>  1:   1
>  2:   2
>  3:   4
>  4:   6
>  5:  10
>  6:  18
>  7:  30
>  8:  50
>  9:  78
> 10: 130
> 11: 210
>
> Not in EIS
>
> Christian
>
>