読者です 読者をやめる 読者になる 読者になる

(define -ayalog '())

括弧に魅せられて道を外した名前のないプログラマ

ピアスの公式を書いてみた。

クラムというゲームがあるそうで、それの発展として「砲門の問題(The Gunport Problem)」というのがあるらしい。

m×nの板上にドミノを置いたとき、1×1の大きさの「穴」が最大いくつ開けられるか。
ただしmもnも1より大きいものとする。
※ドミノは1×2の大きさ

たぶん、英語のものだとこの辺がその話かな。
The Gunport Problem - Mathematics Magazine
日本語で「砲門の問題」って検索したら、「訪問」の検索結果がでやがりますので、英語で検索した。

で、この問題に関してピアスという人が、予測を述べていて、公式があったのでこれをSchemeで記述してみたっていうわけ。

(define  (pearce n m)
  (let ((nm (mod n 3)) (mm (mod m 3)))
    (cond [(any zero? `(,nm ,mm)) (/ (* m n) 3)]
	  [(or (every (cut = 1 <>) `(,nm ,mm))
	       (every (cut = 2 <>) `(,nm ,mm))) (/ (- (* n m) 4) 3)]
	  [else (/ (- (* n m) 2) 3)])))

これ公式の正しさが証明されていないらしく、8×10の盤に対しては公式によれば穴が26になるらしいんだけど、ドミノで作ることができた穴は24個が最大だったらしい。(1970年代の話だから、今はどうか知らないけど)
興味ある人は挑戦してみてると面白いんじゃないですかね。証明。