|
uchinyan |
|
はい，こんにちは。さて，今回の問題は．．．
これは類題を見たことがあります。算チャレでも出題されていたように思います。 つまり．．． 正八面体の各面の中心を，上から見て，△PAB から反時計回りに 1，2，3，4，△QAB から反時計回りに 5，6，7，8 とします。 すると，問題は，最初 1 にいるアリが 1 秒ごとに立方体 1234-5678 の辺上を移動するとき， 5 秒後に 7 にいる場合の数を求める問題になります。 これはよく見る問題です。このことを念頭において，というか，これに置き換えて，解きました。 (解法1) 漸化式風に考える解法です。 1 秒ごとに立方体の各頂点にアリが来る場合の数は，1 秒前の隣り合う頂点の場合の数の和になります。 これより表を書くと， 各頂点 01 02 03 04 05 06 07 08 00秒後 01 00 00 00 00 00 00 00 01秒後 00 01 00 01 01 00 00 00 02秒後 03 00 02 00 00 02 00 02 03秒後 00 07 00 07 07 00 06 00 04秒後 21 00 20 00 00 20 00 20 05秒後 00 61 00 61 61 00 60 00 そこで，5 秒後の頂点 7 は 60 なので，60 通り，になります。 (解法2) 立方体の 1-2 方向の移動を a，1-4 方向の移動を b，1-5 方向の移動を c とすると， 5 秒後の移動は a，b，c を重複を許して 5 個並べるのと同じです。 ただし，同じ方向の移動は，必ず，行って戻ってしかないので，例えば，a が 2 回ある場合は移動がないのと同じになります。 頂点 7 に至るには，この行って戻ってを含めて a，b，c が 1 回ずつになります。 実際には，5 秒後なので，一回だけ行って戻ってをする，a，a，a，b，c か，a，b，b，b，c か，a，b，c，c，c か， のいずれかを並べることになります。 明らかにそれぞれの場合の数は同じで，そのうちの，例えば，a，a，a，b，c は，5!/3!1!1! = 20 通り，なので， 求める場合の数は，20 * 3 = 60 通り，になります。 なお，a，a，a，b，c の並べ方は，五つの場所から a を並べる三つを選ぶと考えて，5C3 = 30 通り，でもいいですね。 (解法3) (解法1)の表を書いてみれば分かりますが，一般に，n 秒後において，次のことが分かります。 全体の移動の場合の数は，各秒ごとに 3 通りで 3^n 通り。 ・n が偶数の場合 頂点 2，4，5，7 は，0 通り。 頂点 3，6，8 は，対称性より，同じ。 頂点 1 は，頂点 3，6，8 のぞれぞれより 1 だけ多い。 ・n が奇数の場合 頂点 1，3，6，8 は，0 通り。 頂点 2，4，5 は，対称性より，同じ。 頂点 7 は，頂点 2，4，5 のぞれぞれより 1 だけ少ない。 そこで，5 秒後の 7 は，(3^5 - 3)/4 = 240/4 = 60 通り，になります。 より厳密には，数学的帰納法を使うか，漸化式を立てて解けばいいですが，数学になってしまうので，省略します。 |
|
ネコの住む家
10月8日（木） 13:22:14
MAIL:uchi@sco.bekkoame.ne.jp 35164 |