ｸｲｽﾞ大陸

2-1-3.i≠nの場合
F(i)=min(R(i),max(R(n-1)+R(n)+1,X(i)+1))なので、
F(i)≧k+2であれば、
R(i)≧k+2かつ、max(R(n-1)+R(n),X(i))≧k+1である。
R(n-1)+R(n)≧k+1またはX(i)≧k+1が成り立つ。

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

1≦s≦n-1,s≠iのとき、
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(n-1)+VR(n)+1,VX(s)+1),k+1)
=min(R(s),max(VR(n-1)+R(n)+1,VX(s)+1),k+1)
=min(R(s),k+1)=f(s)

Vf(i)=min(R(i)-1,max(VR(n-1)+R(n)+1,VX(i)+1),k+1)
=k+1=f(i)
となり、すべて一致する。

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

R(i)≧k+2,VX(i)≧kなので、
Vf(i)=min(VR(i),max(VR(n-1)+VR(n)+1,VX(i)+1),k+1)
=min(R(i)-1,max(VR(n-1)+VR(n)+1,VX(i)+1),k+1)
=k+1=f(i)
となり、すべて一致する。

以上で、2-1-3の場合の証明も終わり、2-1が証明された。

残るは2-2の証明のみ。