ゆきくらげ自作問001 "タイムパラドックスを回避せよ"

問.
f:id:yukikurage:20200820144052p:plain:w200
　このような感じの16個の頂点とそれを結ぶ辺でできた図形がある。直角っぽいところはすべて直角としてよい。一辺の長さは1である。さて、ご存じのように太郎君という存在がいる。この問題において太郎君は次の規則に従って動く。
(Ⅰ)太郎君は単位時間あたり1の長さを進み、辺の途中で後戻りするようなことはない。
(Ⅱ)太郎君は頂点に着くたび直角に曲がる
　下記の文章の解は存在する。nに入ると考えられるもののうち最大の自然数を求めよ。またnがその値の時、下記の文章の解をかけ。
　「太郎君はついにタイムマシンを完成させた。それを使って遊んでいたところ、なんと同時期に太郎君がn人存在することになってしまった。タイムパラドックスを防ぐには太郎君たちが出会ってはならない。
　時刻t=0に、太郎君たちはそれぞれ異なる頂点にいて、ここで太郎君たちがそれぞれある方向に歩き始めるとすれば、その後太郎君たちが規則に従いつつどんな動きをして、どんなに時間がたったとしても頂点、辺上いずれの場所でも出会わないようにできる。最初に太郎君たちががいる場所と一人ひとりが歩き始める方向の例をかけ。」

※この問題の解の例(※当然間違ってます。)
最大のnは2
f:id:yukikurage:20200820144116p:plain:w200

雑談

　自作問題を作ってみました。すぐ下にヒントと解答があります。
　解く分には特別な知識などは全然必要ありません（たぶん）。問題文を言い換えれば小学生でも解けるかも。その点「自作問」というよりは「自作クイズ」なのかもしれません。
　問題不備があるかも。塾の授業中の思いつきなので……（保険）

ヒント

　ヒントです。解の例は間違っているといいましたが、この状況だと太郎君2人はぶつかりません。nの最大値が間違っているのです。

解法

　考え方を書いていきます。
　まず、思うのは条件(Ⅱ)が厄介であるということです。普通の人類はこんな動きはしないはずです。なのでまず(Ⅱ)を排除して簡単な問題にしてから解いてみます。あと「辺上で出会わない」というのも厄介です。なのでとりあえず(Ⅰ)、「頂点で出会わない」のもと問題を解いてみます。これはよくある問題（よくあるのか？）であり、
f:id:yukikurage:20200820144849p:plain:w200
　こんな感じで頂点をAとBに分けます。するとt=kでAのどれかにいるとするとt=k+1ではBのどれかにいるはずです。逆にt=kでBにいるならt=k+1でAです。こう考えていくと最初にいた場所がAのどこかなら、tが偶数の時A、tが奇数の時Bのどこかになり、最初にBにいたら逆です。したがって最初にAのどこかとBのどこかに2人いればどんなに好きに動いても頂点で出会うことはないとわかります。逆に3人以上いると必ずAとBのどちらかに2人以上が属することとなり、それらの人がぶつかるような場合が存在します(※)。
　※(実際これを言いきるにはちょっと早いです。厳密にいうならこうです。例えば太郎Pと太郎QがどちらもAに属する頂点にいたとします。太郎Pは2単位時間周期で同じ頂点を行ったり来たりすればtが偶数の時は初めにいた場所にいるはずです。太郎Qは、すべての頂点がつながっているので太郎Pが初めにいた場所まで行けます。太郎Qがその場所に着く時は、そこがAに属することよりtが偶数の時であり、この時太郎Pは同じ頂点にいます。)
　ただしこの場合辺上ではぶつかることが容易に想像されます。まあこの際どうでもいいでしょう。(別の問題なので)
　さて、これを念頭に踏まえつつ今度は問題の解答に入っていきます。基本的には同じ考え方です。冗長になってますが簡単に言うとループさせてるだけです。条件(Ⅱ)を追加することで4つの集合を巡回するように設定でき、うまく辺の途中で会うことも回避できます。

解答

以下、 $n\,mod\,r$ をnをrで割った余りとする。
f:id:yukikurage:20200820211736p:plain:w200
　このように頂点を集合 $S_0, S_1,S_2,S_3$ に分ける。ここで太郎君と同様の規則で動く点Pについて考えたい。点Pが時刻 $t=n$ (nは非負整数)にいる頂点を $P(n)$ と表すとする。
　ここでk、iを非負整数として
$P(k)\in S_{(i+k)\,mod\,4}$ かつ $P(k+1)\in S_{(i+k+1)\,mod\,4}$
　ならば図より
$P(k+2)\in S_{(i+k+2)\,mod\,4}$ )」
　である。( $(i+k)\,mod\,4, (i+k+1)\,mod\,4, (i+k+2)\,mod\,4$ の組み合わせは4通りしかない。それぞれについて確かめればよい)
　(要は $S_1→S_2$ ときたら次は $S_3$ だし、 $S_3→S_0$ ときたら次は $S_1$ だという感じ)
　したがって
$P(0)\in S_{i\,mod\,4}, P(1)\in S_{(i+1)\,mod\,4}$
　とすれば帰納的に(すごくあいまい。許して)
$P(k)\in S_{(i+k)\,mod\,4}$
　である。
　ここで太郎君0, 1, 2, 3がいるとして、太郎君jが時刻t=nにいる頂点を $P(j, n)$ と表すこととする。
$P(j, 0)\in S_j, P(j, 1)\in S_{(j+1)\,mod\,4}$ 　……①
　とすれば先ほどの点Pは太郎君と同じ規則で動いていることから
$P(j, k)\in S_{(j+k)\,mod\,4}$ である　……②
　kが等しいときj=0, 1, 2, 3 についてP(j, k)はすべて異なる集合に属する。したがって太郎君たちがぶつかることはない。
　さらに移動中について考える。
　頂点 $P(j, k)$ から $P(j, k+1)$ への移動の際、太郎君j (j = 0, 1, 2, 3) について、それぞれ集合 $S_{(j+k)\,mod\,4}$ に含まれる頂点から集合 $S_{(j+k+1)\,mod\,4}$ に含まれる頂点に移動する辺上にいる。図よりこれらの辺は同一でない。よってnの最大は4以上。

　次に太郎君が5人以上の時について考える。
　太郎君0, 1, 2, 3, 4がいるとする。鳩の巣原理から $P(a,0)\in S_c$ かつ $P(b,0)\in S_c$ となるa, b( $1\leq a, b\leq 4$ )が存在する。ここで太郎君aが1つの小さな四角形を単位時間4周期で回ると $t=k (k\,mod\,4 = 0)$ のときP(a,0)にいることになる。
　すべての頂点がつながっていることから太郎君bは頂点P(a,0)にたどり着ける。このとき $P(a,0)\in S_c$ 、および②より時刻 $t=k (k\,mod\,4 = 0)$ を満たすので太郎君aもその頂点にいることからぶつかってしまうことになる。