整数の性質の問題

どの $2$ つも隣り合わない $4$ 個の頂点の選び方（$4$ 個の頂点の集合）を「よい選び方」とよぶ。

よい選び方の総数. 頂点 $1$ を含むよい選び方では、頂点 $17$ と頂点 $2$ は選べないので、残り $3$ 個を一列に並んだ頂点 $3,4,\dots ,16$（$14$ 個）から、どの $2$ つも隣り合わないように選ぶ。選ぶ $3$ 個を $x<y<z$ とし、$x,y-1,z-2$ に対応させると、これは $3,4,\dots ,14$ の $12$ 個から異なる $3$ 個を選ぶことと $1$ 対 $1$ に対応するので、${}_{12}{\mathrm{C}}_3=220$ 通りである。

対称性から、どの頂点についても、その頂点を含むよい選び方は $220$ 通りある。よい選び方 $1$ つには頂点が $4$ 個含まれるので、よい選び方の総数は
$$\frac{17\times 220}{4}=935$$
である。

回転で 17 個ずつの組に分ける. 各頂点を時計回りに $1$ つ隣へ移す回転を考える。番号は $i\to i+1$（$1\leqq i\leqq 16$）、$17\to 1$ と変わる。隣り合う関係は回転で保たれるので、よい選び方はよい選び方に移る。

番号を $17$ で割った余りで見ると、$i\to i+1$ も $17\to 1$ も「$1$ を足す」ことになる（$1\equiv 17+1(\mathrm{mod}17)$）。よって $1$ 回の回転で、選んだ $4$ 個の番号の和は $17$ を法として $4$ 増える。$j$ 回回転すると和は $4j$ 増える。

よい選び方 $A$ を $0,1,2,\dots ,16$ 回回転して得られる $17$ 個の選び方を考える。$0\leqq j<k\leqq 16$ のとき、$j$ 回と $k$ 回の回転で得られる選び方の和の差は $4(k-j)(\mathrm{mod}17)$ であり、$17$ は素数で $4$ とも $k-j$（$1\leqq k-j\leqq 16$）とも互いに素なので、$4(k-j)$ は $17$ で割り切れない。したがって、この $17$ 個の選び方は和を $17$ で割った余りがすべて異なり、特にすべて異なる選び方である。また、余りは $0,1,\dots ,16$ を $1$ 回ずつとる。

回転を $17$ 回くり返すと元に戻るので、よい選び方全体は、このような「互いに回転で移り合う $17$ 個の組」に重なりなく分けられる。組の数は $\frac{935}{17}=55$ であり、各組には和が $17$ で割り切れる選び方がちょうど $1$ つずつある。

よって、求める選び方は $55$ 通りである。

まず、どの $2$ つも隣り合わない $4$ 頂点の選び方の総数を求める。選ばない $13$ 個の頂点を円周上に並べると、その間の $13$ 個のすき間のうち $4$ 個に選ぶ頂点を $1$ つずつ入れればよい。頂点 $1$ を選ぶ場合と選ばない場合に分けて数える。
- 頂点 $1$ を選ぶ: 頂点 $2$, $17$ は選べないので、頂点 $3,\dots ,16$ の $14$ 個の並びから隣り合わない $3$ 個を選ぶ。${}_{14-3+1}{\mathrm{C}}_3={}_{12}{\mathrm{C}}_3=220$ 通り。
- 頂点 $1$ を選ばない: 頂点 $2,\dots ,17$ の $16$ 個の並びから隣り合わない $4$ 個を選ぶ。${}_{16-4+1}{\mathrm{C}}_4={}_{13}{\mathrm{C}}_4=715$ 通り。
合計 $220+715=935$ 通り。

次に、番号の和を $17$ で割った余りを考える。頂点 $k$ を頂点 $k+1$（頂点 $17$ は頂点 $1$）に移す回転を考えると、番号を $17$ で割った余りは各頂点で $1$ ずつ増える（$17\equiv 0$ から $1$ へも $+1$）。よって選んだ $4$ 頂点の番号の和を $17$ で割った余りは、$1$ 回の回転で $4$ 増える。

$17$ は素数なので、$0$ 回以上 $16$ 回以下の回転で得られる $17$ 個の選び方は、どの $4$ 頂点の組についてもすべて異なる（$17$ 頂点の正十七角形で、$4$ 個の頂点の集合が $0$ でない回転で自分自身に移ることはない。移ると $17$ が $4$ を割り切る必要があり不可能）。さらに、$4$ と $17$ は互いに素なので、$j=0,1,\dots ,16$ 回の回転後の和の余りは $s+4j$ となり、$17$ を法としてすべての余りをちょうど $1$ 回ずつとる。

したがって、$935$ 通りは $935÷17=55$ 個の組に分かれ、各組の中で和が $17$ の倍数となるものがちょうど $1$ 通りずつ。求める選び方は $55$ 通り。

確かめ: $935=17\times 55$ で割り切れる（回転による分類が整合している）。