ある入試問題 – icefog BLOG

学部特別選抜入試問題らしいのですが、要望があったので解いてみました。~~(問3)は解けませんでした。~~解答しました。

ルールは設けてなくて、高校数学の範疇で解くというような縛りもしてません。
こういう数学オリンピック系の問題も、色々な角度から見ると面白いですね。

後々必要に応じて記号を導入していくのが煩わしいので、先に一通りの準備をしておこうと思います。
(問1)と(問2)は力押しで解けるので、(問3)を意識して定式化します~~(また気が向いた時に(問3)も考えてみます)~~。

n次対称群 $S_n$ がn次直積群 $X=(Z_2)^n$ に, $(g, (a_1,\ldots,a_n))\mapsto (a_{g(1)},\ldots,a_{g(n)})$ で作用しているものとする.

n次巡回置換 $\sigma=(1\ldots n)$ の生成する $S_n$ の部分巡回群 $\langle\sigma\rangle$ がXに作用していると見て, Xを $\langle\sigma\rangle$ 空間と考えると, 商空間 $\langle\sigma\rangle\backslash X=Y$ は問題のコインの状態と一対一対応がある.

関数 $f: Z_2\rightarrow Z_2$ を $f(a)=a+1$ と定義し, $\Omega=\{1,..,n\}$ からYへの作用 $F_k$ を,

$F_k(j)(a_1,\ldots,a_n)=(a_1,\ldots,f(a_j),\ldots,f(a_{j+k-1}),a_{j+k},\ldots,a_n)$

で定義する. つまり $F_k(j)$ は $Y\ni x=(a_1,..,a_n)$ のj番目の要素からk枚をひっくり返す, YからYへの写像である. 写像の積を合成により定義すると, これは $\langle\sigma\rangle$ 作用で等化した元を考えるから, 右をはみ出す場合は左に戻って作用する. このとき作用 $F_k$ は次の性質を持つ.

(i) 冪等性: $F_k(j)^2 = Id$ ,
(ii) 可換性: $F_k(i)F_k(j) = F_k(j)F_k(i)$

実際(ii)は, $F_k(i)$ と $F_k(j)$ によって影響を受ける $x\in Y$ の要素で共通のものがなければ明らかだし, そうでない場合も $\langle\sigma\rangle$ 作用による商を考えているから, $1\leq m\leq k-1$ に対し, m個の要素を共有する $x=(A, a_1,\ldots,a_m, B)$ の場合に帰着される. AとBはk-m個以上の要素を含む $Z_2$ の部分列で, $F_k(i), F_k(j)$ がそれぞれB, Aを変化させないものを取っている.

このとき

