« 世界最速のプログレスバーを探す試み | メイン | 接点と円と三角形のパズル »

マッチ棒の並べ方パズル

 以前にこのブログにて、プログラミングで解く数学の問題集のサイト「プロジェクトオイラー」をご紹介しました。(参考:「プロジェクトオイラーを遊び倒すガイド」 導入編初級編中級編上級編

 さて、今回、出された問題を解くだけでは飽き足らず、オリジナル問題を作ってみました。興味のある方はぜひチャレンジしてみて下さい。

---
【問】
正の整数 W, H に対し、長さ 1 のマッチ棒を 2*W*H+W+H 本ならべて、横 W × 縦 H の格子状の図形を作る。
各マッチ棒の頭の向きに応じて様々な並べ方が可能である。
W=3, H=2 の場合、並べ方は全部で 22*3*2+3+2 = 131072 通りある(図形全体の回転や反転は考慮しない)。このうちの 2 つを下に示す。

ここで、次の条件を満たす並べ方に着目する:すべての格子点は、少なくとも 1 個のマッチ棒の頭を含む。
左の例は、12 個の格子点の全てが少なくとも 1 個のマッチ棒の頭を含んでおり条件を満たしているが、右の例は、青丸で囲った格子点が頭を含んでおらず条件を満たしていない。

N(W, H) をこの条件を満たす並べ方の数とする。
例えば、N(1,1)=2、N(2,1)=14, N(3,2)=7618 である。
N(120,12) mod 108 を求めよ。
---

 回答は こちら(受付終了しました)のページに行って、テキストボックスに答の8桁の数字を入力してから「回答」を押して下さい。正解なら専用の掲示板ページに飛びます。不正解なら 404 Not Found が表示されます。

 チャレンジをお待ちしています!

トラックバック

このエントリーのトラックバックURL:
http://www.riverplus.net/cgi/mt/mt-tb.cgi/3195