第415問の解答
問題[場合の数]
左図のような立方体ABCD−EFGHがあります。
いま、頂点Aにテントウムシがいます。このテントウムシは、1分ごとに隣り合ういずれかの頂点に移動します。(例えば、頂点Aにいる場合は、1分後にB、D、Eのいずれかの頂点に移動)
では、6分後にテントウムシが頂点Aにいるような移動方法は何通りあるでしょうか。
解答例1
トトロ@Nさん、みかんさん、N.Nishiさん、CRYING DOLPHINさん、キノピーさん、ゆんななこさん、萬田銀次郎さん、TODAIJI 1-Cさん、 他
1分ごとに、各頂点への移動方法の数を書いていくと上図のようになります。
答: 183通り
以上
解答例2
Taroさん、uchinyanさん、tomhさん、 他
n分後の各頂点への移動方法の数をAn、Bn、・・・、Hnとし、漸化式を求めて計算すると上表のようになります。 本問では、A6=183通りとなります。
(参考)行列で計算することもできます。
解答例3
なかさん、長野 美光さん、ミミズクはくず耳さん、 他
3分後には、B、D、E、またはGのいずれかにいて、
B、D、Eへは7通り、Gへは6通り。6分後には、それぞれ往復することになるので、
7×7+7×7+7×7+6×6=183通り。
解答例4
小学名探偵さん、他
n分後について、奇数のときと偶数のときで上記事項が成り立ちます。(帰納法にて証明できる)
n=奇数のとき:(Bn+Dn+En+Gn)=3n
→Bn=Dn=En=(3n+1)/4、Gn=(3n−3)/4n=偶数のとき:(An+Cn+Fn+Hn)=3n
→Cn=Fn=Hn=(3n−1)/4、An=(3n+3)/4とくに本問では、A6=(36+3)/4=(729+3)/4=183通りとなります。
(その他の解法)
何回Aに戻るかで場合分け ・・・ あ〜く@ぴかぴかの(略さん、 他
A からの距離により (B,D,E) , (C,F,H) , (G) の3グループに分け数える ・・・ つよしさん、 他
立方体の3辺に沿っての移動に着目 ・・・ uchinyanさん、 他
2分後ごとの移動に着目 ・・・ 工事中 さん、 他
樹形図で計算する ・・・ 始 受験勉強君さん、 ゴンともさん、 築さん、 他
プログラムで計算する ・・・ kasamaさん、 他