$F_k(i)F_k(j)(x) = F_k(i)(A, f(a_1),\ldots,f(a_m), B') = (A', a_1,\ldots,a_m, B') = F_k(j)F_k(i)(x)$

の形になるのが分かる.

$1\leq m\leq n$ なるmに対し, m個の作用の合成 $T_m=F_k(j_1)\circ F_k(j_2)\circ \cdots \circ F_k(j_m)\ (j_p\neq j_q\ (p\neq q))$ 全体の集合を $G_m(n,k)$ と定義し,

$G(n,k) = \bigcup_{m=1}^n G_m(n,k)$

と定義する. ここで $G_m(n,k)$ の元は $F_k$ の可換性(性質(ii))により, 番号を辞書式に(つまり $F_k(2)F_k(3)F_k(7)$ のように)取っておくと決めて一般性を失わない. 利便性のため, 以降 $[2,3,7]\in G_3(n,k)$ 等と書くことにして, $G_m(n,k)$ の元を指数mの作用と呼ぶことにする.

上の商空間Yの定義に関し注意すべき点は, $\langle\sigma\rangle$ が $G(n,k)$ にも $(\tau,F_k(j))\mapsto F_k(\tau(j))$ で作用していると考えて, 二つの作用に整合性

$T(\tau(x))=(\tau^{-1} T)(x)\ (\tau\in \langle\sigma\rangle)$

を持たせないといけないことである. ここでTは $F_k(j)\ (j=i_1,..,i_m)$ の積で表されることを注意しておく. 実際 $F_k(j)(x)=y$ なら, $\tau\in \langle\sigma\rangle$ に対し, $F_k(\tau(j))(\tau(x))=y$ だから,

$T(\tau(x))=(\tau^{-1} T)(\tau^{-1}\tau(x)) = (\tau^{-1} T)(x)$

が成立する. つまり, Xの元xの $G(n,k)$ 軌道を考えるとき, 我々の立場からはxの属している軌道が問題なのだから, $G(n,k)x\sim \langle\sigma\rangle G(n,k)x$ と見るべきである.

(問3)で問われているように, 任意の初期状態 $x=(a_1,\ldots,a_n)$ から操作の有限回の繰り返しでゲームが終了できるための必要十分条件は,

$x\in G(n,k)(1,1,\ldots,1) = \{ T(1,1,\ldots,1) | T\in G(n,k) \}$

となることである.

逆にある初期状態 $x\in X$ が存在し終了状態にさせられないことと, $G(n,k)$ 作用によるXの軌道分解が二つ以上の直和から成ることとは同値である. これで準備は整った.

問1. 4回, 作用パターン $[1,2,3,7]$ .
実際n=7, k=3で, 初期状態はW上1001010と表せる. 関係(*2)による縮約によって

1001010 ～ 0111010 ～ 1011011 ～ 1000111 ～ 1111111

だからゲームは写像 $[1,2,3,7]\in G_4(7,3)$ により, 4回で終了させることができる. 3回以下でゲームを終了させられないことも, 次のようにして分かる.

ある状態での1の個数をbとして, 初期状態ではb=3である. $G_1(7,3)$ の元でbは $\pm1,\ \pm 3$ の変動をせしめうる. 最終的にb=7にするために, +4せねばいけない. よって１回で終了はできない. また, 操作( $G_1(7,3)$ の元)の可換性から, 2回で終了させるためにbは1+3, 2+2という増減パターンを取らなければいけないが, 直ぐに確かめられる通りこれも不可能である. よって3回で終了できないことを言えば良い. 最大 ${}_7C_3=35$ パターンを確かめるのはそれほど難しくないが, ここではより易しい考察で不可能なことが分かる.

つまり3回で終了するためには, 2回目にxは0001111の軌道上にないといけない. このときb=4であるが, $\pm 1,\pm 3$ のどの２回の組み合わせによっても+1することはできないので, これは不可能だと分かる. よって(問1)が言えた.

問2. 指数1の作用6通り, 指数2の作用15通り, 計21通りを検証し, 指数3以上の全ての作用がこれらの組み合わせで構成できることを確かめて, 不可能だと証明できる. 厳密には帰納法を使う.

以下指数4までの対応表:

Id=[1,2,4,5]=[1,3,4,6]=[2,3,5,6]
[1,2]=[4,5]=[1,3,5,6]=[2,3,4,6]
[1,3]=[4,6]=[1,2,5,6]=[2,3,4,5]
[1,4]=[2,5]=[3,6]
[1.5]=[2,4]=[1,2,3,6]=[3,4,5,6]
[1,6]=[3,4]=[1,2,3,5]=[2,4,5,6]
[2,3]=[5,6]=[1,3,4,5]=[1,2,4,6]
[2,6]=[3,5]=[1,2,3,4]=[1,4,5,6]
[1,2,3]=[1,5,6]
[1,2,6]=[1,3,5]=[2,3,4]

2015-12-15 12:30追記

一旦解答した後, (n,k)=(3,2)に対し相異なる二つの軌道 $0\sim 2,\ 1\sim 3$ が存在することを確かめた. これは明らかに上記における例外となっており, nとkが互いに素という条件では不十分だったことが分かった.

実際のところ $Z_n$ の中でk倍写像の生成する部分群の個数と一対一対応しているというのに根本の誤りがあり, (n,k)=(3,2)の場合, それは唯一つ( $:=Z_3$ )であるが, 実際には2つの軌道があることが確かめられる.

さて上の議論を精密にするため, アーベル群のk倍写像 $i\mapsto i+k$ の代わりに, 写像 $(\eta,\mu)$ を次のように定義する. $J=\{0,\ldots,n\}$ とするとき,

$\begin{cases} \eta(i) = \begin{cases} i+k & (k+i\leq n) \\ 2n-(k+i) & (k+i>n)\end{cases} \\ \mu(i) = \begin{cases} i-k & (k<i) \\="" k-i="" &="" (i\leq="" k)\end{cases}="" \end{cases}=""$

=”” これらの写像はすぐに加法との整合性がないと分かる.=”” 実際 $0\leq="" g\leq="" j$ に対し,=”” $i="n-k-j$ のとき $\eta(i+g)=\eta(i)" +="" g$ なのに $i="n-k+j+1$ のとき $\eta(i+g)=\eta(i)-g$ である.” $\mu}$ も同様に示される.=”” 一方で,=”” これらは定義からjへの作用になっているため,=”” その軌道を考えることができる.=”” 厳密にはiの値によって作用のさせ方が異なるようにしなければいけないが,=”” これら $(\eta,\mu)$ が共に作用していると見て $(\eta,\mu)$ 作用と呼ぶことにする.=”” この意味は,=”” jの元のうちこれら二つの作用の組み合わせで写りあう全ての元を等化するということである.=”” 実はそうして得られる軌道の個数が1であることが,=”” 任意の初期状態から終了状態にできるための必要十分条件であることを次のように説明できる.=”” $g(n,k)$ 作用によってxの元は常に $x_0="(0,\ldots,0),\ldots,x_n=(1,\ldots,1)$ にY上同値であり,” 集合 $h="\langle\sigma\rangle\backslash\{x_0,x_1,\ldots,x_n\}$ の元を自然数の集合 $J=\{0,\ldots,n\}$ と見るとき,” $(\eta,\mu)$ 作用の合成によって $i\mapsto="" n\="" (\forall="" i\leq="" n)$ とできれば,=”” 任意の初期状態から終了状態にできることになる.=”” 具体的に $(\eta,\mu)$ のjへの作用とhへの作用を同一視する際には,=”” $x_i="(0,\ldots,0,\overbrace{1,\cdots" ,1}^{i})$ の1の個数をiとし,=”” 要素で0か1いずれかが最大長続いている左から数えて最初の塊の一番目の要素の番号を $t_i$ とするとき(i=”nのときは1番目を選ぶ.” 巡回置換によって作用の結果残った1は全て右端に移し,=”” これを改めてhの元と見る),=”” このとき $f_k(t_i)$ を0に対し適用させる時,=”” それによって変動した1の個数を $\mu(i)$ ,=”” 一方1に対し適用させた時の変動した1の個数を $\eta(i)$ と見做す.=”” これを同じiが現れなくなるまで繰り返す.=”” 具体的に(n,k)=”(17,6)の時,” 0に属す軌道だけやってみよう.=”” \begin{array}{lcl}=”” (0,\ldots,0)=”” &\sim&=”” (0,\ldots,0,\overbrace{1,\cdots=”” ,1}^{6})=”” ,1}^{12})=”” (1,1,1,1,1,0,1,\ldots,1)=”” (0,\overbrace{1,\cdots=”” ,1}^{16})=”” ,1}^{10})=”” ,1}^{4})=”” (1,1,0,\ldots,0)=”” (0,\ldots,0,1,1)=”” ,1}^{8})=”” ,1}^{14})=”” \end{array}=”” このことを $x_0\sim="" x_6\sim="" x_{12}\sim="" x_{16}\sim="" x_{10}\sim="" x_4\sim="" x_2\sim="" x_8\sim="" x_{14}$ と書いてh上一つの軌道と見ることは,=”” j上の $(\eta,\mu)$ 軌道と見ることに等しい.=”” さて,=”” 作用 $(\eta,\mu)$ による $j$ の軌道分解は仮定よりj全体であるから,=”” 任意の初期状態(の代表系) $x_i$ は終了状態(の代表系) $x_n$ に指定された作用の合成で移ることができる.=”” これで十分条件は示された.=”” 上で説明した対応 $h\leftrightarrow="" j$ によって必要性も明らかであろう.=”” <hr=””> </i)>

以上を踏まえて $G(n,k)$ 空間Xに関する議論として再構すると, 補題及び問３の正確な解を得る.

Lemma.1. $k\geq 2,\ k\mid n$ のとき, Xが相異なる軌道を2個以上持つ.
$1\leq l\leq k$ に対し, $x_l=(0,\cdots ,0,\overbrace{1,\cdots ,1}^{l})$ とおくとき, 仮定より $(1,\ldots,1)\sim (0,\ldots,0)\sim x_k\in G(n,k)x_k$ だから, $x_0 \not\sim x_1$ を示せば(*1)は示されたことになる.

$(\eta,J)$ 上の議論で $n=mk$ とおくと,

$1\sim 1+k\sim \cdots \sim 2n-(1+mk)=n-1 \sim k(m-1)-1 \sim \cdots \sim k-1 \sim \cdots \sim n-1$

作用が巡回するので軌道上これ以上新しい元は得られない. 1の軌道上にある全ての元は $\not\equiv 0\mod k$ であるから $x_0 \not\sim x_1$ である■

Lemma.2. kが偶数のとき, 0の $(\eta,\mu)$ 軌道は偶数である.
初期段階ではi=0だから, 無論偶数. iが偶数なら $\eta(i),\mu(i)$ は定義から偶数である■

Lemma.3. kが偶数のとき, Xが相異なる軌道を2個以上持つ.
補題2により, 1の $(\eta,\mu)$ 軌道は奇数であるから, この場合も $x_0\not\sim x_1$ が示される.

最後に問題３の解答.

Prop.1. kが奇数でnとkが互いに素であることは, Xが唯一つの軌道を持つことの必要十分条件である.
(必要性) 補題1, 3から, kは奇数で $k\nmid n$ を満たすことが分かる. kとnが最大公約数 $d\geq 2$ を持つと仮定して矛盾を出す.

整数列 $\{C_j\}_j$ で,

$\begin{array}{l} C_0=0, C_i\in \{[n/k],[n/k]+1\}\ (\forall 1\leq i\leq s) \\ C_1+\ldots+C_s = n \end{array}$

を満たすものに対し, 関数 $\rho_{ij}$ を

$\rho_{ij}(v)=(-1)^i\{v+(j+C_1+C_2+\ldots+C_i)k - 2in\}\ (0\leq j\leq C_{i+1},\ i\geq 0)$

で定義する. このとき0の $(\eta,\mu)$ 軌道は $\rho(0)$ の形をしているので, 軌道は常にdの倍数から成る. 一方1の軌道は $\rho(1)$ の形だから決してdの倍数にならない. 仮定から $x_0\sim x_1$ でないといけないが, これらは同一軌道に成り得ないので矛盾である.

(十分性) 上で定義した関数 $\rho_{ij}$ は, 0での値 $\rho_{ij}(0)$ をiを添え字, jをパラメータの関数とみるとき

$\rho_{ij}(0) = \pi_i(j)$

と書くことにする. これがJへの全射, つまり $\pi_{i_1}(j)\neq \pi_{i_2}(j')\ (\forall 1\leq i_1<i_2\leq s,\="" \forall="" j,j')$ であることと,=”” 唯一つの軌道を持つことは同値である.=”” 今仮定よりnとkは互いに素であるから,=”” $\pi_i(0)-\pi_{i'}(0)\not\equiv="" 0\mod="" k\="" (\forall="" i,i'\leq="" i\neq="" i')$ であるので(*2),=”” $\pi_i(j)$ は全射であることが示された■=”” (*2):=”” $k\mid="" 2nm="" (m\geq="" 1)="" \leftrightarrow="" k\mid="" m$ だが,=”” $m\leq="" s-1<k$ よりこれは起こりえない=”” <!–=”” (n-k)=”” k=”” <=”” c_1=”” (n+k)=””> C_2
2(n-k)/k-C_1 < C_3 2(n+k)/k-C_2 > C_4
3(n-k)/k – (C_1+C_3) < C_5 C_{2j} < j(n+k)/k-\sum_{l=1}^{j-1} C_{2l} C_{2j-1} > j(n-k)/k-\sum_{l=1}^{j-1} C_{2l-1} </i_2\leq>

2n/k-(n-k)/k>2n/k-C_1≧C_2
(3n-k)/k – C_1 – (n+k)/k< (3n-k)/k – (C_1+C_2) < C_3 4n/k-C_2 – 2(n-k)/k >4n/k-(C_1+C_2+C_3)≧C_4

3(n-k)/k – (C_1+C_3) < (5n-k)/k – (C_1+C_2+C_3+C_4) < C_5 0, k, 2k, .., C_1k, 2n-C_1k-k, 2n-C_1k-2k, .., 2n-(C_1+C_2)k, (C_1+C_2+1)k-2n, (C_1+C_2+2)k-2n, .., (C_1+C_2+C_3)k-2n, 4n-(C_1+C_2+C_3+1)k, 4n-(C_1+C_2+C_3+2)k,.., 4n-(C_1+C_2+C_3+C_4)k (C_1+C_2+C_3+C_4+1)k-4n,.., (C_1+C_2+C_3+C_4+C_5)k-4n m + i = n (i<k) なら,=”” m=”” →=”” +=”” 2i=”” -=”” k=”m” 2(n-m)=”” i=”n-C_1k” c_{2j}=”” <=”” j(n+k)=”” k-\sum_{l=”1}^{j-1}” c_{2l},\\=”” c_{2j-1}=””> j(n-k)/k-\sum_{l=1}^{j-1} C_{2l-1} \\
–></k)>