ｸｲｽﾞ大陸

それでは、
「各グループのロボットが何回目に分かるのかは一意に決まる」
ことを証明しておきます。
（あの証明にほとんど含まれているのですが）

グループ数、各グループの台数が与えられたとき、
任意の自然数ｔについて、
ｔ回目にどのロボットが分かるかは一意に決まる
ということを証明すれば十分です。

ｔについての数学的帰納法で証明します。

ｔ=1のときに成り立つことは明らかです。

ｔが1以上k以下の自然数のときには成り立つと仮定します。
k回目終了時点でまだ分かっていないロボットについて考えます。
自分の番号の候補は有限個です。
候補の一つがj番だとして、自分の番号がj番だと想定すると、
グループ数、各グループの台数は確定します。
すると、帰納法の仮定により、1回目からk回目までの各回において、
その回に分かるロボットは一意に決まります。
実際の結果と比較して、一致しなければ、自分はj番ではないと分かります。
一致した場合は、自分がj番ではないと論理的に推論することは不可能です。
従って、一致する場合が2つ以上ある場合には
自分の番号を推論することはできません。
一致する場合が少なくとも一つあることは明らかですので、
一致する場合がただ一つだけのときのみ、自分の番号が推論できることになります。
各ロボットは完璧な推論をすることになっていますので、
k+1回目にも自分の番号が分かるロボットは一意に決まります。
証明終わり


各ロボットは上記の方法で機械的に判断を下したという想定で問題を作りました。
どんな推論を行おうと、完璧な推論であれば、
この方法による結論と同じになるはずです。