図形の埋め込み４　 　　　　　　　　　　　　　　　　　　　　　　　　　

　下図のような７×７のマス目の図形がある。

　　　　　　　　

　今、次の３種類の図形を何枚か用いて、上の図形を埋め尽くすことを考える。ただし、裏返
しや回転させて用いてもよい。また、使わない種類の図形があってもよいものとする。

	Ｏ-Type		Ｌ-Type		Ｚ-Type

　どのように組み合わせればいいだろうか？一例を示してください。





























（答）　次のように埋め尽くすことができる。

　　　

　上記の例で、Ｏ-Ｔｙｐｅ は用いず、Ｚ-Ｔｙｐｅ は１個だけ用いて、後はすべてＬ-Ｔｙｐｅ という
点が面白いですね！


　Dengan kesaktian Indukmu さんからのコメントです。（令和３年９月２日付け）

　題意を準拠したままで、「７×７のマス目の図形」から「９×９のマス目の図形」に変更した
場合には、どのように詰めたらよいのでしょうか？


　らすかるさんからのコメントです。（令和３年９月２日付け）

□□○○□□○○□
□□○○□□○□□
○○
○○
□□　7×7の図形を
□□　ここに入れる
○○
○□
□□

でよいと思います。

□□
□□

を使わないようにするならば、次のようにすればできますね。

□○○□□○○□□
□□○○□□○○□
○○
○□
□□　7×7の図形を
□○　ここに入れる
○○
○□
□□


　Dengan kesaktian Indukmu さんからのコメントです。（令和３年９月２日付け）

　らすかるさん、有り難うございます。７より大の任意の奇数について、

□□
□□

を使わないようにしながら詰めることができると納得いたしました。


（コメント）　ｎ＝７のときには１個のＺ-Ｔｙｐｅ を用いる必要がありましたが、ｎ＝９の場合は
　　　　　　すべてＬ-Ｔｙｐｅ のみで埋め尽くすことが可能なようです。一例として、

　　　　


　Dengan kesaktian Indukmu さんからのコメントです。（令和３年９月５日付け）

　上記の一例を拝見いたしました。 知人から教わった解とは異なっていました。上記の解に
は、２×６の長方形にＬ-Ｔｙｐｅを４個詰まっている領域がありますが、知人のそれにはその
ような領域が含まれていません。

　それはひとまずさておき、７×７にて L 15、S 1 のケースの別解をば。

　まず、７×７のどまんなかのマス以外の４８マスを１６個のＬで詰める解を作ります。回転対
称なのですぐに作れます。２×３の長方形ブロックを配置する感じになります。この長方形ブ
ロックを２個組み合わせて、４×３の長方形ブロックをつくり、これを４つ、回転対称に詰めれ
ばよいです。

　　　

　中央マスの■を、隣接するＬのうちのひとつに吸収させてＺを１個作れば出来上がりです。


（コメント）　なるほど！機械的に構成する方法があるんですね。美しいです．．．。


　DD++さんからのコメントです。（令和３年９月６日付け）

　ｎ＝７のときには１個のＺ-Ｔｙｐｅ を用いる必要がありました

　実はこれは偽で、O-Ｔｙｐｅ の方を使う解も存在します。L を 15 個使うところは共通です。
（絶対に L の使用個数が 15 であることは簡単に証明できます）


（コメント）　確かに、O-Ｔｙｐｅ の方を使う解も存在しますね。一例として、

　　


　Dengan kesaktian Indukmu さんからのコメントです。（令和３年９月６日付け）

　先日に投稿した L 15、Ｚ 1 の解に似た解として、L 15、O 1 の解の一つが見つかりました。

　LOZ 縛りから離れると、L 15、T 1 も得られます。

　マスを４つ繋げるピースには、あとは、□□□□ の I 型がありますね。

　L 15、I 1 は……、宿題として持ち帰ります。


　DD++さんからのコメントです。（令和３年９月６日付け）

　T や I を用いる話になると、L は 15 個とは限りませんし、そもそも 7x7 より小さい、例えば
5x5 を作れたりするので、別の問題という感が．．．。


