おしどり硬貨のパズル〜証明

おしどりパズルの証明は、数学における「置換」という概念を用いると簡単になる。ある列を逆順にしたり他の形に入れ換えたりする操作を、数学では「置換」と呼ぶ。列の二つの要素を入れ換える置換を、特に「互換」と呼ぶ。さて、全ての置換は、いくつかの互換の組み合わせに書き換える事ができる。複数の互換の組み合わせを「互換の積」と呼ぶ。例えば4枚の硬貨の入れ換えは、下図のように二回の互換の積で表せる。

ある置換を互換の積で表す場合、その表し方は様々であるが、次の重要な定理がある。

定理: ある置換を互換の積に表した場合、その互換の数が偶数個か奇数個であるかはその表し方に依存しない。

つまり、ある置換が偶数個の互換の積で表せた場合、その置換は奇数個の互換では表せない、という事になる。という事は、置換の性質はそれが偶数個の互換で表せるか奇数個の互換で表せるかによって、二つに分けられる事になる。偶数個の互換の積である置換を「偶置換」、奇数個の互換の積である置換を「奇置換」と呼ぶ。

この定理の詳細な証明は群論の教科書を参照していただきたいが、以下に簡単に述べておこう。証明を飛ばす場合はこちら

ある数列があって、全ての要素が異なる値を持つとする。この数列の i 番目と j 番目の要素を入れ換えるとしよう。数列の各要素について、右側にその要素より小さい値を持つ要素が何個あるかを数えて、この入れ換えによってその個数の合計がいくつ変化したかを調べる。このとき、 i 番目の要素の左側にある要素と、 j番目の要素の右側にある要素については、入れ換えの前後で、右側にある小さい値の要素の個数は変化しないから、除外して考える。

まず i 番目の要素について。入れ換え前に、この数列の i+1 番目から j-1 番目までで、 i 番目の要素より小さい値を持つ要素の数がN個だったとする。入れ換えの後では、これらが全部左側に来るので、 i 番目の要素から見た、右側にある小さい値の個数はN減る事になる。一方、i+1 番目から j-1 番目までの要素のうち、 i 番目の要素より大きい値を持つ要素は、(j - i - 1 - N) 個ある。これらの要素については、 i 番目の要素が右側にやってくる事になるので、それぞれ1個ずつ、右側にある小さい値の個数が増える事になる。

同様に、j 番目の要素について考える。i+1 番目から j-1 番目までに、 j 番目の要素より小さい値の要素の数がM個だったとする。入れ換えの後では、これらが全部右側に来るので、小さい値の個数はM個増える。一方で (j - i - 1 - M) 個の要素は、右側にあった自分より小さい値を失う。

これらの個数を合計すると、

- N + (j - i - 1 - N) + M - (j - i - 1 - M) = 2(M - N)

となる。そして、i 番目と j 番目の要素を比較すると、i 番目の要素の方が大きければ、個数の合計は1減るし、小さければ1増える。従って、i 番目と j 番目の要素を入れ換えると、右側にある小さい値を持つ要素の個数の合計は、2(M - N) - 1 か、2(M - N) + 1 となり、どちらも奇数となる。という事は、互換を一回行うと、要素の右側にある小さい値の個数の合計はその偶奇が反転する事になる。

従って、偶数回の互換の積と、奇数回の互換の積とでは、小さい値の個数の合計の偶奇は必ず一致しない、という事となる。故に、ある置換が偶置換でも奇置換でもある、という事にはならない。

いよいよ本題である。駒の数が4n+2個の場合を考える (4n, 4n+1 個の場合はできるのが明らかだし、4n+3 個の場合は、4n+2 個の場合から簡単に導ける)。このとき、逆順への入れ換え操作は、奇置換となる。

さて、「隣り合った二つの駒をいっしょに動かす」という操作を置換とみなし、それが偶置換であるか奇置換であるかを考えてみよう。任意の隣りあった二つの駒を移動した先が、元の位置から数えて n 個目の駒と n+1 個目の駒との間に移動したとしよう。下図の例の場合、6個の駒を挟んで移動したと数える。

この置換を、二つの駒のうち右側の駒を移動する置換と左側の駒を移動する置換の積であるとみなす。右側の駒を移動する置換は、nが偶数であれば偶置換、奇数であれば奇置換となる。これは、前述の定理の証明と同じ方法でも理解できるし、n 回の隣の駒との互換だと考えても良い。そして、同様にして左側の駒を移動する置換も、n が偶数の場合は偶置換、奇数の場合は奇置換となる。この二つの置換の積は、n が偶数の場合は偶置換と偶置換の積で偶置換となり、 n が奇数の場合でも、奇置換と奇置換の積でやはり偶置換となる。つまり、この操作は偶置換である事が示された。従って、この操作を何度繰り返そうとも、その結果は偶置換となる。

さて、4n+2 個の駒の列の逆順への入れ換えは奇置換であった。ある置換が奇置換でも偶置換でもあるという事はない。従って、奇置換となる入れ換え操作は、隣り合う二つの駒をいっしょに動かす操作では実現できない事になる。

証明終わり