7
$\begingroup$

Suppose an array of length $n$(odd number) which is composed with only $0$.

We start to ‘flip’( or ‘change’) numbers with following rules.

  1. [1, 1] → [0, 0]
  2. [0, 0] → [1, 1]
  3. [1, 0] or [0, 1] : do not change.
  4. Change elements sequentially and rotationally(when you reach at the end of the array), and repeat until the array becomes its initial state.

For example, if the length of the array is 3,

0   [0 0 0] #start
1   [1 1 0] #first and second element is [0, 0], by rule 2, it became [1, 1]
2   [1 1 0] #third and first element = [0, 1], by rule 3, just pass.
3   [1 1 0] #second and third = [1, 0], pass
4   [0 0 0] #first and second = [1, 1], by rule 1, change it to [0, 0].

After 4 steps, the array repeats its configuration, so, the period is $4$.

Another example, $n = 5$

0   [0 0 0 0 0]
1   [1 1 0 0 0]
2   [1 1 1 1 0]
3   [1 1 1 1 0]
4   [1 0 0 1 0]
5   [1 0 0 1 0]
6   [1 0 0 1 0]
7   [1 0 0 1 0]
8   [1 0 0 1 0]
9   [1 1 1 1 0]
10  [1 1 1 1 0]
11  [0 0 1 1 0]
12  [0 0 0 0 0]

The period is $12$.

And when $n=7$,

0   [0 0 0 0 0 0 0]
1   [1 1 0 0 0 0 0]
2   [1 1 1 1 0 0 0]
3   [1 1 1 1 1 1 0]
4   [1 1 1 1 1 1 0]
5   [1 0 0 1 1 1 0]
6   [1 0 0 0 0 1 0]
7   [1 0 0 0 0 1 0]
8   [1 0 0 0 0 1 0]
9   [1 0 1 1 0 1 0]
10  [1 0 1 1 0 1 0]
11  [1 0 1 1 0 1 0]
12  [1 0 1 1 0 1 0]
13  [1 0 1 1 0 1 0]
14  [1 0 1 1 0 1 0]
15  [1 0 1 1 0 1 0]
16  [1 0 0 0 0 1 0]
17  [1 0 0 0 0 1 0]
18  [1 0 0 0 0 1 0]
19  [1 1 1 0 0 1 0]
20  [1 1 1 1 1 1 0]
21  [1 1 1 1 1 1 0]
22  [0 0 1 1 1 1 0]
23  [0 0 0 0 1 1 0]
24  [0 0 0 0 0 0 0]

The period is $24$.

It looks like the series of periods follows A046092 (0, 4, 12, 24, 40, 60, 84, 112, 144, 180, 220, 264,… )

How can I prove this?

(If you want to look into more longer cases, refer here )

(Any modification of my English will be appreciated. English is not my mother tongue.)

$\endgroup$
4
  • $\begingroup$ looks like last column is always zero and the first column goes from 0 to 1 on first step ... stays 1 throughout and turns to zero and stays there for steps N-(n-1)/2 to N? also 2nd to last column sequence plays out as the reverse order of 1st column, that is, first (n-1)/2 of 2nd to last column are 0 and then 1 all through until final step $\endgroup$ Commented Aug 18, 2017 at 1:52
  • $\begingroup$ Is column 2 the reverse of column n-2? $\endgroup$ Commented Aug 18, 2017 at 1:57
  • $\begingroup$ and column x the inverse of column n-x? $\endgroup$ Commented Aug 18, 2017 at 10:52
  • $\begingroup$ What is the order of swapping? $[1,2],[1,3],...,[1,n],[2,3],...,[2,n],...,[n-1,n],[1,2],...$ ? $\endgroup$ Commented Sep 20, 2017 at 7:12

1 Answer 1

0
$\begingroup$

This question is quite old, but as there is no answer yet, I decided to answer it.

Lets split or steps in groups of size $n$, so that after each "batch", the cursor is back at the beginning of the list. This batch is equivalent at the following operations:

  • For each pair (even-odd), if they are equal, flip them. ($\frac{n-1}{2}$ steps)
  • For each pair (odd-even), if they are equal, flip them. ($\frac{n+1}{2}$ steps)

As the last element of the list is always a zero bordered by ones, it can be safely ignored.

So applying these operations in order, one gets the following pattern:

 0 : 000000000
 4 : 111111110
 9 : 100000010
13 : 101111010
18 : 101001010

At each step, there is a clump of same value element, surrounded by alternating elements. Each step, the clump flips its value, leaving the two outermost values the same, growing the alternating area. This goes on until the middle cannot be swapped anymore, and the last step will be a no-op. Then, because of the reversibility of the described operations, it will reverse the effects and end back at the original state:

22 : 101001010
27 : 101111010
31 : 100000010
36 : 111111110
40 : 000000000

Because of this, the operation will reach its initial state after $n$ such operations, or $n\frac{n-1}{2}+\frac{n-1}{2}=\frac{(n-1)(n+1)}{2}$ original operations. The odds terms of this formula match the given sequence in the question.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .