ｸｲｽﾞ大陸

F(i)=ｔは、i番グループのロボットがｔ回目に分かるための必要十分条件。

これを証明するにあたり、まずはF(i)の取り得る値を考える。
関数R,Xは整数値しかとらないので、F(i)が整数値となることは明らか。
R(n)≧1なのでR(n-1)+R(n)≧1,max(R(n),X(n)+1)≧1であり、F(n)≧1
i≠nのとき、R(i)≧1なので同様にしてF(i)≧1
つまり、F(i)は1以上の整数である。
よって、すべての自然数ｔについて証明すればよい。

ｔについての数学的帰納法で証明する。
1.ｔ=1のときに成立することを示す。
2.1以上k以下のｔについて成立すると仮定すると、ｔ=k+1のときにも成立することを示す。
これができれば、すべての自然数ｔについて成立するという証明になる。

1.ｔ=1のとき
i番グループのロボットが1回目に分かる⇒F(i)=1、の証明：
i番グループのロボットが1回目に分かるとする。
リストに1番からある番号までの連続するグループ番号が存在している場合は、
1番からリスト中の最大番号+1番までが、自分のグループ番号の候補になり、
特定できない。
R(i)≧2のときはリストに1番からn番までのすべての番号が現れるので、R(i)=1。
i=n≧2の場合、R(i)=1であっても、リストには1番からn-1番までのすべての番号が現れる。
よって、i=nの場合はn=1でなくてはいけない。
この場合、全ロボット台数は1となりリストには何も記載されず、自分は1番だと分かる。
このとき、F(i)=min(R(n-1)+R(n),max(R(n),X(n)+1))=min(1,max(1,1))=1

i≠nの場合、R(i)=1,R(n)≧1,X(i)≧R(n)≧1なので、
F(i)=min(R(i),max(R(n-1)+R(n)+1,X(i)+1))=min(1,max(R(n-1)+R(n)+1,X(i)+1))=1
となり、証明された。

F(i)=1⇒i番グループのロボットは1回目に分かる、ことの証明：
F(i)=1とする。
i=nであれば、F(i)=min(R(n-1)+R(n),max(R(n),X(n)+1))
すると、R(n-1)+R(n)=1またはmax(R(n),X(n)+1)=1が成り立つ。
R(n-1)+R(n)=1となるのは、n=1,R(n)=1のときだけ。
これは全ロボット台数が1ということなので、1回目に分かる。
max(R(n),X(n)+1)=1のときは、R(n)=1,X(n)=0なのでn=1となり同じことになる。

i≠nであれば、min(R(i),max(R(n-1)+R(n)+1,X(i)+1))=1。
R(i)=1またはmax(R(n-1)+R(n)+1,X(i)+1)=1が成り立つ。
R(i)=1であれば、リスト中にi番が現れずi+1番が存在するので、
自分がi番だということが1回目に分かる。
max(R(n-1)+R(n)+1,X(i)+1)=1のとき、
R(n-1)+R(n)≦1かつ、X(i)≦1。
これを満たすのは、R(n)=1,n=1のときだけなので、1回目に分かることになる。

以上より、ｔ=1のときには証明された。

続く。