　Dengan kesaktian Indukmu さんからのコメントです。（令和３年９月１０日付け）

　DD++さんがおっしゃるに

　（絶対に L の使用個数が 15 であることは簡単に証明できます）

とのことでした。凄く興味が引かれて、ああでもないこうでもないと色々な試行錯誤を繰り返
しました。

　ぜんぜん《簡単に》ではないのですけれども、一応のメドがついたようなつかないような、
そんなおぼつかない理屈をこねてみました。以下に記します。お願いできるようでしたなら
ば、是非、御批正くださいますようお願い申し上げます。

　７×７の各マスにひとつづつ、数値を付加します。下記に示します。

　　１０１０１０１
　　２０２０２０２
　　１０１０１０１
　　２０２０２０２
　　１０１０１０１
　　２０２０２０２
　　１０１０１０１

　この上にＺ型のピースを１個配置すると、置き方いかんに関わらずに、そのピースは必ず、
０を２個、１を１個、２を１個、合計４個の数値をカバーすることになります。

　一方、Ｌ型ピースの置き方には３種類あります。

　・第一番めの置き方では、０を２個、１を１個カバーする

　・第二番めの置き方では、０を２個、２を１個カバーする

　・第三番めの置き方では、０を１個、１を１個、、２を１個カバーする

　さて、Ｚ型ピースとＬ型ピースとで７×７のマスを埋め尽くしたとします。このときに使われた
各種のピースの個数を以下のように定義します。

　Ｚ型のピース ・・・　a個
　Ｌ型ピースの第一番め　・・・　b個
　Ｌ型ピースの第二番め　・・・　c個
　Ｌ型ピースの第三番め　・・・　d個

　０のマスは 21個 ありますので、次の等式が成り立ちます。

　　2*a+2*b+2*c+d = 21

　１のマスは 16個 ありますので、次の等式が成り立ちます。

　　a+b+d = 16

　２のマスは 12個 ありますので、次の等式が成り立ちます。

　　a+c+d = 12

　ここまでのまとめです。

　正の整数 a 、非負整数 b c d について、次の 3 本の等式が成り立っています。

　　2*a+2*b+2*c+d = 21　・・・　（イ）
　　a+b+d = 16　・・・　（ロ）
　　a+c+d = 12　・・・　（ハ）

　さて、これらの条件のもとで、a = 1 に限ることを証明したいわけです。

　（ロ）と（ハ）より、　b = c +4　・・・　（ニ）　を導けます。

　（ニ）を（イ）に代入して、　2*a+4*c+d = 13　・・・　（ホ）　が得られます。

　（ホ）を変形すると次のようになります。

　　(a +c +d)+a+3*c =13　・・・　（ヘ）

　（ヘ）と（ハ）より、　a+3*c = 1　・・・　（ト）　が得られます。

　（ト）で、aが正の整数、cが非負整数であったことを鑑みれば以下がわかります。

　　a = 1　、c = 0

すなわち、Ｚ型ピースは１個だけ使うことになりました。

＃もっと簡単な証明が欲しかったのですけれども．．．。

　ひとつ前のバージョンでは、

　　２０２０２０２
　　０１０１０１０
　　２０２０２０２
　　０１０１０１０
　　２０２０２０２
　　０１０１０１０
　　２０２０２０２

を使ったのですけれども、求めたい結論を得るためのステップが馬鹿みたいに長くてしんど
かったです。

　非負整数 a、b、c、正の整数 d について、

　　a+2*b+2*c+2*d = 24
　　a+b+d = 9
　　a+c+d = 16

が成り立つときに、d=1 を証明したいわけです。


　DD++さんからのコメントです。（令和３年９月１１日付け）

　＃もっと簡単な証明が欲しかったのですけれども．．．。

　その番号付けで言う「1」のところだけ注目すればもっと簡単に済みますよ。


　Dengan kesaktian Indukmu さんからのコメントです。（令和３年９月１１日付け）

　本当ですね！！嬉しい！！！有難うございました。

　　１０１０１０１
　　０００００００
　　１０１０１０１
　　０００００００
　　１０１０１０１
　　０００００００
　　１０１０１０１

において、ピースの配置の可能性を考えると、次の何れかである。

　Ｚ型[0001] 　・・・　a個
　Ｌ型[001]　・・・　b個
　Ｌ型[000]　・・・　c個

　０のマスは 33個 ありますので、　3*a+2*b+3*c = 33　・・・　（イ）

　１のマスは 16個 ありますので、　a+b = 16　・・・　（ロ）

　（ロ）より、　b = 16-a　なので、これを（イ）に代入して整理すると、　a+3*c = 1　から、

　c = 0　、a = 1 を得る。


（コメント）　Dengan kesaktian Indukmu さんの方法に触発されて、考えてみた。次の配置図

　　１０１０１０１
　　０００００００
　　１０１０１０１
　　０００００００
　　１０１０１０１
　　０００００００
　　１０１０１０１

において、　０は、３３マス、１は、１６マスを占める。

　Ｌ型[001または000]　・・・　ｘ個
　Ｚ型[0001]　・・・　ｙ個
　Ｏ型[0001]　・・・　ｚ個

で４９マスが埋め尽くされたものとすると、　３ｘ＋４ｙ＋４ｚ＝４９

　ｘ、ｙ、ｚは非負の整数なので、　３（ｘ−１５）＋４（ｙ＋ｚ−１）＝０　から、

　　ｘ＝１５−４ｋ　、ｙ＋ｚ＝３ｋ＋１　（ｋは整数）

　ｘ、ｙ、ｚは非負の整数なので、　−１/３≦ｋ≦１５/４　から、　ｋ＝０、１、２、３

　ｋ＝１　のとき、ｙ＋ｚ＝４　から、　０は１２マス、１は４マスの使用で、

　　残りは、０は２１マス、１は１２マスであるが、１が１２マスあることから、

　　０は２４マス以上が必要で、これは不可能。

　ｋ＝２　のとき、ｙ＋ｚ＝７　から、　０は２１マス、１は７マスの使用で、

　　残りは、０は１２マス、１は９マスであるが、１が９マスあることから、

　　０は１８マス以上が必要で、これは不可能。

　ｋ＝３　のとき、ｙ＋ｚ＝１０　から、　０は３０マス、１は１０マスの使用で、

　　残りは、０は３マス、１は６マスであるが、１が６マスあることから、

　　０は１２マス以上が必要で、これは不可能。

　以上から、残った可能性は、ｋ＝０　のときであるが、ｙ＋ｚ＝１　から、

　　０は３マス、１は１マスの使用で、残りは、０は３０マス、１は１５マスであるが、１が１５マス

　　あることから、０は３０マス以上が必要であるが、これは条件を満たす。

　したがって、Ｌ型は必ず１５個必要で、ｚ型またはＯ型は１個必要である。

（コメント）　題意を満たすためには、必ず１６ピースが必要で、１５、１４、１３（ピース）では
　　　　　　覆いきれないんですね！


　DD++さんからのコメントです。（令和３年９月１１日付け）

　実は、文字式すら要りません。「最低 16 ピース必要で面積が 49」と考えると、49-3*16 = 1
しか面積の余裕がないんです。


　Dengan kesaktian Indukmu さんからのコメントです。（令和３年９月１２日付け）

　「最低 16 ピース必要」というのは理解できません。面積 49 を覆うために、Z が 1 で L が
15 ならば 16 ピースですが、例えば、Z が 4 で L が 11 ならば 15 ピースなのでは……？

　この 15 ピースでは覆えないことを示したかったはずではありませんでしょうか。

　「最低 16 ピース必要」はどこから出てきたのでしょうか？


　DD++さんからのコメントです。（令和３年９月１１日付け）

　Dengan さんの番号付けで言う「1」のマスを 1 つのブロックで複数塞ぐことができませんの
で……。


　Dengan kesaktian Indukmu さんからのコメントです。（令和３年９月１２日付け）

　いやあ、すばらしいです。スカッとしました。


　Dengan kesaktian Indukmu さんからのコメントです。（令和３年９月１３日付け）

　n を２以上の自然数とします。縦 n マス、横 (n +1) マスになるように単位正方形のマスを
並べた長方形の盤面を考えます。(今までは縦 n マス、横 n  マスの正方形の盤面でしたが…)

　今、次の２種類の図形のピースを何枚か用いて、上の長方形の盤面を埋め尽くすことを
考える。ただし、裏返しや回転させて用いてもよい。（□は単位正方形とみなしてください。）

　長方形の盤面を、上の２種類のピースで埋め尽くしたときに、Ｌ型ピースの枚数をできるだ
け小さくしたい。（Ｚ型ピースの枚数をできるだけ大きくしたい）

　Ｌ型ピースの最小枚数を n で表してください。

　Ｌ型ピースとＺ型ピースとで、どのように埋め尽くすのかについての具体的な方法と、その
方法がベストであることを示したいというわけです。


　DD++さんからのコメントです。（令和３年９月１４日付け）

　より一般に、「片方が２以上の偶数、片方が３以上の奇数の長方形」である場合、L の最
小枚数は、「辺の長さのうち偶数である方」ですね。

　辺の長さを 2a と 2b-1 とすると、面積は 4ab-2a です。一方、奇数行奇数列目のマスは全
部で ab 個あり、これらを 1 枚で同時に複数塞ぐことはできないので、最低 ab 枚のピースが
必要です。

　全て Z を使うとすれば、面積が 2a オーバーします。よって、L は最低 2a 枚必要です。

　ところで、長さ 2a の辺を a 等分して幅 2 の長方形を a 個作り、それぞれの長方形の両
端に L を置き、残りを Z で埋めると、実際に L を 2a 枚しか使わずに条件を満たすことが
可能です。

　よって、最小枚数は 2a 枚です。


（コメント）　ａ＝２、ｂ＝３　として、上記を構成してみた。２×５の長方形は、両端をＬ２枚で抑
　　　　　　えて、間はＺで埋め尽くされる。Ｌの最小枚数は４枚である。

　　　　　　

　次のような場合もあるが、Ｌはやはり４枚必要である。

　　　　　


　Dengan kesaktian Indukmu さんからのコメントです。（令和３年９月１４日付け）

　DD++さんの、奇数×偶数の一般解を拝見いたしました。何度目になることでしょうか。
いやあ、素晴らしいです。

　出題のキッカケは、らすかるさんによる以下の図解からでした。

　次のように、左上にＬ字型ピースが２つ使われています。

□
□□
○○
・○

　これを縦方向に１マス分、縮めますと、次のようにＺ型ピースになります。

□
□□
・□

　以上で変形が終了しました。結果は次のようになります。

□○○□□○○□□
□□○○□□○○□
○□
○○　6×7の図形を
□○　ここに入れる
□□
○□
○○

その心は、6×7の図形に皮を被せて、8×9の図形を作れる。その際に増加するＬ字型ピー
スの個数は僅かに 2 個に抑えることができる、というものでした。

　この皮を元手に、ひとまわり大きな皮をつくるには、行方向にＺ型ピースをひとつ追加、列
方向にＺ型ピースをひとつ追加をすればよいことがわかります。Ｌ型ピースの個数は２個の
ままで増えません。同様に皮の大きさをどんどん大きくしていっても、一枚の皮のＬ型ピース
の個数は２個のままです。

　皮を何枚も何枚も重ね着させていって n 枚 を被せることを考えますと、皮一枚ごとにＬ型
ピースの個数は 2 個ですから、全体としては 2*n 個のＬ型ピースの増大が見込まれます。

　上のような考えに基づいて、次のようなお絵描きをしてみました。

　それぞれ、Ｌ型ピースのみで作られている２×３の長方形に一枚の皮を被せたもの、Ｌ型
ピースのみで作られている３×４の長方形に一枚の皮を被せたもの、となっています。

　n × (n+1) の盤面について考えたかったのですが、n が偶数のときと、n が奇数のときと
で、皮の作り方を変えたほうが……私にはわかりやすかったです。

　あとは、マトリョーシカのように入れ子をしていけばよいわけです。

