Q.100 「孤独な田中」

どちゃ楽

Q.100 ☆7 [suiso_728660様]

100人の田中が同じスタート地から体育館を永遠に周回する。田中$n$ $(1\le n\le 100, n\in\mathbb{N})$ が体育館を1周するのにかかる時間は $n$ とする。このとき,どの田中に,自分から半周離れた場所に他の99人の田中が位置するような孤独な瞬間が訪れるか。

この問題のツイート: https://twitter.com/so_easy_math/status/961425394472595456

解答

田中$n$は一周に時間$n$を要するので,体育館の一周を$1$とし,田中$n$の速さは$\dfrac{1}{n}$ としてよい。このとき,スタートの時刻を$t=0$として,時刻$t=t_1$のときの田中$n$が移動した距離は $\dfrac{t_1}{n}$ である。

体育館のスタート地を原点とし,田中たちの進む方向に$x$軸を取り,この軸上で $x=a,1+a$を表す点は同一であるとみなせば,$\{a\}$ で実数$a$の小数部分を表すとして,時刻$t=t_1$のときの田中$n$の位置は $x=\{\dfrac{t_1}{n}\}$ である。

孤独な田中の番号を$m $ とする。この田中$m$を取り除き,田中$1,2,\cdots,m - 1,m+1,\cdots,100$ の99人で考える。まず,次の事柄を示す。

ある時刻において,この99人はある一つの地点で集まり,その地点はスタート地点に限る。

(証明)

田中$1$と$2$が集合する時刻$t=t'$の条件を考えると,$\{t'\}=\{\dfrac{t'}{2}\}$ であるから,$t'$ と $\dfrac{t'}{2}$ の小数部分が一致する。これは $t' -\dfrac{t'}{2}=\dfrac{t'}{2}$ が整数であることに同値で,すなわち$t'$は2の倍数である。また,このとき田中$1,2$はともにスタート地点にいる。したがって田中$1,2$はともに同時刻に集合することがあり,かつその地点がスタート地点($x=0$)に限る。

同様に田中$4$と$8$が集合する時刻$t=t'$の条件を考えると,$\dfrac{t'}{4}$ と $\dfrac{t'}{8}$ の小数部分が一致するから,$\dfrac{t'}{4}-\dfrac{t'}{8}=\dfrac{t'}{8}$ は整数であるため,$t'$は8の倍数である。このとき田中$4,8$はスタート地点にいる。同様に,田中$4,8$は同時刻に集合することがあり,かつその地点がスタート地点($x=0$)に限る。

また,田中$n$は 時刻$t=n\times j$ ($j$は0以上の整数) のときに限りスタート地点に戻ってく るので,$m $が何であっても,99人の田中$1,2,\cdots,m - 1,m+1,\cdots,100$ は 時刻$t=\mbox{lcm}(1,2,\cdots,m - 1,m+1,\cdots,100)\times j$ においてスタート地点に集合する。逆に,この99人がスタート地点に集合することがあれば,田中$1,2$ が2人が集まっているか, 田中$4,8$の2人が集まっているかの少なくとも一方が成立する。田中$1,2$の2人も,田中$3,4$の2人も,先に示したように,どちらもスタート地点でのみ出会うことかできるから,この99人が出会う地点はスタート地点に限る。(証明終)

これにより,少なくとも99人が同時に集合するときは必ずスタート地点で集合していることが言える。

$L(m)=\mbox{lcm}(1,2,\cdots,m - 1,m+1,\cdots,100)$ とおいて,ある非負整数$j$が存在して 時刻$t=L(m)j$のときに田中$m$がスタート地点から真反対のところ($x=\dfrac{1}{2}$)にいる。

時刻$t=L(m)j$のとき,田中$m$の位置は $\{\dfrac{L(m)j}{m}\}$ なので

$\{\dfrac{L(m)j}{m}\}=\dfrac{1}{2}$ である。これは, $\dfrac{L(m)j}{m}-\dfrac{1}{2}= \dfrac{2L(m)j-m}{2m} $ が整数であることに同値で,そのような$j$が存在するような$m$を探せば良い。

$m=64$ のとき,$j$が存在することを示す。$j$が奇数であるとき,$\dfrac{2L(m)j-m}{2m} = \dfrac{2L(64)j-64}{128}$ が整数となることを言えば十分である。1から100までの整数で,64を除いた数は2で高々5回しか割り切れない。したがって $L(64)$は32で割り切れるが64で割り切れない。よって,$L(64)=32l$ ($l$は奇数) と置くことができ,$\dfrac{64lj-64}{128}=\dfrac{lj-1}{2}$は整数である。($l,j$が奇数であるから分子は偶数であるため)

よって田中64は題意を満たす。逆に $m\neq 64$ ならば,$m$は高々2で6回しか割れず,$m=2^{a}b$ ($0\le a\le 6$, $b$は奇数)と表せるが,一方で$L(m)$は64の倍数であるため,$L(m)=64c$とすると

$2L(m)j-m=2^{7}cj-2^{a}b=2^{a}(2^{7-a}cj-b)$ であり,$7-a\ge 1$より,$j$をどのように取ってもどのように取っても括弧内の数は奇数であるから,$\dfrac{2L(m)j-m}{2m}=\dfrac{2^{a}(2^{7-a}cj-b)}{2^{a+1}b}=\dfrac{2^{7-a}cj-b}{2b}$ は明らかに整数でない。よって,田中64以外は題意を満たさない。

以上より,田中64が孤立する。

コメント

面白い設定の問題ですね。数オリ予選の後半とかに出てきそう。数式で表現することが重要な問題ですね。