ここから本文です

3×mの長方形に1×2の長方形を敷き詰める方法は何通りあるかわかる方はいらっしゃい...

dex********さん

2010/6/1820:48:44

3×mの長方形に1×2の長方形を敷き詰める方法は何通りあるかわかる方はいらっしゃいますか。
mは変数です。
漸化式などもわかるとありがたいです。
よろしくお願いします。

閲覧数:
102
回答数:
2

違反報告

ベストアンサーに選ばれた回答

osh********さん

2010/6/1900:17:48

mが奇数の場合は、面積が奇数となり 1×2の長方形できちんと敷き詰めることは出来ません。
したがって mが奇数の場合のは 0通り。
【mが偶数のとき】
最後に「長さ3の縦の線」で区切れているところはどこかで分類します。
nが4以上の偶数のとき、3×nの長方形が「長さ3の縦の線」で区切れていない場合は、2通りあります(図を描いて確認してください)
3×n の長方形の敷き詰め方の総数を A[n]と表します。
すると
A[2]=3
《m=4 のとき》・・・[縦3の区切りがないとき]+[最後の縦3の区切りが左から距離2のとき]
A[4]=2+A[2]×3=2+9=11
《m=6 のとき》・・・[縦3の区切りがないとき]+[最後の縦3の区切りが左から距離2のとき]+[最後の縦3の区切りが左から距離4のとき]
A[6]=2+A[2]*2+A[4]*3 (=2+6+11*3=41)
《m=8 のとき》・・・[縦3の区切りがないとき]+[最後の縦3の区切りが左から距離2のとき]+[最後の縦3の区切りが左から距離4のとき]+[最後の縦3の区切りが左から距離6のとき]
A[8]=2+A[2]*2+A[4]*2+A[6]*3 (=2+6+11*3=41)
《m=10 のとき》・・・[縦3の区切りがないとき]+[最後の縦3の区切りが左から距離2のとき]+[最後の縦3の区切りが左から距離4のとき]+[最後の縦3の区切りが左から距離6のとき]+[最後の縦3の区切りが左から距離8のとき]
A[10]=2+A[2]*2+A[4]*2+A[6]*2+A[8]*3 (=2+6+11*2+41*3=153)
・・・・・・・・・・
これらの式より、結局
A[2]=3 ,A[4]=11
A[m]=4*A[m-2]-A[m-4] .(mが以上の偶数のとき)
という漸化式ができます。

(一般項は特性方程式を解けば求まるでしょう。)

質問した人からのコメント

2010/6/19 14:46:44

わかりやすい解説有難うございます。

ベストアンサー以外の回答

1〜1件/1件中

kai********さん

2010/6/1821:12:58

問題が分かりません・・・3x?m

この質問につけられたタグ

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる