◆東京都 明 さんからの解答
【問題１】
ー ー ー ｜ ｜ ー ー ｜ ｜ ｜ ー ー ｜ ｜ ー ー ー＜できるだけ少ないマッチ棒を取り去って長方形をなくするための方針＞
まず全体図形の最外周を除いて、マッチ棒でできた図形の内部を、マッチ棒を取り去ってできる多角形（長方形でない）で埋めることを考えます。
多角形に含まれている単位の正方形の数をＫとすると、
取り去らなければならないマッチ棒は最低Ｋ−１本です。
従って、全体図形を埋めた多角形の数が大きいほど、取り去るマッチ棒の数は少なくて済みます。
このため、出来るだけ小さい多角形で図形の内部を埋めることで、取り去るマッチ棒の数を少なくすることができます。
長方形でない多角形の最小のものは下図の『 状の形です。
ー ー ｜ ｜ ー ｜ ｜ ーこの『 パターンで、しかも『 』の組み合わせ等で長方形ができないように図形の内部を埋めることができれば、取り去るマッチ棒の数を最小にできます。
【問題２】
ー ー ー ー ｜ ｜ ｜ ー ー ｜ ｜ ｜ ｜ ー ー ー ｜ ｜ ｜ ｜ ー ー ｜ ｜ ｜ ー ー ー ー【おまけ１・２】
ｎ×ｎの場合の長方形の個数を求めます。
ｎ×ｎの横の境界線と縦の境界線（各 ｎ＋１本）に着目します。
任意の一つの長方形（正方形も含む）は、一組の横の２本の境界線と縦の２本の境界線により構成されます。
逆に一組の横の２本の境界線と縦の２本の境界線は唯一つの長方形を構成します。
従って長方形の数は、横のｎ＋１本の境界線から２本を選び、さらに縦のｎ＋１本の境界線から２本を選ぶ場合の数に等しくなります。
よって、ｎ×ｎの場合の長方形の個数は
| n+1Ｃ2×n+1Ｃ2＝ | ( | n(n+1) 2 | ) | 2 |
５×５の場合 １８本
ー ー ー ー ー ｜ ｜ ｜ ー ー ー ｜ ｜ ｜ ｜ ｜ ー ー ー ｜ ｜ ｜ ｜ ｜ ー ー ー ｜ ｜ ｜ ｜ ｜ ー ー ｜ ｜ ｜ ー ー ー ー ー６×６の場合 ２５本
ー ー ー ー ー ー ｜ ｜ ｜ ー ー ー ｜ ｜ ｜ ｜ ｜ ｜ ー ー ー ー ｜ ｜ ｜ ｜ ｜ ー ー ー ー ｜ ｜ ｜ ｜ ｜ ー ー ー ー ｜ ｜ ｜ ｜ ｜ ｜ ー ー ー ｜ ｜ ｜ ｜ ー ー ー ー ー ー７×７の場合 ３４本
ー ー ー ー ー ー ー ｜ ｜ ｜ ｜ ー ー ー ー ｜ ｜ ｜ ｜ ｜ ｜ ー ー ー ー ー ｜ ｜ ｜ ｜ ｜ ｜ ー ー ー ー ｜ ｜ ｜ ｜ ｜ ｜ ー ー ー ー ー ｜ ｜ ｜ ｜ ｜ ｜ ー ー ー ー ｜ ｜ ｜ ｜ ｜ ｜ ｜ ー ー ー ｜ ｜ ｜ ｜ ー ー ー ー ー ー ー８×８の場合 ４３本
ー ー ー ー ー ー ー ー ｜ ｜ ｜ ｜ ｜ ー ー ー ー ｜ ｜ ｜ ｜ ｜ ｜ ｜ ー ー ー ー ー ー ｜ ｜ ｜ ｜ ｜ ｜ ｜ ー ー ー ー ｜ ｜ ｜ ｜ ｜ ｜ ー ー ー ー ー ー ー ｜ ｜ ｜ ｜ ｜ ｜ ー ー ー ー ｜ ｜ ｜ ｜ ｜ ｜ ｜ ー ー ー ー ー ー ｜ ｜ ｜ ｜ ｜ ｜ ｜ ー ー ー ー ｜ ｜ ｜ ｜ ｜ ー ー ー ー ー ー ー ー【おまけ４】
まず、ｎ×ｎの場合に、長方形をなくするために取り去らなければならないマッチ棒の最低本数の下限値を求めます。
・ｎが偶数のとき
| 『 の多角形の数は最大で[ | ｎ2 ３ | ]。 |
この時、全体図形の内部で取り去らなければならないマッチ棒の数は
| [ | ｎ2 ３ | ]×２。 |
| [ | ｎ2 ３ | ]×２＋１ となります。 |
| また | ｎ2 ３ | の剰余は１または０です。 |
これが最外周に付いていれば、１本のマッチ棒を取り去ることにより、単位正方形と最外周の正方形を同時になくすことができます。
| 従って、下限値は [ | ｎ2 ３ | ]×２＋１ となります。 |
・ｎが奇数のとき
| 『 の多角形の数は最大で [ | ｎ2 ３ | ]。 |
ところが最外周の辺の単位正方形の数が奇数のため、各辺で『 を置く場所を偶数にするため、孤立正方形が少なくとも２個（全体図形の対角のコーナーに１個ずつ）必要です。
| ｎ2 ３ | が割り切れるとき、すなわちｎが３の倍数のとき、 |
| 下限値は [ | ｎ2 ３ | ]×２＋１となります。 |
| ｎ2 ３ | が割り切れないとき、すなわちｎが３の倍数でないとき、 |
| 下限値は [ | ｎ2 ３ | ]×２＋２となります。 |
下限値は以上のとおりですが、次に数学的帰納法を使って、一般のｎに対し、下限値のマッチ棒を取り去って、求める配置が得られることを示します。
・ｎが偶数のとき
【問題２】および【おまけ３】で求めた配置を基本として、
（ｎ＋６）×（ｎ＋６）がまた下限値により実現できることを示すことで、
すべてのｎ≧４の偶数で実現できることを示します。
まず、６×６は【おまけ３】で求めたように１２個の『 で完全に埋めることができます。
『 を下図で表すと、６×６を『 で埋めた図形は＜図１＞のようになります。
（若干紛らわしい図ですが角から追っていくと『 を切り出せます。）
『 の表現図形
・ー ｜＜図１＞
・ー・ーー・ ｜｜｜・ー｜ ｜・ー｜ー・ ・ー｜ー・｜ ｜ー・｜｜｜ ・ーー・ー・次にｎをｎ≧４の偶数として６×ｎの図形は＜図２＞のように『 で完全に埋めることができます。
・ーー・ ｜・ー｜ ｜｜ー・ ・ー｜｜ ｜ー・｜ ・ーー・６×８
・ー・ー・ーー・ ｜｜｜｜｜・ー｜ ｜・ー・ー｜ー・ ・ー｜ー・ー・｜ ｜ー・｜｜｜｜｜ ・ーー・ー・ー・以下同一パターンの繰り返しで６×ｎを構成できます。
・ー・ー・ー ー・ ｜｜｜｜｜ ・ー｜ ｜・ー・ー ｜ー・ ・ー｜ー・ ー・｜ ｜ー・｜｜｜ ｜｜ ・ーー・ー・ ー・次に、上の６×ｎの図形２個と６×６の図形１個で、＜図３＞の図形を作ります。
＜図３＞
ーーーーーー ーーーーーーーーーー ｜・・・・・・｜｜・・・ ・・・・｜ ｜・・・・・・｜｜・・・ ・・・・｜ ｎ×６ ｎ×ｎ ｜・・・・・・｜｜・・・ ・・・・｜ ｜・・・・・・｜｜・・・ ・・・・｜ ーーーーーー ーーーーーーーーーー ーーーーーー ーーーーーーーーーー ｜・・・・・・｜｜・・・ ・・・・｜ ｜・・・・・・｜｜・・・ ・・・・｜ ｜・・・・・・｜｜・・・ ・・・・｜ ｜・６×６・・｜｜・・・６×ｎ・・・・｜ ｜・・・・・・｜｜・・・ ・・・・｜ ｜・・・・・・｜｜・・・ ・・・・｜ ーーーーーー ーーーーーーーーーー以上で（ｎ＋６）×（ｎ＋６）の配置ができますが、最後に４つのブロックを結合（４つの長方形を１つにする）します。
＜図４＞
｜｜ ー・・ー ー・・ー ｜｜ ー ー ｜ ｜ ｜ ー ー ｜ ｜ ｜ ー ー ー ー ｜ ｜ ｜ ー ｜ ー ｜ ｜ ｜ ー ー＜図４＞の部分を＜図５＞のようにすれば結合ができます。
＜図５＞
・ー ｜｜ー・ ・ー｜｜ ー・ ー ー ｜ ｜ ー ー ー ｜ ｜ ｜ ｜ ー ー ｜ ｜ ｜ ｜ ー ー ー ｜ ｜ ー ー以上で（ｎ＋６）×（ｎ＋６）の単一の配置ができました。
最後に、（もしあれば）右上角の仲間外れの正方形の最外周のマッチ棒を除くことにより、
（ｎ＋６）×（ｎ＋６）の長方形のない配置が実現し、孤立正方形があれば、右上角に配置されたままです。
| この時、取り除いたマッチ棒の数は[ | (ｎ＋６)2 ３ | ]×２＋１ です。 |
| [ | ｎ2 ３ | ]×２＋１本のマッチ棒を取り除くことにより、 |
| なおｎ＝２でも、取り除くマッチ棒の数は[ | ｎ2 ３ | ]×２＋１となっています。 |
・ｎが奇数のとき
ｎ≧２の偶数の場合のｎ×ｎを基本として、（ｎ＋３）×（ｎ＋３）の配置を考えます。
このために＜図６＞の配置を用意します。
ここで辺の数はｎ＋３です。
また、×は孤立正方形を表します。
＜図６＞
・ー× ｜ー・ ・ー｜ ｜ー・ ・ー｜ ｜ ー・ ・ー｜｜ー・ー・ ー・ー・ー・× ｜｜ー・｜｜｜｜ ｜｜｜｜｜｜｜ ×・ーー・ー・ ー・ー・ー・ー・この配置のスペース部分にｎ×ｎ（ｎ≧２の偶数）の上で実現した図形を配置します。
ｎが３の倍数のときはｎ×ｎの図形に孤立正方形はなく、
＜図６＞の×の３つの孤立正方形をなくしても、
| 取り去るマッチ棒の数は[ | (ｎ＋３)2 ３ | ]×２＋１ で済みます。 |
| 結局、取り去るマッチ棒の数は[ | (ｎ＋３)2 ３ | ]×２＋２となります。 |
以上により、下限値のマッチ棒を取り去ることで、求める配置が実現できることが示されました。
またｎ＝３のときも
| [ | ｎ2 ３ | ]×２＋１本のマッチ棒を取り去れば長方形をなくすることができました。 |
| ｎ≧２が偶数または３の倍数のとき、[ | ｎ2 ３ | ]×２＋１ |
| それ以外のとき、[ | ｎ2 ３ | ]×２＋２ |
いろいろなｎの配置をいじり回してようやく証明に至りました。
この証明は実証的な泥臭い方法で、もう少し単純明快なやり方があるような気がするのですが・・・。
◆愛知県 Y.M.Ojisan さんからの解答
【問題１】
初期長方形 個 取り除いたマッチ棒 本
現在の形
【問題２】
初期長方形 個 取り除いたマッチ棒 本
現在の形
【おまけ１、２】
（ｎ＋１Ｃ２）２
∵ 長方形は平行な２辺の２組で囲まれており、選ぶべき平行線は各組ｎ＋１本あるから。
【おまけ３】
（１）５×５
初期長方形 個 取り除いたマッチ棒 本
現在の形
（２）６×６
初期長方形 個 取り除いたマッチ棒 本
現在の形
（３）７×７
初期長方形 個 取り除いたマッチ棒 本
現在の形
（４）２×２
初期長方形 個 取り除いたマッチ棒 本
現在の形
【おまけ４】
| （１）ｎが偶数のとき ｎ | ２ | −[ | ｎ２−１ ３ | ] |
| （２）ｎが奇数のとき ｎ | ２ | −[ | ｎ２−２ ３ | ] |
∵ 【必要性】
（１）全般およびｎが偶数のとき
一番大きなｎ×ｎの正方形を消去するために外周の少なくとも１本をとる必要があります。
このとき１×１の正方形が１個消去され、１×１は残りｎ２−１個となります。
これらを効率的に消去するために、内部の１本をとると１×１の正方形が２個減りますが、これらで構成された１×２の長方形は残っています。
そこでもう一本、長さ２の側の一本をとる必要があります。
これの手順により、全部でＬ型トロミノ状につながった３個の１×１の正方形が消去されます。
つまり１×１の正方形３個につき、少なくとも２本の内部マッチをとらなければなりません。
| Ｌ型トロミノの数は最大 Ｔ＝[ | ｎ２−１ ３ | ] です。 |
| 従って、Ｌ型トロミノの数は最大 Ｔ’＝[ | ｎ２−２ ３ | ] です。 |
◆ 問題へもどる
◆ 今週の問題へ
数学の部屋へもどる