[Integers Arranged: Q & Puzzle]

[Christian G. Bower]

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