◆千葉県 なのはな子 さんからの解答
２進法にしてみたら何かわかるかと思いましたが、何もわかりませんでした。
おもしろい数の並び方にはなりましたが、難しいです。
◆広島県 清川 育男 さんからの解答
【おまけ６】
ID Number: A046932
Sequence:
3,7,15,21,63,127,63,73,889,1533,3255,7905,11811,32767,255,
273,253921,413385,761763,5461,4194303,2088705,2097151,
10961685,298935,125829105,17895697,402653181,10845877,
2097151,1023,1057,255652815,3681400539
Name:
Set S_0 = 11...1 (n times); S_{i+1} is formed by applying D to last n bits of S_i and appending result to S_i; sequence gives period of resulting infinite string.
Comments:
D is the derivative mod 2: e.g. a,b,c,d,e -> a+b,b+c,c+d,d+e.a(n) equals the multiplicative order of x modulo the binary polynomial
1 + xn-1 + xn.
References
L. Bartholdi, Lamps, factorizations and finite fields, Amer. Math. Monthly, 107 (No. 5, May 2000), 429-436 for an interpretation in terms of a circle of light bulbs.
Example:
n=4 produces 111100010011010, so a(4) = 15.
See also: Cf. A010760, A055061.
Keywords: nonn,easy,nice
Offset: 2
Author(s): Russell Walsmith (russw@mailcity.com, russw@lycos.com)
Extension: More terms from Dean Hickerson (dean@math.ucdavis.edu)
REM 今週の問題−第159回の解答プログラム
REM ON...1 OFF...-1
DIM A(36)
FOR M=2 TO 36
PRINT USING "###":M;
FOR I=1 TO M
LET A(I)=1
NEXT I
LET Z=0
FOR N=1 TO 9999999999
FOR J=1 TO M
LET Z=Z+1
IF J=1 THEN
LET J1=M
ELSE
LET J1=J-1
END IF
IF A(J1)=1 THEN
LET A(J)=A(J)*(-1)
END IF
REM チェック
FOR K=1 TO M
IF A(K)<>1 THEN
GOTO 10
END IF
NEXT K
PRINT Z
GOTO 20
10 NEXT J
NEXT N
20 NEXT M
END
2 3
3 7
4 15
5 21
6 63
7 127
8 63
9 73
10 889
11 1533
12 3255
13 7905
14 11811
15 32767
16 255
17 273
18 253921
19 413385
20 761763
21 5461
22 4194303
23 2088705
24 2097151
25 10961685
26 298935
27 125829105
28 17895697
29 402653181
30 10845877
31 2097151
32 1023
33 1057
34 255652815
35 3681400539
36 22839252821
◆愛知県 Y.M.Ojisan さんからの解答
手順の回数を問題としているので、操作する位置を回転させないで、操作後ランプの方を回転(シフト)しても同じである。
このとき手順は以下である。
（１）もし、（Ｎ−１）番目のランプがついていれば、０番目のランプのＯＮ、ＯＦＦを切り替える。
もし、（Ｎ−１）番目のランプがついていないれば、０番目のランプの状態は変わらない。
（２）（Ｎ−１）番目を（Ｎ−２）番目に、（Ｎ−２）番目を（Ｎ−３）番目に。。。。１番を０番に、０番を（Ｎ−１）番目に回転する。
を繰り返す。
電球点灯を１、消灯を０で表すと、その手順は上図のようなシフト＋排他論理和のデジタル回路であらわされる。
一般にこれはＬＦＳＲ（線形フィードバックシフトレジスタ）として詳細に研究されている。
| 参考書： 誤り訂正符号とその応用、映像メディア研究会編、江藤良純、金子敏信監修 その他LFSRで検索すると多数サイトあり。 |
【問題１】 １５回
【問題２】 ６３回
【おまけ１】 ｎ２−１
【おまけ２】
問題のＬＦＳＲは逆元（手順）があり、次のＬＦＳＲで実現される。
従って、Ｎビットの有限個のパターンは枝分かれのない単一のループを形成し、必ず元に戻る。
即ち何れ全部点灯する。
（注：全部０は全部０のまま、もループとする）
【おまけ３】
ＬＦＳＲの０番位置のビット変化を（n＋1）×(n-1)の行列に横書きの順でうめると、下図のような帰納的な関係が見える。
なお、図中の黒矢印は操作に対応しており、行列をAK (i,j)で表すとき
AK (i,j) = AK (i,j-1) + AK(i-1,j-1) mod 2 を実施する。
但し、端まで行ったら、赤矢印で示すように一列目一行下に入れる。
元に戻り、帰納的な関係とはｎ＝２KにおけるAKには上図に示すように、
AK-1が２個とAK-1の最下行が無いものが１個図のような３隅の位置に存在し、
| その他はA | K | (1, | n 2 | )とA | K | ( | n 2 | ， | n 2 |
)を除き０である。 |
一般にAKがその様な構造をもっているとき、
下図のようにして作った行列ＢはＡK+1になっている。
ここでその様な構造とは、
（１）その内部において AK (i,j) = AK (i,j-1) + AK(i-1,j-1) mod 2が成立している。
（２）一行目は全部１であり、最下行（ｎ＋１行目）は全部０である。
（３）一列目は１〜２行目が１でその他は０である。
（４）最終列（ｎ−１列目）は最下行を除き１である。
∵
○ Ｂが（２）〜（４）を満たすことは容易にわかる。詳細略
○ 最終行の次の行（緑）を（１）の式で計算すると、図に示すように最初が１になり、最終行が０であるから全部１である。
これは１行目の状態と矛盾していない。
○ 最終列から第一列目の３行目以下を（１）の式で計算すると全部０である。
また２行目の１も図中の青矢印に示されるように矛盾していない。
○ 図中赤丸の部分の関係も矛盾がないことは容易にわかる。証明略。
○ 最後に図中青２重丸の部分の関係について述べる。
AKの最下行は本来全部０である。
これはその先頭列が０であることにより決まっている。
従って、もし１なら全部１である。
AKの１行目は全部０である。
よって、図中青２重丸の部分も矛盾が無い。
以上より帰納的な関係が証明された。
ＬＦＳＲは線形な関係である。
従って、以上のようにして得られたＢ＝ＡK+1(i，j)は唯一の解であり、
ｎ＝２Kの場合は最長ｎ2−１の周期をもつことが証明された。
一方１がｎ個連続する部分は１行目から２行目の先頭にかけてのみである。
なぜなら、ｎ−１行は全部０で、それ以外のところでも１列目の０により少なくともｎ−１連続するなかに０が１個あるからである。
よって、周期はｎ2−１より小さくならず、おまけ１の解答が証明された。
【おまけ４】
ＬＦＳＲの０番位置のビット変化を（n）×(n-１)の行列に横書きの順でうめると、下図のような帰納的な関係が見える。
但し最初余分の１ビット（値１）は無視している。
ここで、帰納的な関係とはｎ＝２K＋１におけるAKには上図に示すように、
AK-1が２個とAK-1の最下行が無いものが１個図のような３隅の位置に存在し、その他は０である。
一般にAKがその様な構造をもっているとき、
下図のようにして作った行列ＢはＡK+1になっている。
ここでその様な構造とは、
（１）その内部において AK (i,j) = AK(i,j-1) + AK (i-1,j-1) mod 2が成立している。
（２）一行目は全部１であり、最下行（ｎ＋１行目）は全部０である。
（３）一列目は１行目が１でその他は０である。
（４）最終列（ｎ−１列目）は最下行を除き１である。
∵
○Ｂが（２）〜（４）を満たすことは容易にわかる。詳細略
○ 最終列から第一列目の２行目以下を（１）の式で計算すると全部０であり、この間で矛盾していない。
○ おまけ３と同様、図中赤丸、青２重丸の部分の関係も矛盾がないことは容易にわかる。証明略。
○問題は１行目と最終行の関係であるが、上図に示されるように、行列の０行目と最終＋１行を追加し、順序とおり埋めると矛盾してないことがわかる。
よって、ＢはAK+1である。
このＢの周期はおまけと３と同様にして、(n-1)ｎであるといえる。
よって余分の１個を戻すと、周期はｎ2−ｎ＋１である。
【おまけ５】
周期３２５５（PC解です。）
◆東京都 明 さんからの解答
【問題１】 １５回
【問題２】 ６３回
【おまけ１】
２２Ｋ−１
【おまけ２】
最初のランプの状態をＳ0とし、以下のランプの状態を順次Ｓ1、Ｓ2と呼ぶ。
（ランプの状態とは点滅の状態と共に、操作されているランプがどれかの状態を含む）
任意の状態をＳk（ｋ≧1）としたとき、１つ前の状態Ｓk-1は一意に定まる。
具体的にはＳkの状態でｋ番目のランプがＣk（ＯＮ＝1またはＯＦＦ＝0）となったとし、
この時ｋ-1番目のランプがＣk-1（ＯＮ＝1またはＯＦＦ＝0）とすれば
Ｓk-1ではｋ番目のランプは Ｃk＋Ｃk-1（mod2）と決定される。
以下順にＳk-2のｋ−1番目のランプ、Ｓk-3のｋ−2番目のランプが一意に決定される。
Ｓ0、Ｓ1、・・で初めて以前と同じ状態が発生した状態をＳjとすると
Ｓj≠Ｓk(k＝1〜j-1)
（もしＳj＝ＳkとするとＳkの１つ前の状態は異なるＳk-1とＳj-1の２つあることになる。）
したがってＳj＝Ｓ0
状態は有限であるので必ず有限回後に最初の状態Ｓ0に戻る。
（注）この状態とはランプの点滅の状態と、そのとき、どのランプが操作されているかの状態を含む。
単にランプの点滅の状態のみであればもっと早く同じ状態に到達する可能性がある。
(実際に問題１、問題２ではそのとおり）
いずれにせよ、有限回で始めと同じ状態に戻ることが証明された。
【おまけ３】
証明の概略を示します。
この問題は
Ｘn＋Ｘn-1＋１＝０（mod2），ｎ＝２k の条件で
Ｘp＝１（mod2）の最小の正整数ｐを求めることに等しい。
または、ランプの点滅状態を逆にたどれば（以下mod2を省略）
Ｘn＋Ｘ＋１＝０，ｎ＝２k の条件での
Ｘp＝１ の最小の正整数ｐを求めることに等しい。
後者の考え方をとれば
10000000・・・ を100・・・0011（２k+１桁）で割って、剰余が 1 になるところまでの桁数を求めることになる。
計算すると
| 先頭の1の次の桁から 剰余の最下位までの桁数 | 剰余 |
| 2k | 11 |
| 2×2k | 101 |
| 3×2k | 1111 |
| 4×2k | 10001 |
| 5×2k | 110011 |
| 6×2k | 1010101 |
| 7×2k | 11111111 |
| 8×2k | 100000001 |
| 2k×2k | 100・・・00001 （2k +1 桁） |
最後の剰余の桁100・・・00001 （2k +1 桁）を、
割る数100・・・0011（2k+１桁）で割ると
剰余は000・・・00010
剰余の1までの桁数は
2k×2k-1＝(2k)2-1＝22k-1
【おまけ４】
【おまけ３】と同様に
10000000・・・ を100・・・0011（２k+2桁）で割って剰余が 1 になるところまでの桁数を求める。
| 先頭の1の次の桁から 剰余の最下位までの桁数 | 剰余 |
| 2k×（2k+1） | 100・・・00001 （2k +1 桁） |
最後の剰余の桁100・・・00001 （2k +1 桁）を、
割る数100・・・0011（2k+2桁）で割ると
剰余は000・・・000001
剰余の1までの桁数は
2k×(2k+1)+1＝（n-1)n+1＝n2-n+1
【おまけ５】
実験をやっていると大変そうなので計算機でやらせて見ました。
個数 : 2 回数 ： 3 個数 : 3 回数 ： 7 個数 : 4 回数 ： 15 個数 : 5 回数 ： 21 個数 : 6 回数 ： 63 個数 : 7 回数 ： 127 個数 : 8 回数 ： 63 個数 : 9 回数 ： 73 個数 : 10 回数 ： 889 個数 : 11 回数 ： 1533 個数 : 12 回数 ： 3255 個数 : 13 回数 ： 7905 個数 : 14 回数 ： 11811 個数 : 15 回数 ： 32767 個数 : 16 回数 ： 255 個数 : 17 回数 ： 273 個数 : 18 回数 ： 253921 個数 : 19 回数 ： 413385 個数 : 20 回数 ： 761763 個数 : 21 回数 ： 5461 個数 : 22 回数 ： 4194303 個数 : 23 回数 ： 2088705 個数 : 24 回数 ： 2097151【おまけ６】 降参です。
◆ 問題へもどる
◆ 今週の問題へ
数学の部屋へもどる