チェス盤にドミノを敷き詰めるパズル(解答編)

軽いパズルです。【まずは問題を読んでいただいた方がよろしい】かと思います。

切り欠いたチェス盤に、適当にドミノを並べてみると?
(クリックすると、大きい画像を開きます)

チェス盤(8×8マス)から右上と左下を切り欠き、適当にドミノ(1×2、または2×1)を並べてみると、右下4マス(元々白が3マス(赤く着色)、黒1マス)を並べる事ができませんでしたが…?

いや、これは適当に並べたのが悪かった!戦略をもう少し考えてやれば並べる事が可能なのではないか…?



それでは解答です。ご覧になりたい方は下の方にスクロールしてください。






















本文では適当に並べた場合を示しましたが、他のやり方を一つ一つ全て試していっても(あまりにも数が多すぎて挫折すると思いますが…その辺りの「指数爆発」については【以前に説明した量子コンピュータの記事をご覧ください】)「絶対に」ドミノで埋める事はできないのです。

それは何故か?本文の適当に並べた結果、残りマスがどうなっているかを見る事で答えが見えてきます。

チェス盤とドミノの性質を考えてみましょう。1個のドミノを置いた時、チェス盤の黒マスと白マスを一度に覆う事が可能です。逆に言いますと、1個のドミノで白マスを2マス、または黒マスを2マス同時に覆う事は絶対にできないのです。

8×8マスのチェス盤の時は黒が32マスで白が32マス。【問題編でも示した通り、この場合はドミノで埋め尽くす事が可能】です。

しかし、右上と左下を切り欠いたチェス盤だとどうか?黒が30マスで白が32マス…すなわち、どれだけ戦略的に並べていっても黒マスが先に埋まってしまい、最後に白マスが2マス残ってしまうのです。

ドミノの性質から白マスを同時に埋める事は不可能。すなわち右上と左下を切り欠いたチェス盤をドミノで埋め尽くす事は不可能という結論が得られるのです。

あらゆる場合を試そうとすると挫折するけれど、上手く工夫すれば一瞬で「不可能」と分かる。(本質は少し違うのですが)【P≠NPではなくP=NPかもしれない…と思わせる事例】と言えるでしょう。



このチェス盤を見ていて、【別の問題解説用に流用できるな…と思い付き】ました。
スポンサーサイト

テーマ : 今日のつぶやき。 - ジャンル : 日記

コメント
コメントの投稿
管理者にだけ表示を許可する