今回のテーマは「テトリス」。
ゲームで御馴染みのやつです。
・問題
下の図のような白いマス目を、図の下に有る3種類のブロックで
埋める時に、凸型ブロックは最低何個必要か？
ただ解くだけならコマ大生のように、
力づくでやれば解けない事はありません。
ただ最低の個数に関しての理由付けが難しくなります。
先に理由付けを考えるとシステムによって
答えが浮かび上がりますので、後はそれが実行できるかがポイント。
類題としてタイル貼りの問題があるのですが、
これを知っているとシステムが理解しやすいです。
8×8のタイルの右上と左下を
取り除いた図について、
ドミノ（1×2の形、図の右側の物）を
敷きつめる事が出来るか？
これはかなり有名な問題でして、
ある方法を使うと一瞬にして
「出来ない」ことが導けます。
それが下図のように
市松模様に色を付けること。
色を付けた図では、
灰色が32箇所、白色が30箇所です。
しかし、1×2のタイルを置く際には、
灰色1個と白色1個をセットで
埋める事になりますから、
灰色と白色の個数が合っていない
図形では、ドミノを敷きつめる事は
100%不可能なのです。
（ちなみに灰色と白色の個数が同じでも
不可能な図形は有ります）
タイル貼りの問題と同様に、市松模様に色を塗ると
灰色が38個、白色が34個です。
またブロックについて見ると、凸型以外のブロックは
どのように置いても白と灰色が2つずつ消す事になりますが、
凸型だけはどちらかの色を3つ消す事になります。
灰と白の個数の差が4つで、凸型が2つ差をつけるのですから、
凸は最低2個は必要になります。
最低2個は可能性であるので、後は置けるかどうか……
タイル張りの問題は知っていたけど、
この問題に応用できるとは気付きませんでした。
解くのは簡単だけども、「何故か？」を考えるのは難しい問題って
作るのは難しいのですけど……
今回の問題は面白い問題だったと思います。
PR
