◆宮城県 アンパンマン さんからの解答。
【問題１】
帰納法で証明します。
n=1, V(1,0).V(1,1) = 1-1=0
n=kまで内積が0と仮定すると
n=k+1の場合も成り立つことを証明します。
Case1, 0≦i,j＜2k; i≠j
V(k+1,i).V(k+1,j)=2V(k,i).V(k,j)=0
Case2, 0≦i＜2k; j≧2k
V(k+1,i).V(k+1,j)
=V(k,i).V(k,j-2k)-V(k,i).V(k,j-2k)
=0
Case3, i,j≧2k ; i≠j
V(k+1,i).V(k+1,j)=2V(k,i-2k).V(k,j-2k)=0
すなわちn=k+1の場合も成り立つ。
【問題２】
ｎの場合の順番は(a(n,0),a(n,1),...,a(n,2n-1))とします。
ここでa(n,i)は V(n,k)が1 から -1 あるいは -1 から 1 に変わる回数がiになるようなkです。
(a(n+1,0),a(n+1,1),...,a(n+1,2n+1-1))と
(a(n,0),a(n,1),...,a(n,2n-1))との関係は
i＜2n-1,
a(n+1,4i)=a(n,2i)
a(n+1,4i+1)=a(n,2i)+2n
a(n+1,4i+2)=a(n,2i+1)+2n
a(n+1,4i+3)=a(n,2i+1)
a(1,0)=0,a(1,1)=1。
証明（帰納法）
P(n,i)= V(n,i)が1 から -1 あるいは -1 から 1 に変わる回数と定義します。
k=1; P(1,1)-P(1,0)=1-0=1。
k=n までは成り立つ
(つまりP(n,a(n,i+1))-P(n,a(n,i))=1)と仮定すると
k=n+1;i≦2n-1-1
P(n+1,a(n+1,4i+1))-P(n+1,a(n+1,4i))
=P(n+1,a(n,2i)+2n)-P(n+1,a(n,2i))
=2P(n,a(n,2i))+1-2P(n,a(n,2i))
=1
P(n+1,a(n+1,4i+2))-P(n+1,a(n+1,4i+1))
=P(n+1,a(n,2i+1)+2n)-P(n+1,a(n,2i)+2n)
=2P(n,a(n,2i+1))-(2P(n,a(n,2i))+1)
=2(P(n,a(n,2i))+1)-(2P(n,a(n,2i))+1)
=1
P(n+1,a(n+1,4i+3))-P(n+1,a(n+1,4i+2))
=P(n+1,a(n,2i+1))-P(n+1,a(n,2i+1)+2n)
=2P(n,a(n,2i+1))+1-2P(n,a(n,2i+1))
=1
P(n+1,a(n+1,4i+4))-P(n+1,a(n+1,4i+3))
=P(n+1,a(n,2i+2))-P(n+1,a(n,2i+1))
=2(P(n,a(n,2i+1))+1)-(2P(n,a(n,2i+1))+1)
=1
ｋ=n+1で成り立つ。
さらに、帰納法で
a(n+1,i)=2a(n,i) ; i＜2n
a(n+1,i)=2a(n,2n+1-i-1)+1 ; 2n≦i＜2n+1
を証明できる。
証明
k=1の場合は
a(2,0)=0=a(1,0)
a(2,1)=2=2a(1,1)
a(2,2)=3=2a(1,3-2)+1
a(2,3)=1=2a(1,3-3)+1
k=nまで成り立つと仮定します。
case1; i＜2n-2,
a(n+1,4i)
=a(n,2i)
=2a(n-1,2i)
=2a(n,4i)
a(n+1,4i+1)
=a(n,2i)+2n
=2a(n-1,2i)+2n
=2[a(n-1,2i)+2n-1]
=2a(n,4i+1)
a(n+1,4i+2)
=a(n,2i+1)+2n
=2[a(n-1,2i+1)+2n-1]
=2a(n,4i+2)
a(n+1,4i+3)
=a(n,2i+1)
=2a(n-1,2i+1)
=2a(n,4i+3)
case2; 2n-2≦i＜2n-1,
a(n+1,4i)=a(n,2i)
=2a(n-1,2n-2i-1)+1
=2a(n-1,2(2n-1-i-1)+1)+1
=2a(n,4(2n-1-i-1)+3)+1
=2a(n,2n+1-4i-1)+1
a(n+1,4i+1)
=a(n,2i)+2n
=2a(n-1,2n-2i-1)+2n+1
=2[a(n-1,2(2n-1-i-1)+1)+2n-1]+1
=2a(n,4(2n-1-i-1)+2)+1
=2a(n,2n+1-4i-2)+1
a(n+1,4i+2)
=a(n,2i+1)+2n
=2[a(n-1,2(2n-1-i-1))+2n-1]+1
=2a(n,4(2n-1-i-1)+1)+1
=2a(n,2n+1-4i-3)+1
a(n+1,4i+3)
=a(n,2i+1)
=2a(n-1,2(2n-1-i-1))+1
=2a(n,4(2n-1-i-1))+1
=2a(n,2n+1-4i-4)+1
ゆえにk=n+1の場合も成り立つ。
すなわち、下記の並べ替えで条件を満たすような置換が得られます。
a(n+1,i)=2a(n,i) ; i＜2n
a(n+1,i)=2a(n,2n+1-i-1)+1 ; 2n≦i＜2n+1