　いずれにせよ、皮一枚につきＬ字が２個増えることには変わりません。Ｌの個数は、「辺の
長さのうち偶数である方」となっています。

　これが最小であることの証明は、 DD++ さんに以前ご教示頂いた手法で示せます。

＃偶数×偶数の長方形でどうなるのか、これから考えてみたいと思っています。やはり、ら
　すかるさんの皮を使いたいわけですが…最小性の証明をどうしたものか……はて……。


　Dengan kesaktian Indukmu さんからのコメントです。（令和３年９月１６日付け）

　偶数×偶数の盤でＺ型ピースの枚数を最大に、Ｌ型ピースの枚数を最小にする問題には、
全く参りました。何か新機軸がみつからないと…。そんな中でも、ひとつだけわかったことが
あります。

　n ≧ 3 のときに、 2*n 行 × 6 列の盤面において、Ｌ型ピースの枚数の、最小値の上界と
して 8 があるというものです。
(この条件下では、最小値は 12 てはないかと思っていましたので意外でした。)

　なお、この 8 が最小であるかどうかについては、まだ結論がありません。

　以下、図解です。

　同様なことをずっと続けられますが、Ｌの枚数は増加しません。


　DD++さんからのコメントです。（令和３年９月１６日付け）

　長方形の縦横の長さが 6 以上で、

　短い方の辺が複偶数であればその数そのもの、短い方の辺が単偶数であればその数＋２

で条件を満たすことは私の手元で達成しています。

　ただし、これが最小かどうかは難しいですね。


　Dengan kesaktian Indukmu さんからのコメントです。（令和３年９月１６日付け）

　素晴らしいですっ。うーん、複偶数ですか……

　８×８（片方は延長可）な図が手元にありまして。

◎◎□□■■□□
◎□□■■□□●
◎◎○○◎◎●●
◎○○●●◎□□
◎□□●■□□◇
◎◎□□■■◇◇
◎■■○○■◇●
◎◎■■○○●●

（これ、左端がアレなのでぐんぐん成長できます。）

《短い方の辺が複偶数であればその数そのもの》の一例になっていますね。


　Dengan kesaktian Indukmu さんからのコメントです。（令和３年９月１９日付け）

　６×８ だと綺麗なのがあるのでしたか…… なるほど。

△△▲▲△△
△５△▲１△
５５△△１１
５６▼▼２１
６６▼▽２２
６７▽▽３２
７７△▲３３
７△△▲▲３

において、L型ピース8枚のうち最上部の３組の

△△
△・

を

△△
△■
■■
■・

とすれば、高さが２伸びます。すなわち、

△△▲▲△△
△◎○▲●△
◎◎○○●●
◎５△○１●
５５△△１１
５６▼▼２１
６６▼▽２２
６７▽▽３２
７７△▲３３
７△△▲▲３

＃上の横幅が６（Ｌ型８枚）のほかに、８（Ｌ型８枚）、１０（Ｌ型１２枚）、１２（Ｌ型１２枚）のもの
　を用意すればいいのかも。


　Dengan kesaktian Indukmu さんからのコメントです。（令和３年１０月１日付け）

　偶数×偶数の盤面をＬ型ピースとＺ型ピースとで埋め尽くすときに、できるだけＬ型ピース
の枚数を少なくしたいときに、DD++さんがおっしゃるに

　短い方の辺が複偶数であればその数そのもの
　 短い方の辺が単偶数であればその数 +2

……がＬ型ピースの枚数であるとのことでした。

　具体的にどのように埋めたらよいのかについて改めて考えてみました。

　単偶数（６）のケース。

▼▼▽▽▼▼
▼●●▽●▼
１●３●●５
１１３３５５
▲１△３５▲
▲▲△△▲▲

※上辺のＬ型ピースのそれぞれをＬ型ピースとＺ型ピースとに置き換えることにより、背丈が
　伸びます。すなわち、

▼▼▽▽▼▼
▼０２▽４▼
００２２４４
０●●２●４
１●３●●５
１１３３５５
▲１△３５▲
▲▲△△▲▲

