ある入試問題

JCEqAsO

学部特別選抜入試問題らしいのですが、要望があったので解いてみました。(問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_2f(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\rangleG(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せねばいけない. よって1回で終了はできない. また, 操作(G_1(7,3)の元)の可換性から, 2回で終了させるためにbは1+3, 2+2という増減パターンを取らなければいけないが, 直ぐに確かめられる通りこれも不可能である. よって3回で終了できないことを言えば良い. 最大{}_7C_3=35パターンを確かめるのはそれほど難しくないが, ここではより易しい考察で不可能なことが分かる.

つまり3回で終了するためには, 2回目にxは0001111の軌道上にないといけない. このときb=4であるが, \pm 1,\pm 3のどの2回の組み合わせによっても+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}) \\ &\sim& (0,\ldots,0,\overbrace{1,\cdots ,1}^{12}) \\ &\sim& (1,1,1,1,1,0,1,\ldots,1) \\ &\sim& (0,\overbrace{1,\cdots ,1}^{16}) \\ &\sim& (0,\ldots,0,\overbrace{1,\cdots ,1}^{10}) \\ &\sim& (0,\ldots,0,\overbrace{1,\cdots ,1}^{4}) \\ &\sim& (1,1,0,\ldots,0) \\ &\sim& (0,\ldots,0,1,1) \\ &\sim& (0,\ldots,0,\overbrace{1,\cdots ,1}^{8}) \\ &\sim& (0,\ldots,0,\overbrace{1,\cdots ,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によって必要性も明らかであろう.


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

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が示される.

最後に問題3の解答.

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 s,\ i\neq i')であるので(*2), \pi_i(j)は全射であることが示された■

(*2): k\mid 2nm (m\geq 1) \Leftrightarrow k\mid mだが, m\leq s-1<kよりこれは起こりえない