Permutation(?): + Integers Increasingly Arranged

[David Wasserman]

Yes, it is a permutation.  We need to show that every space gets 
filled eventually.  By induction, it is enough to prove that the 
left-most space gets filled eventually.  We define a related sequence:
     When n is placed, let b(n) be the number of empty spaces to the left of n.
This sequence obeys a recurrence:
     If b(n) >= n, b(n + 1) = b(n) - n;
     If b(n) < n,  b(n + 1) = b(n) + n - 1.
What we need to show is that this sequence will always eventually get 
back to 0.
Here's some terms:
0, 0, 1, 3,
6, 1, 6,
12, 4, 12, 2, 12, 0, 12,
25, 10, 25, 8, 25, 6, 25, 4, 25, 2, 25, 0, 25,
51, 23, 51, 21, 51, 19, ..., 51, 1, 51,
102, 49, 102, 47, ..., 102, 1, 102,
204, 100, 204, ..., 2, 204, 0, 204,
409, 202, ...

You can see the pattern here.  The sequence is divided into chunks. 
Each chunk is the interleave of (1) a constant sequence, and (2) a 
sequence that descends by 2s.  If the descending sequence is even, 
the chunk ends when it reaches 0; otherwise the chunk ends when it 
reaches 1.
The parities of the chunks obey a cycle:
1) odd descending, even constant; then
2) even descending, even constant; then
3) even descending, odd constant; then
4) odd descending, odd constant; then
and then back to 1).  In particular, there will always be more chunks 
with even descending terms, so the sequence will always eventually 
get back to 0.

  - David Wasserman



Leroy Quet wrote:
>1, 2, 13, 3, 6, *, 4, 11, *, 9, 5, * 7, *, *, *, *, *, *, 8,
> *, 10, 16, 12, *, 14, *, *, *, *, *, *, *, *, *, *, *, *, *, 15,...