ペントミノ牧場パズル

ペントミノ牧場パズル 宇佐見 公輔 2021 年 1 月 24 日 1/13 宇佐見 公輔 ペントミノ牧場パズル

自己紹介 職業：プログラマ / 趣味：数学 最近の活動： ルービックキューブ群を SageMath で見る（10 月 / 日曜数 学会） ルービックキューブと群論（10 月 / 関西日曜数学友の会） 平面の敷き詰めとルート系（6 月 / 日曜数学会） 四元数のはなし（5 月 / 関西日曜数学友の会） 2/13 宇佐見 公輔 ペントミノ牧場パズル

ペントミノ 正方形 5 つを辺どうしを合わせてつなげた形。回転・鏡像で重な るものを同じとみなすと、12 個あります。 3/13 宇佐見 公輔 ペントミノ牧場パズル

ペントミノパズル ペントミノを使ったパズルとして、12 個のピースを並べて平面図 形を作る、というものがもっともよく知られています。 次の図では、6 × 10 の長方形を作っています。 4/13 宇佐見 公輔 ペントミノ牧場パズル

ペントミノパズルの解 一般的に「いくつかのポリオミノを使って特定の平面図形を作る」 という問題に対して、それを解くアルゴリズムが知られています。 （Donald E. Knuth, Dancing links, arXiv cs/0011047, 2000） このアルゴリズムは SageMath に実装されていて、簡単に使うこ とができます。（sage.combinat.tiling.TilingSolver クラス） 先ほどの 6 × 10 の長方形の場合、2339 通りの解があります。 5/13 宇佐見 公輔 ペントミノ牧場パズル

ペントミノ牧場 ここでは、ペントミノを使った別のパズル、ペントミノ牧場 （Pentomino farm）を紹介します。12 個のピースを並べて輪を作 ります。囲まれてできる図形の面積の最大値はいくつでしょうか。 6/13 宇佐見 公輔 ペントミノ牧場パズル

ペントミノ牧場の最大値 答えを示してしまいますが、最大値は 128 です。 ペントミノのタイリングパズルではコンピュータを使って解を出 していました。そのため、ペントミノ牧場のパズルもコンピュー タを使うのが良さそうに見えます。 しかし、実は理詰めで最大値が 128 であることを証明することが できます。今回はその概略を説明します。 7/13 宇佐見 公輔 ペントミノ牧場パズル

できる図形の形を考える 矩形を基準として内側にへこんだ形と考えることができます。 矩形は 12 × 12 = 144、へこんだ部分は全部で 17、飛び出ている 部分が 1 です。したがって、144 − 17 + 1 = 128 となります。 8/13 宇佐見 公輔 ペントミノ牧場パズル

周の長さを考える (1) 可能な基準矩形の大きさを考えるために、周の長さを考えます。 各ピースが周をかたちづくるときに、「他のピースから入ってく る正方形」と「他のピースに出ていく正方形」があります。その 間の「長さ」の最大値がピースごとに決まります。 9/13 宇佐見 公輔 ペントミノ牧場パズル

周の長さを考える (2) 合計すると 5 × 6 + 4 × 5 + 3 × 1 = 53 です。矩形の周の長さなの で偶数である必要があり、実際には 52 が最大です。 このことから、次のような矩形が基準として考えられます。 13 × 13 の正方形 : 面積は 12 × 12 = 144 です。 14 × 12 の長方形 : 面積は 13 × 11 = 143 です。 15 × 11 の長方形 : 面積は 14 × 10 = 140 です。 1 つのピースだけ最大の長さを使いません。U のピースを長さ 3 とみなして、矩形から飛び出る部分が 1 個生じると考えるのが最 も効率が良いです。 10/13 宇佐見 公輔 ペントミノ牧場パズル

ピースの分類 さらに突っ込んで考えるには「長さ」だけでなく、入ってから出 るまでの「進み」と「寄り」で分類します。 11/13 宇佐見 公輔 ペントミノ牧場パズル

へこみの量 この分類から、基準矩形に対してへこみが 6 と飛び出しが 1 ある ことが分かります。 さらに細かく考えて、辺に置くべきピース、角に置くべきピース を考えると、基準矩形に対して 11 の削りが必要であることが分 かります。 このため、144 − 6 + 1 − 11 = 128 が最大面積であることが導け ます。 12/13 宇佐見 公輔 ペントミノ牧場パズル

参考文献 ペントミノパズル： Donald E. Knuth, Dancing links, arXiv cs/0011047 Tiling Solver - Sage Reference Manual ペントミノ牧場： 島内剛一, ルービック・キューブと数学パズル 13/13 宇佐見 公輔 ペントミノ牧場パズル

• https://arxiv.org/abs/cs/0011047
• https://doc.sagemath.org/html/en/reference/combinat/sage/combinat/tiling.html
• https://www.amazon.co.jp/dp/4535785376/ref=nosim?tag=usamik-22