ペントミノ牧場パズル

196 Views

January 24, 21

スライド概要

ペントミノ牧場パズル @第20回日曜数学会 - ニコニコ動画
https://www.nicovideo.jp/watch/sm38245603

第20回日曜数学会
https://live2.nicovideo.jp/watch/lv330088172

ペントミノ牧場パズルの話をしました #日曜数学会 - usami-k 数学日記
https://usami-k.hatenadiary.jp/entry/2021/01/25/082148

profile-image

https://usami-k.github.io/

シェア

またはPlayer版

埋め込む »CMSなどでJSが使えない場合

関連スライド

各ページのテキスト
1.

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

2.

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

3.

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

4.

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

5.

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

6.

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

7.

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

8.

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

9.

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

10.

周の長さを考える (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.

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

12.

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

13.

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