※この、背丈を伸ばす作業は再帰的に行うことが出来、その際にＬ型ピースの枚数が増え
　ないことから、以下が言えることとなります。

　短い方の辺が単偶数の６であれば、その数＋２、すなわち８枚のＬ型ピースがあれば、盤
面を覆いつくせる。

《上の図で●で表した２枚のピースを以後の説明の都合上、【余計もの】と呼びます。》


　単偶数（１０）のケース。

▽▽▼▼▽▽▼▼▽▽
▽０▼３６▽▼ＡＤ▽
００３３６６ＡＡＤＤ
０●３７７６ＡＢＥＤ
１●●４７７ＢＢＥＥ
１１４４８８Ｂ●●Ｅ
２１４５９８８Ｃ●Ｆ
２２５５９９ＣＣＦＦ
△２５▲△９Ｃ▲Ｆ△
△△▲▲△△▲▲△△


※背丈を伸ばす作業を同様に行うことが出来て、その際にＬ型ピースの枚数が増えないこと
　から、以下が言えることとなります。

　短い方の辺が単偶数の１０であれば、その数＋２、すなわち１２枚のＬ型ピースがあれば、
盤面を覆いつくせる。

《上の図で●で表した２枚のピースも以後の説明の都合上、【余計もの】と呼びます。》

単偶数のケースでは余計ものの発生が必須ということになります。


　複偶数（８）の場合。

▼▼▼▼▼▼▼▼
▼０▼３５▼７▼
００３３５５７７
０１３４６５８７
１１４４６６８８
１２４▼▼６９８
２２△▲▼△９９
２△△▲▲△△９

※背丈を伸ばす作業を同様に行うことが出来て、その際にＬ型ピースの枚数が増えないこと
　から、以下が言えることとなります。

　短い方の辺が複偶数の８であれば、その数、すなわち８枚のＬ型ピースがあれば、盤面を
覆いつくせる。

　余計ものはありません。


　複偶数（１２）の場合。

▼▼▼▼▼▼▼▼▼▼▼▼
▼０▼５▼ＡＥ▼Ｉ▼Ｍ▼
００５５ＡＡＥＥＩＩＭＭ
０１５６ＡＢＦＥＪＩＮＭ
１１６６ＢＢＦＦＪＪＮＮ
１２６７ＢＣＧＦＫＪＯＮ
２２７７ＣＣＧＧＫＫＯＯ
２３７８Ｃ▼▼ＧＬＫＰＯ
３３８８９Ｄ▼ＨＬＬＰＰ
３４８９９ＤＤＨＨＬＱＰ
４４▲９△▲Ｄ△Ｈ▲ＱＱ
４▲▲△△▲▲△△▲▲Ｑ

※背丈を伸ばす作業を同様に行うことが出来て、その際にＬ型ピースの枚数が増えないこと
　から、以下が言えることとなります。

　短い方の辺が複偶数の１２であれば、その数、すなわち１２枚のＬ型ピースがあれば、盤面
を覆いつくせる。

　余計ものはありません。


　ところで、【ここでは】単偶数を次に述べる２種類に分別します。

・�E型・・・6 +8*k の形で表すことができるもの。ただし、kは自然数です。

・�I型・・・10 +8*k の形で表すことができるもの。ただし、kは自然数です。


　短い方の辺が、�E型の単偶数の盤面では、これを、短い方の辺が８の盤面を複数と、短い
方の辺が６の盤面をひとつとに分割できます。

　このときに余計ものは、２枚に押さえられています。

　すなわち、

　短い方の辺が�E型の単偶数であれば、その数＋２のＬ型ピースがあれば、盤面を覆いつ
くせる。

ことがわかりました。

　短い方の辺が�I型の単偶数でも全く同様です。


　複偶数の場合には、余計ものがないので次のように言えます。

　短い方の辺が複偶数であれば、その数のＬ型ピースがあれば、盤面を覆いつくせる。


　細かいところが雑で申し訳ありませんが、DD++さんが仰っていたことを自分なりに確認で
きました。これが最小であるかどうかについては、相変わらずサッパリわかりません。



　　以下、工事中！