ｸｲｽﾞ大陸

2-1-2.i=n,R(n)≧2の場合
F(n)≧k+2であれば、
R(n-1)+R(n)≧k+2かつ、max(R(n),X(n)+1)≧k+2である。
よって、R(n)≧k+2またはX(n)≧k+1である。

R(n)≧k+2のとき、
j=n+1と想定してみる。
m=n+1,VR(n)=R(n)-1,VR(n+1)=1であり、
1≦s≦n-1のときは、VR(s)=R(s)である。
リスト中に現れるグループ番号は1からnまでなので、
1≦s≦nのときに、f(s)=Vf(s)となることを示せばよい。
n番グループはk回目までに分かってないので、f(n)=k+1
Vf(n)=min(VR(n),max(VR(m-1)+VR(m)+1,VX(n)+1),k+1)
=min(R(n)-1,max(VR(n)+VR(n+1)+1,VX(n)+1),k+1)
=min(R(n)-1,max(R(n)-1+1+1,VX(n)+1),k+1)
=min(R(n)-1,max(R(n)+1,VX(n)+1),k+1)
R(n)≧k+2なので、これはk+1に等しく、f(n)に一致する。
1≦s≦n-1のとき、
R(n)≧k+2なので、
f(s)=min(R(s),max(R(n-1)+R(n)+1,X(s)+1),k+1)=min(R(s),k+1)
Vf(s)=min(VR(s),max(VR(m-1)+VR(m)+1,VX(s)+1,k+1)
=min(R(s),max(R(n)+1,VX(s)+1),k+1)
=min(R(s),k+1)=f(s)
となり、一致する。

X(n)≧k+1のとき、
1以上n-1以下のあるjがあって、R(j)≧k+1が成り立つ。
j番グループだと想定すると、
m=n,VR(n)=R(n)-1,VR(j)=R(j)+1であり、
1≦s≦n-1,s≠jのときには、VR(s)=R(s)である。
リスト中に現れるグループ番号は1からnまでなので、
1≦s≦nのときに、f(s)=Vf(s)となることを示せばよい。
Vf(n)=Vf(m)=min(VR(m-1)+VR(m),max(VR(m),VX(m)+1),k+1)
=min(R(n-1)+R(n)-1,max(R(n)-1,VX(n)+1),k+1)
R(n-1)+R(n)≧k+2,VX(n)≧VR(j)=R(j)+1≧k+2なので、
この値はk+1に等しく、f(n)に一致する。
1≦s≦n,s≠jのとき、
R(n-1)+R(n)≧k+2なので、
f(s)=min(R(s),max(R(n-1)+R(n)+1,X(s)+1),k+1)
=min(R(s),k+1)
VR(n-1)+R(n)≧R(n-1)+R(n)-1≧k+1なので、
Vf(s)=min(VR(s),max(VR(m-1)+VR(m)+1,VX(s)+1),k+1)
=min(R(s),max(VR(n-1)+R(n),VX(s)+1),k+1)
=min(R(s),k+1)=f(s)

f(j)=min(R(j),k+1)=k+1
Vf(j)=min(R(j)+1,k+1)=k+1
となり、すべて一致する。

以上より、i番グループのロボットはk+1回目には分からず、2-1-2の場合の証明終了。

続く。