この記事は「
日曜数学 Advent Calendar 2022
」の 12月12日分の記事になります。
「12月12日」は、月と日を入れ替えても同じ日付になりますね!つまり不変・・・!!
……というわけで、この記事では不変量を使ってとある数学の問題を解いてみたいと思います。
(2022.12.12 追記)
※ 子葉さんのコメントでのご指摘にあわせて記号を修正しました。
不変量とは、たとえば「合同な図形の面積」とか「相似な図形の頂点数」のようなもののことです。ちゃんと定義するとこんな感じです。(Wikipedia調べ)
不変量(ふへんりょう、invariant)とは、数学的対象を特徴付ける別種の数学的対象のことである。一般に、不変量は数や多項式など、不変量同士の同型性判定がもとの対象の同型性判定より簡単であるものをとる。良い不変量とは、簡単に計算でき、かつなるべく強い同型性判別能力をもつものである。
さて、この記事で挑戦する問題はみよしじゅんいち (@nosiika)さんの考案した次のようなものです。
Pペントミノからモノミノを引くと、テトロミノ5種のうち、Tテトロミノ、Lテトロミノ、Oテトロミノ、Sテトロミノの4種を作ることができる。引き算でテトロミノ5種を作ることができるようなポリオミノの組は存在するだろうか?
まず用語の説明をします。同じ大きさの正方形を辺に沿ってつなげた形を総称してポリオミノといいます。特に、正方形
テトロミノは、裏返しや回転で一致するものを同一視すると5種類あり、区別するために似た形のアルファベットを用いてそれぞれ I型・O型・L型・S型・T型 と呼んだりします。
テトロミノの I・O・L・S・T
そして、「Pペントミノからモノミノを引くと、テトロミノ5種のうち、Tテトロミノ、Lテトロミノ、Oテトロミノ、Sテトロミノの4種を作ることができる。」というのは、次の図のようにすれば、Pペントミノ(アルファベットのPに似た形のペントミノのことです。)からモノミノを削ることで4種のテトロミノが作れるということです。
PペントミノからO・L・S・Tのテトロミノが削り出せる
問題は、このようにポリオミノを「引き算」のように削った時に、テトロミノ
とりあえず試行錯誤してみると、たとえばヘキソミノからドミノを削って
ヘキソミノから I・O・L のテトロミノが削り出せる
しかしながら、
しばらくやってみると「無理なのでは?」という気がしてきます。
となれば、不可能であることを証明したくなりますね!
さて、最初に考えたのは以前「欠損チェスボードにドミノを敷き詰められるか」のときに使った、チェスボードの黒白のマスを数える方法でした。
そのときの記事を一部引用します。
欠損チェス盤にドミノ・L型トロミノ・I型トロミノを敷き詰めたい
=====(ここから引用)=====
欠損チェスボードにドミノを敷き詰められるか
=====(引用おわり)=====
このときと同じように、市松模様の上にテトロミノを並べてみます。
市松模様の上にテトロミノを配置する
そして、「テトロミノと重なる黒マスと白マスの個数の差」という量を考えます。
すると、その量は、テトロミノを平行移動・裏返し・回転しても変化しないことがわかります。つまり不変量……!!(伏線回収)
少し考えれば、テトロミノに限らず、一般的にポリオミノ全てについて「テトロミノと重なる黒マスと白マスの個数の差」は不変量となることがわかります。
ここでは、「ポリオミノ
表にするとこんな感じになります。
N(I) | N(O) | N(L) | N(S) | N(T) |
---|---|---|---|---|
0 | 0 | 0 | 0 | 2 |
次に、ポリオミノの「引き算」をすると、
となります。
したがって、「Tテトロミノと、T以外のテトロミノをどちらも削り出せるポリオミノ
上記の式を満たす組み合わせを考えると
しかありえないことがわかります。
突然ですが、正方形の数が偶数のポリオミノを「偶数ミノ」、奇数のポリオミノを「奇数ミノ」と呼ぶことにします。すると、次のようになります。
偶数を2つの整数に分けるとその偶奇が一致するから、その2つに分けた整数の差は偶数となる。
また、奇数を2つの整数に分けるとその偶奇は一致しないから、その2つに分けた整数の差も奇数となる。
したがって、
ここまでで、つぎのことがわかりました。
冒頭の例もこれを満たしていることを確認してください。
PペントミノからO・L・S・Tのテトロミノが削り出せる(再掲)
このアプローチでは、条件をみたすポリオミノの組合せが存在する場合には「奇数ミノと奇数ミノ」であること、特に、「黒マスと白マスの差が
しかし、不変量はこれだけではありません。他の不変量が使えないかさらに考えます。
不変量としてはその他にも、ポリオミノの辺や頂点や内角に注目していろいろなものを考えることができます。
試行錯誤の結果、次のようなものを考えてみることにしました。
まず縦縞、横縞にチェス盤の模様を塗り替えて、そこにポリオミノを配置します。
縦縞の黒白差と、横縞の黒白差
縦縞の上にポリオミノを置いたときの「黒マスの数と白マスの数の差」を
盤上に配置したポリオミノ
そこで、テトロミノを
各テトロミノについて表にすると次のとおり。
もう少しシンプルにすることができそうです。
表にすると
ここからは、
しばらくは、主に
ここで、
偶数を2つの整数に分けるとその偶奇が一致するから、その2つに分けた整数の差は偶数となる。
また、奇数を2つの整数に分けるとその偶奇は一致しないから、その2つに分けた整数の差も奇数となる。
次に、ポリオミノの「引き算」をすると、
※ 複号は
となります。
複号になっているのは、
今、ポリオミノ
(※ ここでいろいろなテトロミノの中から
I_1テトロミノとOテトロミノを削り出すポリオミノの例
このとき、
だったととすると、
となります。
そこで場合分けして考えます。。
を使って式を立てると
これらすべてを満たす必要があります。(
前半
補題
を使って式を立てると
これらすべてを満たす必要があります。(
下
したがって、補題
ここまでで、
ですから、「
まとめると、結局、次のことがわかったことになります。
『
これで、この問題の答えができました!
(解答)
引き算でテトロミノ5種を作ることができるようなポリオミノの組は存在しない。
『
したがって、引き算でテトロミノ
ついに答えが出ました!
「条件を満たすポリオミノの組合せは存在しない」!
めでたしめでたし。
……
……
……のはずだったのですが。
みよしじゅんいち (@nosiika)さんから衝撃の追加問題が。
まだ十分理解できてはいないのですが、パリティ違いのTを除外した、I、L、O、Sができる可能性はありそうな感じですか?
つまり、「
先ほどと同様に考えると、もしそのようなポリオミノの組合せ
又は
でなければいけないことまではわかりますが、そのような
試行錯誤したところでは、おそらく「不可能」と予想しています……が、まだ証明はできていません。
というわけで、私が主に日曜数学活動をしているTwitter上での成果の一部をまとめさせていただきました。
当初の問題には答えが出てスッキリしましたが、最後の追加問題はまだ答えが出いません。
よろしければ皆さんもいっしょに考えてみませんか?
「条件を満たすポリオミノの組合せを発見する」か「条件を満たすポリオミノの組合せが存在しないことを証明する」か、どちらのルートを進むべきかすらまだ予想できないホットな話題です。
特に期限もないので好きな時に好きなだけ考えられるのが日曜数学の醍醐味です。
これを読んだ皆さんも是非素敵な日曜数学ライフを送ってくださいね!
最後に、この記事の元ネタとなったツイートたちの一部をご紹介します。みよしじゅんいち (@nosiika)さん、Taichi AOKI (@aoki_taichi)さん、TokusiN (@toku51n)さんとのやり取りがなければこの記事はできませんでした。ありがとうございました!
Pペントミノからモノミノを引くと、テトロミノ5種のうち、Tテトロミノ、Lテトロミノ、Oテトロミノ、Sテトロミノの4種を作ることができる。引き算でテトロミノ5種を作ることができるようなポリオミノの組は存在するだろうか?
— みよしじゅんいち (@nosiika) October 31, 2022
実はこれだけで不可能性いえたりしませんかね。 https://t.co/pzumubkn6P
— Taichi AOKI (@aoki_taichi) October 31, 2022
チェス盤のようにテトロミノを黒白に塗り分けると、Tは黒白の差が2、I・O・L・Sは0。したがって、削る方を黒白に塗り分けたときの黒白の差は1でなければいけません。
— apu (@apu_yokai) October 31, 2022
もしかしてOテトロミノとIテトロミノを削り出しでできるのはPっぽいヘキソミノからドミノを削ったときだけだったりしないかしら? https://t.co/wF69kxozuq
— Taichi AOKI (@aoki_taichi) October 31, 2022
これに正方形の枠を追加するトリッキーな反例がありますね。
— TokusiN (@toku51n) October 31, 2022
おお、なるほど
— apu (@apu_yokai) October 31, 2022
…可能なパターンは全部偶数ですね
偶数でなければ無理である事を証明できれば元の主張も証明できますが🤔
通勤時間にずっとこれ考えてだんだけど、OミノとIミノを削り出しできるのは偶数ミノを削ったときに限られる事を証明できた(と思う)
— apu (@apu_yokai) November 9, 2022
Tミノとそれ以外の組み合わせは奇数ミノを削ったときに限られるので、全てのテトロミノを削り出せるようなポリオミノは存在しない https://t.co/OwJhmOLhXQ
OテトロミノとIテトロミノを削り出しでできるのは元となるポリオミノから偶数ミノを削ったときだけ
— apu (@apu_yokai) November 9, 2022
凄まじく雑だけど伝われ…! https://t.co/OwJhmOLhXQ pic.twitter.com/pgYyueuNgD
まだ十分理解できてはいないのですが、パリティ違いのTを除外した、I、L、O、Sができる可能性はありそうな感じですか?
— みよしじゅんいち (@nosiika) November 9, 2022