|
おーちゃん |
|
N=2^n の場合を考えてみました。
（以下、XOR を取りやすいように N桁の数 の代わりに 0,1,2,……,N-1 を並べ替えた数列で考えます） {0,1,2,3,……,N-1} に対して {0,0,…,0},{1,1,…,1},……,{N-1,N-1,…,N-1} を XOR して {0,1,2,3,……,N-1} {1,0,3,2,……,N-2} {2,3,0,1,……,N-3} {3,2,1,0,……,N-4} …… {N-2,N-1,N-4,N-3,……,1} {N-1,N-2,N-3,N-4,……,0} の N個を得るところまでは OK。 次にこれらに 0 を除く 1,……,N-1 を置換する操作 f を順次加えて N(N-1)個に増やします。 この置換操作 f の求め方を以下のように考えました： (1) a(0)=1, a(1)=2, a(2)=4, ……, a(n-1)=2^(n-1) とする (2) a(n) 以降は次の漸化式で決定する a(k) = a(k-n) XOR a(k-n+1) (3) f(a(n)) = a(n+1) とする すると、a(k) は周期がたかだか N-1 の周期的数列になります。 もし a(k) の周期が N-1 になっていれば、f は 1,……,N-1 全体を巡回する置換操作となります。 たとえば n=3 (N=8) のときは f : 1→2→4→3→6→7→5→1 （周期 7） n=4 (N=16) のときは f : 1→2→4→8→3→6→12→11→5→10→7→14→15→13→9→1 （周期 15） となります。 この f を使って 1個の {0,1,2,3,……,N-1} から {0,1,2,3,……,N-1} {0,f(1),f(2),f(3),……,f(N-1)} {0,f^2(1),f^2(2),f^2(3),……,f^2(N-1)} …… {0,f^<N-2>(1),f^<N-2>(2),f^<N-2>(3),……,f^<N-2>(N-1)} の N-1個に増やすことが出来ます。 こうして作った N(N-1)個の数列は互いにたかだか 1箇所しか重複しません。（これの証明は略） さて問題は置換操作 f が常に存在するかなのですが…… n=3,4 は上記のとおりOKなのですが、それ以降は n=5 は周期 21（≠31） で NG n=6 は周期 63 で OK n=7 は周期 127 で OK n=8 は周期 63（≠255）で NG n=9 は周期 73（≠511）で NG n=10 は周期 889（≠1023）で NG n=11 は周期 1533（≠2047）で NG n=12 は周期 3255（≠4095）で NG n=13 は周期 7905（≠8191）で NG n=14 は周期 11811（≠16383）で NG n=15 は周期 32767 で OK と結果は良くありません。 f を求めるときの漸化式をちょっと変えてやれば n=5 は、漸化式 a(k) = a(k-n) XOR a(k-n+2) で周期 31 n=9 は、漸化式 a(k) = a(k-n) XOR a(k-n+4) で周期 511 n=10 は、漸化式 a(k) = a(k-n) XOR a(k-n+3) で周期 1023 n=11 は、漸化式 a(k) = a(k-n) XOR a(k-n+2) で周期 2047 と適切な f を得られる場合もありますが、 n=8,12,13,14 では漸化式の若干の変更でも f は得られませんでした。 というわけで、N=2^n での一般解（または解の不在の証明）は簡単ではないようです。 |
|
12月10日（火） 11:35:22
41213 |