Problem 256 を 紹介する

畳がでてくるので,畳好きの日本人としては,紹介しないわけにはいかない.

(問題の雰囲気を伝えることを目標にする.詳しくは Problem 256 – Project Eulerで)

どんな問題かというと…

縦がa,横がbの長方形の部屋(a <= b)に畳(1×2の長方形)を敷き詰めることを考えます(下図参照).

f:id:jeneshicc:20090920013052g:image

(画像はhttp://projecteuler.net/index.php?section=problems&id=256のものを転載)

ただし,畳の4つの角が一箇所に集まるような敷き詰めかたは禁止します.

(たぶん,敷き詰めた畳がズレやすいとかなんでしょう,たぶん)

したがって,上の図の右側の敷き詰めかたはダメ(赤い X 印のところに4つの角があつまっている),

左側は大丈夫.

次に,部屋の面積 s = a * b に注目します.ある面積の部屋の形は色々ありますが(縦,横を整数に制限),

それぞれが,畳で敷き詰めることが出来るかを考えます.

(例えば, s = 70 とすると,1 x 70, 2 x 35, 5 x 14, 7 x 10 の部屋の形がある.)

敷き詰めることができない部屋の形の数を T(s) と表します.

T(s) = n となる,最小の s を探すにはどうすれば良いですか?

(ちなみに,T(s) = 1 となる最小の s は s = 70 だそうです.)

という問題.

実際に和室の畳の様子を見ると,ヒントになるかも??

ちなみに,畳 – Wikipediaによると,

問題の4つの角が集まらないような敷きかたを「祝儀敷き」というそうです.

だから,問題は「祝儀敷きできない部屋の形は?」となるのか.