オセロ 
お正月のＴＶ特番を見ていたら、次のようなパズルが出題されていた。
５×５のオセロ盤があり、２５個の駒がすべて裏返っている。
（TVでは、３×３であった。）
１枚の駒の表裏を変えると、その駒の縦・横の全ての駒も一
斉に表裏を変えるものとする。
（オセロでは、斜めも変わるが、このパズルでは考えないこと
にする。）
２５個の駒を全て表にするには、最低何手必要であろうか？
実際に、Ｆｌａｓｈ で、駒を裏返して遊んでみよう！
Ｆｌａｓｈ 版は、こちら ＨＴＭＬ 版は、こちら をクリックしてください。
セキュリティ保護のため、コンピュータにアクセスできるアクティブ コンテンツが表示されないように、
Ｉｎｔｅｒｎｅｔ Ｅｘｐｌｏｒｅｒ で制限していると、ＨＴＭＬ版、Ｆｌａｓｈ版ともに見られません。ブロックされている
コンテンツを許可してください。（すみません、自己の責任でお願いします。）
（答） ５手あれば十分。次のようにやればよい。
 |
→ |  |
→ |  |
→ |  |
→ |  |
奇数×奇数のオセロ盤では、常にこのような手順で裏返すことが可能であるが、
偶数×偶数のオセロ盤では、果たして、このようなパズルは成立するのであろうか？
（追記） 偶数×偶数のオセロ盤でも、このようなパズルは成立する。
たとえば、２×２のオセロ盤の場合、４手あれば十分である。
 |
→ |  |
→ |  |
→ |  |
各マス目毎に（上記では、行列（ａｍｎ）と考えて、ａ11→ａ12→ａ21→ａ22 の順に）駒を
裏返せばよい。実は、順番は任意でよい。大切な所は、全てのマス目において１回だ
け操作を行うということである。
４×４のオセロ盤の場合、１６手あれば十分である。
その方法は、２×２のオセロ盤の場合と同様である。
簡単な試算から、この１６手が最短手数であると確信している。（証明は、未だ！）
一般に、ｎ が偶数のとき、ｎ×ｎ のオセロ盤の場合、ｎ2手あれば十分である。
もちろん、ｎ が奇数のとき、ｎ×ｎ のオセロ盤の場合、ｎ手あれば十分である。
攻略法さんが、上記で示された一般解を考察されました。（平成２２年１２月１６日付け）
Nが奇数の場合
「同じ行（または列）すべてを１回ずつ（順番は任意）」で裏返すと、それに伴なう列（または
行）では、１回のみ裏返る。他の列（または行）は裏返らない。
また、その数はいくつ在ってもよい。
ｊ列
×× ×●× × ┐
×× ×●× × │←いくつ在ってもよい
：
：
×× ×●× × ┘
i行 ●●…●●●…●
×× ×●× × ┐
： ：
×× ×●× ×
│←いくつ在ってもよい
×× ×●× ×
┘
※ 1(n)×N（またはN×1(n)）と記す。1(n)の意味は「束ねる」とする。
したがって、列（または行）に対して、１回ずつの裏返しによるN手が必要となる。順番は任
意でよい。このとき、N手は奇数なので、その１行（または１列）もすべて裏返っている。
したがって、N手となる。
Nが偶数の場合
1(n)×N（またはN×1(n)）に分割すると、N通りの領域ができる。
1 2 3 N
1┌─┬─┬─┬ … ┬─┐
└─┴─┴─┴ … ┴─┘
2┌─┬─┬─┬ …
┬─┐
└─┴─┴─┴ … ┴─┘
：
N┌─┬─┬─┬ … ┬─┐
└─┴─┴─┴ …
┴─┘
ある領域で、奇数の場合の操作を行うと、この領域を除いてすべて裏返っている。（１回目）
※操作は、この場合「この領域は、そのまま。他は、裏返る」を意味する。
次に別の領域で、同操作を行うと、先の領域とこの領域のみが裏返る。（２回目）
※この領域は、１回目で裏返っている→裏返ったまま
※先の領域は、１回目で元のまま→裏返る
※他の領域は、１回目で裏返っている→元に戻る
同様に
次に別の領域で、同操作を行うと、先の２つの領域とこの領域を除いて裏返る。（３回目）
次に別の領域で、同操作を行うと、先の３つの領域とこの領域のみ裏返る。（４回目）
これを続けると
(２ｋ−１)回目で、先の(２ｋ−２)個の領域とこの領域を除いて裏返る。
２ｋ回目で、先の(２ｋ−１)個の領域とこの領域のみ裏返る。
また、領域を選択する順番は任意でよい。
各領域を１回ずつ選択すると、N回目ですべて領域は選択されて、このときすべて裏返って
いる。したがって、N2手となる。
M行N列の場合
・Ｍ、Ｎのどちらか１つが奇数なら、それが仮にＭなら、Ｍ手。
手順.
1≦ｋ≦Nなる列ｋを１つ選び、その列すべてを１回ずつ選択する（順番は任意）
・共に奇数なら、Ｍｉｎ(Ｍ，Ｎ)手。 手順 同上
・共に偶数なら、Ｍ・Ｎ手。 手順 すべてのマスを１回ずつ選択する（順番は任意）