数学の部屋へもどる◆熊本県の中学校３年生 ニャン さんからの解答
【問題１】
5手です
【問題２】
16手です
【おまけ１】
ｎが奇数のときn×nの黒石を全て裏返すのは最短でｎ手です。
(1,1)、(2,1)、…(n,1)のn手になります。
【おまけ２】
ｎが偶数のときｎ×ｎの黒石を全て裏返すのは最短でn×n手です。
(1,1)、(2,1)…かどに来たら曲がって、の繰り返し、1度裏返したところの直前で曲がる…の繰り返しで結果的に全部の駒を1度裏返すので 結果的にn×n手になります。
【おまけ３】
【おまけ１】は縦をｎ行、横をn'行とします。
縦1行のみを裏返しにしていくと、偶数手の時には、その行は黒、裏返した横の石は全て水色。
(n-1)手のときに(nが奇数ということでn-1は偶数)n行め及びn'行の(2n-1)個のみが黒であり、そこで(n',1)を裏返すと全てが水色になりま す。
よって、(n-1+1)でn手ということになります。
【おまけ２】はおまけ１と同様にしていくとn回裏返したときに(nが偶数ということでn回)n行目のみが黒です。
そこから曲がり(n,n')に来たらまた曲がり (1,n')でまた曲がり、さっき裏返した(1,1)の直前(2,1)で曲がり…というふうに繰り返していくと、全ての石(つまりn×n)を1度裏返すことになります。
よってn×n手ということになります。
◆海外 ブリタ さんからの解答
【問題１】
縦または横に一直線上の駒を一回ずつクリックしていく（順番を問わない）。
(1,1)→(2,1)→(3,1)→(4,1)→(5,1)
(1,3)→(2,3)→(3,3)→(4,3)→(5,3)
(1,3)→(3,3)→(5,3)→(2,3)→(4,3)
など、5手の手順が10×5!通り。
また、全ての駒が少なくとも一回はひっくり返らないといけないので、行数（列数）が５であることを考えれば、５手が最短手。
【問題２】
全ての駒をクリックするような手順（順番を問わない）
(1,1)→(1,3)→(1,4)→(2,1)→(2,3)→ (2,4)→(3,1)→(3,3)→(3,4)→(4,1)→ (4,3)→(4,4)→(1,2)→(2,2)→(3,2)→ (4,2)など、16手の手順が16!通り。
【おまけ３】
全ての駒が少なくとも一回はひっくり返らないといけないので、行数（列数）がnであることを考えれば、n手が最短手。
１．ｎが奇数の場合、縦または横に一直線上の駒を一回ずつクリックしていく（順番を問わない）と、クリックされた行（または列）以外の駒は全て一回ずつひっくり返るので、青になる。
クリックされた行（または列）の駒はn回（奇数回）ずつひっくり返るので、青になる。
従ってこの手順が最短手で全ての駒を青にすることが出来る。
２．ｎが偶数の場合
この『オセロの石の裏返し』は、以下（１）〜（２）の性質がある。
（１） クリックする順序を問わない
（２） 同じ駒を複数回クリックした場合は、偶数回であれば０回（クリックしない）、奇数回であれば１回クリックした場合と同様の結果になる。
上記（１）（２）より、n2個の駒のうちどの駒をクリックしてどの駒をクリックしないかという組合せを調べれば、すべての手順を検証することが出来る。
以下、上記（２）の無駄を省いた場合の手順（以下「効率的手順」）のみを考える。
効率的手順の組合せは2^n2通り（クリックする順番を問わない）であり、
いずれの効率的手順の手数も高々n2手である。
また、
（３） ある駒を１回クリックし、その駒の上下左右の駒を全て１回ずつクリックすれば、最初にひっくり返した駒のみを反転することが出来る。
（∵中心の駒は2n-1回（奇数回）ひっくり返され、上下左右の駒は全てn回（偶数回）ひっくり返される）
上記（３）より、任意の駒の色の組合せに対して、ある効率的手順が存在することが分かる。
任意の駒の色の組合せも効率的手順の組合せも同じく2^n2通りであることから、これらは１対１対応している。
ところで、全ての駒を１回ずつクリックする効率的手順は全ての駒を反転させる。
（∵全ての駒は2n回（偶数回）ひっくり返される）
従って、全ての駒を反転させるための効率的手順は、全ての駒を１回ずつクリックする効率的手順のみであり、
その手数はn2手である。
◆滋賀県 松尾 さんからの解答
【問題１】【おまけ１】【おまけ３】
同じ列または行の石を裏返します。n 手必要です。
すべての石を1回は裏返すので、n × n の場合、少なくともn手必要です。
n手に満たない場合、裏返してない行、列が残ります。
奇数の場合、同じ行または列を裏返せばいいので、 n手が最短手数です。
【問題２】【おまけ２】【おまけ３】
すべての石を裏返します。n×n 手必要です。
(1) 2×2 の場合を考えます。4個を水色に変えるには4個すべてを裏返します。
これ以外にありません。(○は水色、×は黒です。)
裏返した順序 ×× --> ○○ --> ×× --> ○× --> ○○ 1 2 ×× ○× ○○ ×× ○○ 3 4(2) 4×4 の場合を考えます。
nが奇数の場合のように、1列または1行を裏返しただけではできません。
他の列、行も裏返す必要があります。
違う列、行を裏返した場合を考えます。
以下は2手進めた時の状態です。
(1,1)(2,2)を裏返しました。○は水色、×は黒です。
○×○○
×○○○
○○××
○○××ここで、左上の4個(1,1),(1,2),(2,1),(2,2)に注目します。
右下の4個を裏返しても、左上の4個の状態は変わりません。
左下または右上の4個を裏返しても、×は○になりますが、同時に○が×になります。
結局、左上の4個を裏返して○にそろえるしかありません。
そろえるには 2×2の場合と同じです。
全てを裏返すので 4手必要です。
この場合は(1,2),(2,1)を裏返します。
以下のようになります。
○○××
○○××
××××
×××× 裏返した石以外は、裏返されてないか、2回裏返されてるので×(黒)のままです。
○○○×
○○○×
○○○○
××○× ここでは、右下の4個、(3,3),(3,4),(4,3),(4,4)に注目します。同じように残りの2×2の2ブロックをすべて裏返して、すべての石が○になります。
(3) nが6以上の偶数の場合も同じです。
結局、すべての石を裏返す必要があり、最短の手数はn×nとなります。
なお、2×2を隣合わせの石で考えましたが、離れていても同じです。
◆神奈川県 アンパンマン さんからの解答
【問題１】
(2,1)→(2,2)→(2,3)→(2,4)→(2,5)→
【問題２】
(1,1)→(1,2)→(1,3)→(1,4)→(4,1)→ (4,2)→(4,3)→(4,4)→(2,1)→(2,2)→ (2,3)→(2,4)→(3,1)→(3,2)→(3,3)→ (3,4)→【おまけ１】
ｎ手(列または行のすべてのマスを押す、順番は関係ない)
回答数=2n
【おまけ２】
ｎ2手(列または行のすべてのマスを押す、順番は関係ない)
回答数=1
【おまけ３】
●奇数のときの最短の理由
k回(k＜n)押して、押した枡目を(a_1,b_1),...,(a_k,b_k)とする。
M={1,...,n}、A={a_1,a_2,...,a_k}、B={b_1,b_2,...,b_k}とすると
(M-A)×(M-B)のマスは押されないので、ひっくり返されていないことになる。
矛盾。
よって少なくともn手が必要。
ｎ手の例が見つかったので、nは最小回数である。
●偶数の場合の最短手数の理由
偶数の場合、どのマスでも、そのマスの行と列にあるすべて押すと、
そのマスだけひっくり返される(2n-1回)。
まず、次の二つのことが自明である（証明を省略）。
Lemma1.マスを2回押すと状態が変わらない
Lemma2.マスの押す順番が関係ない
最短手数は上記の手法で一つだけのマスをひっくり返させる。
Lemma1,2により、次の方法で回数を減らす。
1.押す回数が偶数の場合のマスは押さないことにする
2.押す回数が奇数の場合、マスを押す回数を1回に減らす
これにより、最短手数が得られる。
nが奇数の場合どのマスの押す回数も奇数(2n-1)であるため、すべてのマスを一回ずつを押すのが最短手数になる。
◆愛知県 Y.M.Ojisan さんからの解答
【問題１】 ５手
(1,1)→(1,2)→(1,3)→(1,4)→(1,5)→
【問題２】 １６手
(1,1)→(1,2)→(1,3)→(1,4)→(2,1)→(2,2)→(2,3)→(2,4)→(3,1)→(3,2)→
(3,3)→(3,4)→(4,1)→(4,2)→(4,3)→(4,4)→
【おまけ１】 ｎ手
手順は上辺一行返し。
(1,1)→(1,2)→(1,3)→〜→(1,n−1)→(1,n)
【おまけ２】 ｎ2手
手順は全石返し。
(1,1)→(1,2)→(1,3)→〜→(1,n−1)→(1,n)→ (2,1)→(2,2)→(2,3)→〜→(2,n−1)→(2,n)→ ↓ (n,1)→(n,2)→(n,3)→〜→(n,n−1)→(n,n)【おまけ３】
（１） 奇数の場合
十分条件：
上辺一行を返せば各列の２行目以下が裏になる。
また上辺一行は奇数回の返しが発生するので裏になる。
必要条件：
ｎ未満の返しでは、少なくとも一行は返した石のない行がある。
列も同様である。
よってその交点にある石は表のままであり、ｎ未満では不可能である。
（２） 偶数の場合
十分条件：
全石を返せば、各石につき、2n−1 回＝奇数回の返しがあり、全て裏にすることができる。
必要条件：
全て表の状態をφ、全て裏をα、全て返す手順（実際は順序に拠らないのでパターンである）をＡとする。
さらに、返す操作実行を＾で表すと、十分条件は φ＾Ａ＝α とあらわされる。
また手順数は ＃Ａ＝ｎ2 等と表記することとする。
（注記：＾は排他論理和を模倣している）
いま φ＾Ｂ＝α である Ｂがあって ＃Ｂ＜ｎ2とする。
問題の対称性から、Ｂをｐ行回転シフトした Ｂ↑ｐ もまた
φ＾（Ｂ↑ｐ）＝α である。
よって、ｎは偶数なので
| Ｃ＝ | ｎ Λ ｐ＝１ |
（Ｂ↑ｐ） とおくとき φ＾Ｃ＝φ である。 |
ここで Λは ｐ＝１〜ｎまでの 連続＾演算を表すとする。
Ｂのある一行（ｋ行）の返しの数を ｍ＝＃Ｂk,* とすると、
対応するＣの行の返し数は ｍｎ＝＃Ｃk,*であり、Ｃ生成式の対称性からＣの各位置の返し数は ｍ である。
実行上の操作は ｍ の偶奇性のみに依存する。
したがって、Ｃは各行において全て返すか、返さないかのいずれかでと等価である。
さらに行の交換を行えば、上から何行かのみ全て返す手順である。
その結果、得られる石のパターンは返し方（つまりＣ）ないしその表裏反転と同じパターンが必ず得られる。
一方、φ＾Ｃ＝φでなければならない。
従って、 ｍ は全ての行で偶数（＝返さない）でなければならない。
列方向も同様である。
＃Ｂ＜ｎ2の場合、どこかに返していない位置がある。
その位置を通る行、列を考えるとき、いずれも返し数は偶数であるから、その位置は裏にはならい。
即ち φ＾Ｂ≠αである。
よって ＃Ｂ＝ｎ2でなければならない。
◆東京都 明 さんからの解答
【問題１】
(1,1)→(1,2)→(1,3)→(1,4)→(1,5)
【問題２】
(1,1)→(1,2)→(1,3)→(1,4)→(2,1)→ (2,2)→(2,3)→(2,4)→(3,1)→(3,2)→ (3,3)→(3,4)→(4,1)→(4,2)→(4,3)→ (4,4)【おまけ１】
ｎが奇数の時、同一列、もしくは同一行のｎ個の駒を反転することにより、駒を全て裏にできます。
このｎ手が最短手数です。
【おまけ２】
ｎが偶数の時、ｎ×ｎのすべての駒を１回ずつ反転することにより、駒を全て裏にできます。
このｎ×ｎ手が最短手数です。
【おまけ３】
このゲームでは駒を裏返す順番に関わりなく、裏返す駒の場所のみで結果が決まります。
したがって、同一の駒を２回裏返す手はありません。
ｎが奇数の時、
裏返した駒と同一の行、列を外すことを考えると、ｎ-1回の駒の裏返しでは必ず最低１個の駒が残ることになります。
これはｎ-1回の駒の裏返しでは、すべての駒を裏返しにできないことを示します。
同一列、もしくは同一行のｎ個の駒を反転するとすべての駒が裏となります。
したがって、このｎ手が最短手数となります。
ｎが偶数の時、
まず、すべての駒を１回ずつ反転させたとき、すべての駒は奇数回反転することになり、すべての駒は裏になります。
１つの駒に注目して、その駒を含めその駒の同一の行、列にある駒を１回ずつ反転させると、注目した駒のみが裏となり、他の駒は元のままです。
したがって、盤面の駒を任意のパターンにすることができて、
パターンの数は2ｎ×ｎです。
（偶数回駒を反転させるのは全く反転させないことと同じであることに注意）
一方、反転させる駒の選び方も2ｎ×ｎですので、盤面の駒の任意の裏返しのパターンに対して、反転させる駒のただ１つの選択方法が対応することが判ります。
以上により、すべての駒を１回ずつ反転させることがすべての駒を裏にする最小手数であることが証明されました。
言い換えれば、ｎが偶数のとき、反転させる駒をｎ×ｎ次元の一つのベクトルに対応させると、すべての駒で構成されるｎ×ｎ個のベクトルは一次独立であると言うことができます。
ｎが奇数のときはｎ×ｎ個のベクトルは従属関係があり、
従属なベクトルは2(n-1)個となるようです。
ちなみに、盤の縦、横が異なる場合でも、共に偶数の時はすべての駒を反転させることが、すべての駒を裏返しにする最短手数であり、 共に奇数であるときは小さい方の一列を反転させることがすべての駒を裏返しにする最短手数であることを同様に証明できます。
一方が偶数で、他方が奇数の場合は、奇数の一列を反転させることが最短手数のようですが、証明はできていません。
前回回答で証明できていなかった部分についてご報告します。
横（行方向）が奇数、縦（列方向）が偶数の場合の最短手数は一行の駒をすべて反転指定することであることを証明します。
まず１つの行の駒をすべて反転指定すれば盤面の駒はすべて裏になります。
次に１つの行の駒をすべて反転指定しない場合、盤面のすべての駒を裏にすることができないか、最小手数にできないことを示します。
（１）最初の行で反転指定した駒の数が偶数の場合。
この行の駒は表になっているため、すべてを裏にするために各列ごとに少なくとも１つを反転指定しなければなりません。
この場合、１つの行の駒をすべて反転指定した場合より手数が多くなってしまいます。
（２）最初の行で反転指定した駒の数が奇数の場合。
この行の駒はすべて裏になっているので、盤面の残りの列方向で反転指定する駒の数は列ごとに偶数でなくてはなりません。
したがって反転指定する最初の行以外の駒の総数は偶数でなくてはなりません。
最初に戻って、最初の行で反転指定していない駒を含む列を考えると、この列は最初の行の駒を除いて表であり、この列を裏にするためには反転指定する最初の行以外の駒の総数は奇数でなくてはならないことが以下のように示せます。
最初の行で反転指定していない駒を含む列に注目します。
a)この列の駒の反転指定の数が偶数のとき。
この列は最初の行の駒を除いて表であることから、残りの行毎の反転指定の駒の数は奇数でなくてはなりません。
残りの行は奇数のため、反転指定する残りの駒の総数は、列の反転指定の駒を合わせ奇数となります。
b)この列の駒の反転指定の数が奇数のとき。
この列は裏になっていることから、残りの行毎の反転指定の駒の数は偶数でなくてはなりません。
よってこの場合も反転指定する残りの駒の総数は、列の反転指定の駒を合わせ奇数となります。
したがって（２）の場合、盤面のすべての駒を裏にすることはできません。
以上により、横（行方向）が奇数、縦（列方向）が偶数の場合の最短手数は一行の駒をすべて反転指定することであることが証明されました。
また、両方向とも偶数の場合、上記と同様な方法で反転指定される行、または列は、その行または列のすべての駒が反転指定されなければならないことが示されます。
盤面のすべての駒を裏にするため、少なくとも１つの駒は反転指定しなければなりません。
ここからすべての行、列のすべての駒が反転指定されなければならないことが示されます。
全体の駒を反転指定すれば盤面のすべての駒が裏となることから、この方法が唯１つの手であることが証明できました。
縦横とも偶数の場合、反転指定される行、または列は、その行または列のすべての駒が反転指定されなければならないことの証明。
（１）最初の行で反転指定した駒の数が偶数の場合。
この行の駒は表になっているため、すべてを裏にするために各列ごとに奇数の駒を反転指定しなければなりません。
列の数は偶数のため、反転指定する残りの駒の総数は偶数でなくてはなりません。
最初に戻って、最初の行で反転指定していない駒を含む列を考えると、この列は表であり、この列を裏にするためには反転指定する最初の行以外の駒の総数は奇数でなくてはならないことが以下のように示せます。
最初の行で反転指定していない駒を含む列に注目します。
a)この列の駒の反転指定の数が偶数のとき。
この列は表であることから、残りの行毎の反転指定の駒の数は奇数でなくてはなりません。
残りの行は奇数のため、反転指定する残りの駒の総数は、列の反転指定の駒を含め奇数となります。
b)この列の駒の反転指定の数が奇数のとき。
この列は裏になっていることから、残りの行毎の反転指定の駒の数は偶数でなくてはなりません。
よってこの場合も反転指定する残りの駒の総数は、列の反転指定の駒を含め奇数となります。
したがって（１）の場合、盤面のすべての駒を裏にすることはできません。
（２）最初の行で反転指定した駒の数が奇数の場合。
上の（２）と全く同じに盤面のすべての駒を裏にすることはできないことが示されます。
◆ 問題へもどる
◆ 今週の問題へ