OMCE011(F)

　正の整数 $n$ に対して，$\mathrm{mod} \ n$ で問題文の条件を満たすような移動を $n^2-1$ 回したときに $P$ がいる可能性のある点の個数を $A_n$ で表す．求めるのは $A_{50}$ の値である．
　一辺 $n$ のマス目で正方形を作り，その対辺どうしをつないでトーラスを作る．このとき，問題の条件を満たす経路とはすなわちその $n^2$ 個のマスをちょうど $1$ 度ずつ通るような経路である．経路長の $\mathrm{mod} \ n$ を考えれば，$un+v$ 回 $(u$ は非負整数，$0\leq v \leq n-1)$ の操作を終わらせたあとに $P$ がいるべきマスは図１$(n=7$ の場合$)$ のように塗り分けたマスのうち $v$ と書き込まれた場所のどこかであり，特にすべての移動が終わったあとにいるべきマスは $n-1$ が書かれたマスである．

　さて，以下 $0$ が書かれたマス $n$ 個を総称してスタートマス，$n-1$ が書かれたマス $n$ 個を総称してゴールマスと呼ぶことにする．このとき，$P$ は $n^2-1$ 回の移動の中で $n$ 回スタートマスからゴールマスへの移動 $($経路長 $n-1)$ をし，また $n-1$ 回ゴールマスからスタートマスへの移動 $($経路長 $1)$ をすることになる．スタートマス，ゴールマスを除いた $n(n-2)$ 個のマス目を前者の移動ですべて網羅しなければならないことから，前者の移動の仕方は $n$ 回すべてにおいて合同でなければならないことがわかる（これは経路中で $P$ が曲がる部分に着目すると示すことができる）．
　ここで，$P$ が最終的にいるマス目の $x$ 座標はすなわち，$P$ が右に動いた回数である．この動いた回数は，$0$ 以上 $n$ 未満の整数 $k,l$ を用いて $kn+l$ と一意的に表せるため，以下 $P$ が右に動いた回数を $(k,l)$ の形で表すこととする．このとき，$k$ の値はスタートマスからゴールマスへの各移動で右に何マス動いたかを示すものであり，$l$ の値はゴールマスからスタートマスへの計 $n-1$ 回の移動のうち何回右に動いたかを示すものである．
　この $k,l$ の値が一定ならば，スタートマスからゴールマスへの移動の仕方は，実際にそのような移動が可能かどうかに影響しない．すなわち，スタートマスからゴールマスへの移動は，$y$ 軸方向に $n-1-k$ マス動き，その後 $x$ 軸方向に $k$ マス動く場合のみを考えればよい．
　このとき，実際に最終的な $x$ 座標が $(k,l)$ とすることができるかどうかは，図2（ $n=7，k=2，l=3$ の場合）のように実際に経路を書き，ゴールへたどり着くまでにすべての経路を通れるかを検証すればいい．たとえば図2では，ゴールへたどり着くまですべての経路を通っていないので，$n=7$ において $(k,l)=(2,3)$ とすることはできない．ここで，どの隣接するスタートマスとも直接連結されていないゴールマスを行き止まりとよぶ．

　さて，$(k,l)$ の値によって場合分けをする．

• $(1)$ $l=0$ のとき
  　$a$ 回目にたどり着くゴールマスの $x$ 座標は $ak$ と $\mathrm{mod}\ n$ で合同．行き止まりとなるゴールマスは $x=0$ 上のものであるため，$ak\ (a=1,\ldots,n)$ が $a=n$ で初めて $n$ の倍数となればよい．つまり $k$ と $n$ が互いに素であることが条件であるため，場合の数は $\varphi(n)$ ($\varphi$ はEuler関数)．

• $(2)$ $k=l\neq 0$ のとき
  　始めにたどりつくゴールマスが行き止まりなので，明らかに不適．

• $(3)$ それ以外
  　 $P$ が最初にいたスタートマスと同じ $y$ 座標のマス及び最初に着いたゴールマスと同じ $x$ 座標のマスを削除し，離れた部分をくっつけるようにして新たに一辺 $n-1$ の正方形を作る(図3)．

このとき場合分けより行き止まりのゴールマスは消去されず，もとの正方形で $P$ が $n$ または $n+1$ 回目の操作で到着したマス $A$ 及び行き止まり以外はすべての出入りが連結される．また新たにループが生まれる・消えることもないため，このマス $A$ を新たに点 $P$ の初期位置と定めると，一辺 $n-1$ の正方形における新たな経路を得ることができる．この場合分けに該当する $(k,l)$ の組は $(n-1)^2$ 個であり，操作によって消去される $x$ 方向の移動の回数に着目すれば，一辺 $n-1$ の正方形の経路における $x$ 方向の移動の回数は $$\begin{cases} kn+l-2k & (l\lt k) \\ kn+l-(2k+1) & (l \gt k) \end{cases}$$ であり，場合分けの条件下においてこれは $0$ 以上 $(n-1)^2$ 未満の任意の整数値をちょうど一度ずつとる．したがって，この場合に問題の条件を満たす $(k, l)$ の個数は $A_{n-1}$ に等しい．

　以上より，任意の $2$ 以上の整数 $n$ について $A_n=A_{n-1}+\varphi(n)$ を得る．さらに $A_1=1=\varphi(1)$ なので， $$A_n=\sum_{k=1}^{n}\varphi(k)$$ であり，これを計算すればよい．$50$ 以下の正の整数の組 $(k,l)$ であって $k$ と $l$ が互いに素となるようなものの個数は $2A_{50}-1$ に等しく，一方でこれは $k,l$ がともに $2,3,5,\ldots$ の倍数である場合をそれぞれ計算することで $1547$ に等しいことがわかる．これより $A_{50}=\mathbf{774}$ がわかり，これが解答すべき値である．