No. 43≫ No.44 ≫No. 45
いはら
2010/05/11 12:33
続いて2の証明。
任意の自然数kについて、
ｔが1以上k以下のときに成立すると仮定すると、ｔ=k+1のときにも成立することを示す。
つまり、
1≦ｔ≦kのときには、
i番グループのロボットがｔ回目に分かる⇔F(i)=ｔ
が成り立つならば、
2-1.i番グループのロボットがk+1回目に分かる⇒F(i)=k+1
2-2.F(i)=k+1⇒i番グループのロボットはk+1回目に分かる
が成り立つことを示す。
1≦ｔ≦kのときには、
i番グループのロボットがｔ回目に分かる⇔F(i)=ｔ
が成立すると仮定。
2-1.i番グループのロボットがk+1回目に分かるとき、F(i)=k+1になることの証明:
帰納法の仮定から、F(i)≦kであればk回目までに分かるので、F(i)≧k+1である。
F(i)≧k+2であればk+1回目には分からないことを示せば、
k+1回目に分かるときF(i)=k+1となることが証明できる。
k+1回目に分からないということは、iとは異なるあるグループ番号jがあって、
自分がj番グループだと想定したときのk回目までの結果が現実の結果と全く同じになる、
ということである。
sを1以上n以下の自然数とすると、帰納法の仮定により、
F(s)≦kのときは、s番グループのロボットはF(s)回目に分かり、
F(s)≧k+1のときは、s番グループのロボットはk回目までには分からない。
そこで、F(s)≦kのときにはF(s)と同じ値をとり、
F(s)≧k+1のときにはk+1となる関数fを考えてみる。
f(s)=min(F(s),k+1)
とすればよい。
iとjについての2つの関数の値が、リスト中のすべてのグループ番号sについて一致するとき、
自分はi番かj番が判断できないので、k+1回目には分からないということになる。
同じ記号を使うと紛らわしいので、自分がj番グループだと想定したときの、
全グループ数をmとし、
R,X,fの代わりにVR,VX,Vfを使うことにする。
添え字のjをつけるべきであるが、それは省略することにする。
i=mのとき、Vf(i)=min(VR(m-1)+VR(m),max(VR(m),VX(m)+1),k+1)
i≠mのとき、Vf(i)=min(VR(i),max(VR(m-1)+R(m)+1,VX(i)+1),k+1)
である。
次の3つの場合に分けて考える。
2-1-1.i=n,R(n)=1
2-1-2.i=n,R(n)≧2
2-1-3.i≠n
F(i)≧k+2であれば、i番グループのロボットはk+1回目には分からないことを示す。
2-1-1.i=n,R(n)=1の場合
R(n-1)≧0,X(n)≧0,R(n-1)≦X(n)なので、
F(n)=min(R(n-1)+R(n),max(R(n),X(n)+1))=min(R(n-1)+1,max(1,X(n)+1))
=min(R(n-1)+1,X(n)+1)=min(R(n-1),X(n))+1=R(n-1)+1
よって、F(i)≧k+2であれば、R(n-1)≧k+1であり、n-1番グループのロボットは存在する。
R(n-1)+R(n)≧k+2なので、
F(n-1)=min(R(n-1),max(R(n-1)+R(n)+1,X(n-1)+1))≧k+1
であり、n-1番グループのロボットはk回目までに分かっていないことになる。
そこで、j=n-1と想定してみる。
m=n-1,VR(n-1)=R(n-1)+1,VR(n)=0であり、
1≦s≦n-2のときは、VR(s)=R(s)である。
リスト中に現れるグループ番号は1からn-1までなので、
1≦s≦n-1のときに、f(s)=Vf(s)となることを示せばよい。
f(n-1)=k+1
Vf(n-1)=Vf(m)=min(VR(m-1)+VR(m),max(VR(m),VX(m)+1),k+1)
=min(VR(n-2)+VR(n-1),max(VR(n-1),VX(n-1)+1),k+1)
=min(R(n-2)+R(n-1)+1,max(R(n-1)+1,VX(n-1)+1),k+1)
R(n-1)≧k+1なので第一項、第二項ともk+1以上。
よって、Vf(n-1)=k+1=f(n-1)
1≦s≦n-2のとき、
f(s)=min(R(s),max(R(n-1)+R(n)+1,X(s)+1),k+1)
Vf(s)=min(VR(s),max(VR(n-1)+VR(n)+1,VX(s)+1),k+1)
=min(R(s),max(R(n-1)+R(n)+1,VX(s)+1),k+1)
f(s)とVf(s)の式で異なっているのは、X(s)とVX(s)の箇所だけである。
X(s)≠VX(s)となるのは、
どちらかがR(n-1),R(n),VR(n-1),VR(n)のいずれかと等しくなるときに限られる。
R(n-1),R(n),VR(n-1),VR(n)≦R(n-1)+R(n)なので、
その場合は、max(R(n-1)+R(n)+1,X(s)+1)=max(R(n-1)+R(n)+1,VX(s)+1)となり、
f(s)=Vf(s)となる。
以上より、1≦s≦n-1のときにf(s)=Vf(s)が成り立つことが分かった。
よって、i番グループのロボットはk+1回目には分からず、2-1-1の場合が証明された。
続く。
任意の自然数kについて、
ｔが1以上k以下のときに成立すると仮定すると、ｔ=k+1のときにも成立することを示す。
つまり、
1≦ｔ≦kのときには、
i番グループのロボットがｔ回目に分かる⇔F(i)=ｔ
が成り立つならば、
2-1.i番グループのロボットがk+1回目に分かる⇒F(i)=k+1
2-2.F(i)=k+1⇒i番グループのロボットはk+1回目に分かる
が成り立つことを示す。
1≦ｔ≦kのときには、
i番グループのロボットがｔ回目に分かる⇔F(i)=ｔ
が成立すると仮定。
2-1.i番グループのロボットがk+1回目に分かるとき、F(i)=k+1になることの証明:
帰納法の仮定から、F(i)≦kであればk回目までに分かるので、F(i)≧k+1である。
F(i)≧k+2であればk+1回目には分からないことを示せば、
k+1回目に分かるときF(i)=k+1となることが証明できる。
k+1回目に分からないということは、iとは異なるあるグループ番号jがあって、
自分がj番グループだと想定したときのk回目までの結果が現実の結果と全く同じになる、
ということである。
sを1以上n以下の自然数とすると、帰納法の仮定により、
F(s)≦kのときは、s番グループのロボットはF(s)回目に分かり、
F(s)≧k+1のときは、s番グループのロボットはk回目までには分からない。
そこで、F(s)≦kのときにはF(s)と同じ値をとり、
F(s)≧k+1のときにはk+1となる関数fを考えてみる。
f(s)=min(F(s),k+1)
とすればよい。
iとjについての2つの関数の値が、リスト中のすべてのグループ番号sについて一致するとき、
自分はi番かj番が判断できないので、k+1回目には分からないということになる。
同じ記号を使うと紛らわしいので、自分がj番グループだと想定したときの、
全グループ数をmとし、
R,X,fの代わりにVR,VX,Vfを使うことにする。
添え字のjをつけるべきであるが、それは省略することにする。
i=mのとき、Vf(i)=min(VR(m-1)+VR(m),max(VR(m),VX(m)+1),k+1)
i≠mのとき、Vf(i)=min(VR(i),max(VR(m-1)+R(m)+1,VX(i)+1),k+1)
である。
次の3つの場合に分けて考える。
2-1-1.i=n,R(n)=1
2-1-2.i=n,R(n)≧2
2-1-3.i≠n
F(i)≧k+2であれば、i番グループのロボットはk+1回目には分からないことを示す。
2-1-1.i=n,R(n)=1の場合
R(n-1)≧0,X(n)≧0,R(n-1)≦X(n)なので、
F(n)=min(R(n-1)+R(n),max(R(n),X(n)+1))=min(R(n-1)+1,max(1,X(n)+1))
=min(R(n-1)+1,X(n)+1)=min(R(n-1),X(n))+1=R(n-1)+1
よって、F(i)≧k+2であれば、R(n-1)≧k+1であり、n-1番グループのロボットは存在する。
R(n-1)+R(n)≧k+2なので、
F(n-1)=min(R(n-1),max(R(n-1)+R(n)+1,X(n-1)+1))≧k+1
であり、n-1番グループのロボットはk回目までに分かっていないことになる。
そこで、j=n-1と想定してみる。
m=n-1,VR(n-1)=R(n-1)+1,VR(n)=0であり、
1≦s≦n-2のときは、VR(s)=R(s)である。
リスト中に現れるグループ番号は1からn-1までなので、
1≦s≦n-1のときに、f(s)=Vf(s)となることを示せばよい。
f(n-1)=k+1
Vf(n-1)=Vf(m)=min(VR(m-1)+VR(m),max(VR(m),VX(m)+1),k+1)
=min(VR(n-2)+VR(n-1),max(VR(n-1),VX(n-1)+1),k+1)
=min(R(n-2)+R(n-1)+1,max(R(n-1)+1,VX(n-1)+1),k+1)
R(n-1)≧k+1なので第一項、第二項ともk+1以上。
よって、Vf(n-1)=k+1=f(n-1)
1≦s≦n-2のとき、
f(s)=min(R(s),max(R(n-1)+R(n)+1,X(s)+1),k+1)
Vf(s)=min(VR(s),max(VR(n-1)+VR(n)+1,VX(s)+1),k+1)
=min(R(s),max(R(n-1)+R(n)+1,VX(s)+1),k+1)
f(s)とVf(s)の式で異なっているのは、X(s)とVX(s)の箇所だけである。
X(s)≠VX(s)となるのは、
どちらかがR(n-1),R(n),VR(n-1),VR(n)のいずれかと等しくなるときに限られる。
R(n-1),R(n),VR(n-1),VR(n)≦R(n-1)+R(n)なので、
その場合は、max(R(n-1)+R(n)+1,X(s)+1)=max(R(n-1)+R(n)+1,VX(s)+1)となり、
f(s)=Vf(s)となる。
以上より、1≦s≦n-1のときにf(s)=Vf(s)が成り立つことが分かった。
よって、i番グループのロボットはk+1回目には分からず、2-1-1の場合が証明された。
続く。