No. 46≫ No.47 ≫No. 48
いはら
2010/05/12 12:41
2-2.F(i)=k+1のとき、i番グループのロボットはk+1回目に分かることの証明:
F(i)=k+1とする。
i番グループのロボットがｔ回目に分かるとして、
ｔ≦kであれば、F(i)=ｔである(帰納法の仮定)。
k回目までに分かる場合はF(i)≦kなので、k回目までには分からなかったことになる。
よってk+1回目までに分かったことを示せばよい。
2-2-1.i=n
2-2-2.i≠n
の2つの場合に分けて調べる。
2-2-1.i=nの場合
F(i)=min(R(n-1)+R(n),max(R(n),X(n)+1))
F(i)=R(n-1)+R(n)またはF(i)=max(R(n),X(n)+1)のどちらかは成り立つ。
F(i)=R(n-1)+R(n)のとき
R(n-1)+R(n)=k+1であり、R(n)≧1なのでR(n-1)≦k
よってn-1番のロボットはk回目までに分かっており、自分はn-1番ではないと分かっている。
R(n)≠1であれば、リストにn番が存在している。
自分がn番グループでないとすると、
R(n-1)+R(n)=kとなるので、n番はk回目までに分かったことになり矛盾。
R(n)=1であれば、
R(n-1)+R(n)=k+1より、R(n-1)=k
よって、n-1番グループはk回目までに分かっている。
リストに現れている番号は1からn-1までなので、
自分の番号の候補は1からnまで。
n-1番は既に分かっているので自分はn-1番ではない。
n≦2であれば、自分はn番だと分かる。
n≧3のとき、自分は1からn-2番のいずれか。
自分がn番でないj番だと想定すると、
m=n-1,VR(j)=R(j)+1,VR(m)=R(n-1)
1≦s≦n-2,s≠jのときは、VR(s)=R(s)
R(n-1)≧k,R(n-2)+R(n-1)≧k+1なので、
Vf(n-1)=Vf(m)=min(VR(m-1)+VR(m),max(VR(m),VX(m)+1),k+1)
=min(R(n-2)+R(n-1),max(R(n-1),VX(n-1)+1),k+1)
=k+1
となり、n-1番はk回目までに分からなかったことになり矛盾。
よって、自分はn番だと分かる。
F(i)=max(R(n),X(n)+1)=k+1のとき
1以上n-1以下のsについて、R(s)≦kである。
F(s)=min(R(s),max(R(n-1)+R(n)+1,X(i)+1))≦kとなるので、
1からn-1番はk回目までに分かっている。
さらに、R(n)≦k+1も成り立つ。
R(n)=1であれば、自分の番号の候補は1からnなのでn番だと分かる。
R(n)≧2のとき、候補はnまたはn+1。
n+1番だと想定すると、
Vf(n)=min(VR(n),max(VR(n)+VR(n+1)+1,VX(n)+1),k+1)
=min(R(n)-1,max(VR(n)+VR(n+1)+1,VX(n)+1),k+1)≦k
となるので、n番はk回目までに分かっている。
よって、自分はn+1番ではなくn番だと分かる。
以上より、i=nの場合にはk+1回目までに分かることが証明された。
2-2-2.i≠nの場合
F(i)=min(R(i),max(R(n-1)+R(n)+1,X(i)+1))=k+1
F(i)=R(i)またはF(i)=max(R(n-1)+R(n),X(i))+1のどちらかは成り立つ。
F(i)=R(i)=k+1のとき
自分がi番でないと想定すると、
Vf(i)=min(VR(i),max(VR(m-1)+VR(m)+1,VX(i)+1),k+1)
≦VR(i)=R(i)-1=k
となり、i番がk回目までに分かったことになってしまう。
よって、自分はi番だと分かる。
F(i)=max(R(n-1)+R(n),X(i))+1=k+1のとき
max(R(n-1)+R(n),X(i))=kである。
R(n-1)+R(n)≦kなので、n番はk回目までに分かっている。
1≦s≦n-1,s≠jのとき、R(s)≦kなので、s番もk回目までに分かっている。
よって、自分はi番またはn+1番でしかあり得ない。
n+1番だと想定すると、
Vf(i)=min(R(i)-1,max(VR(n)+VR(n+1)+1,VX(i)+1),k+1)≦R(i)-1=k
となり、i番がk回目までに分かったことになってしまう。
よって自分はi番だと分かる。
これでi≠nの場合にもk+1回目までに分かることになり、2-2が証明された。
以上で2の証明が終わり、
任意の自然数ｔについて成立することが証明された。
証明終わり
F(i)=k+1とする。
i番グループのロボットがｔ回目に分かるとして、
ｔ≦kであれば、F(i)=ｔである(帰納法の仮定)。
k回目までに分かる場合はF(i)≦kなので、k回目までには分からなかったことになる。
よってk+1回目までに分かったことを示せばよい。
2-2-1.i=n
2-2-2.i≠n
の2つの場合に分けて調べる。
2-2-1.i=nの場合
F(i)=min(R(n-1)+R(n),max(R(n),X(n)+1))
F(i)=R(n-1)+R(n)またはF(i)=max(R(n),X(n)+1)のどちらかは成り立つ。
F(i)=R(n-1)+R(n)のとき
R(n-1)+R(n)=k+1であり、R(n)≧1なのでR(n-1)≦k
よってn-1番のロボットはk回目までに分かっており、自分はn-1番ではないと分かっている。
R(n)≠1であれば、リストにn番が存在している。
自分がn番グループでないとすると、
R(n-1)+R(n)=kとなるので、n番はk回目までに分かったことになり矛盾。
R(n)=1であれば、
R(n-1)+R(n)=k+1より、R(n-1)=k
よって、n-1番グループはk回目までに分かっている。
リストに現れている番号は1からn-1までなので、
自分の番号の候補は1からnまで。
n-1番は既に分かっているので自分はn-1番ではない。
n≦2であれば、自分はn番だと分かる。
n≧3のとき、自分は1からn-2番のいずれか。
自分がn番でないj番だと想定すると、
m=n-1,VR(j)=R(j)+1,VR(m)=R(n-1)
1≦s≦n-2,s≠jのときは、VR(s)=R(s)
R(n-1)≧k,R(n-2)+R(n-1)≧k+1なので、
Vf(n-1)=Vf(m)=min(VR(m-1)+VR(m),max(VR(m),VX(m)+1),k+1)
=min(R(n-2)+R(n-1),max(R(n-1),VX(n-1)+1),k+1)
=k+1
となり、n-1番はk回目までに分からなかったことになり矛盾。
よって、自分はn番だと分かる。
F(i)=max(R(n),X(n)+1)=k+1のとき
1以上n-1以下のsについて、R(s)≦kである。
F(s)=min(R(s),max(R(n-1)+R(n)+1,X(i)+1))≦kとなるので、
1からn-1番はk回目までに分かっている。
さらに、R(n)≦k+1も成り立つ。
R(n)=1であれば、自分の番号の候補は1からnなのでn番だと分かる。
R(n)≧2のとき、候補はnまたはn+1。
n+1番だと想定すると、
Vf(n)=min(VR(n),max(VR(n)+VR(n+1)+1,VX(n)+1),k+1)
=min(R(n)-1,max(VR(n)+VR(n+1)+1,VX(n)+1),k+1)≦k
となるので、n番はk回目までに分かっている。
よって、自分はn+1番ではなくn番だと分かる。
以上より、i=nの場合にはk+1回目までに分かることが証明された。
2-2-2.i≠nの場合
F(i)=min(R(i),max(R(n-1)+R(n)+1,X(i)+1))=k+1
F(i)=R(i)またはF(i)=max(R(n-1)+R(n),X(i))+1のどちらかは成り立つ。
F(i)=R(i)=k+1のとき
自分がi番でないと想定すると、
Vf(i)=min(VR(i),max(VR(m-1)+VR(m)+1,VX(i)+1),k+1)
≦VR(i)=R(i)-1=k
となり、i番がk回目までに分かったことになってしまう。
よって、自分はi番だと分かる。
F(i)=max(R(n-1)+R(n),X(i))+1=k+1のとき
max(R(n-1)+R(n),X(i))=kである。
R(n-1)+R(n)≦kなので、n番はk回目までに分かっている。
1≦s≦n-1,s≠jのとき、R(s)≦kなので、s番もk回目までに分かっている。
よって、自分はi番またはn+1番でしかあり得ない。
n+1番だと想定すると、
Vf(i)=min(R(i)-1,max(VR(n)+VR(n+1)+1,VX(i)+1),k+1)≦R(i)-1=k
となり、i番がk回目までに分かったことになってしまう。
よって自分はi番だと分かる。
これでi≠nの場合にもk+1回目までに分かることになり、2-2が証明された。
以上で2の証明が終わり、
任意の自然数ｔについて成立することが証明された。
証明終わり