Friday, 11 March 2016

permutations - Flipping odd number array by two numbers in series.

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.)

No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...