|
uchinyan |
|
はい，こんにちは。今年最後の問題ですね。早いものです．．．
さて，今回の問題ですが，最初はサッパリ分からず，プログラムでも組もうかと思ったのですが， 頭の中で，1 人の場合，2 人の場合，3 人の場合，4 人の場合ぐらいまでやってみて，「ハハーン」という感じでした (^^; ポイントは，1, 7 は友人が一人，2 〜 6 は友人が二人，ということですね。 どなたかとかぶるとは思いますが，二つほど思いついたので書いておきます。 (解法1) 最初に思いついた解法です。本当は漸化式なのですが，算数っぽく書いておきます。 ただ，少し冗長＆不正確になってしまいました。ごめんなさい。 以下で，「の状況と同じ」というのは，正確には人数が違うので異なりますが， 同じ考え方で同様の議論を繰り返すと場合の数も同じになる，ことを意味します。 「1)の場合」などもそうした意味を含んでいるとお考えください。ここらの記述があいまいでした。 1 の位置に注目します。 1) 1 が先頭の場合 1 の友人は 2 だけなので，1 のすぐ後は 2 だけです。例えば，4 だと，4 の前に友人がいることに矛盾します。 2 は友人が二人，1, 3 がいますが，1 は前にいるので後に来られるのは 3 だけです。 つまり，後に関しては，1 と同じ状況になっています。そこで同じ理由で，2 のすぐ後は 3 だけです。 以下同様にして順次決定してしまうので，この場合は，1 通りしかないことが分かります。 2) 1 が先頭から2番目の場合 1 の友人は 2 だけなので，2 は 1 の前，先頭，にきます。 また，この並び方に関しては，3 〜 7 にとっては，1 とは友人関係にないので，1 の存在は意味がありません。(何か寂しいですが．．．) そこで，2 の位置を決定した後では，1 を除いて考えることができます。 これは，2 〜 7 を同じ規則で並べることになり，しかも， 2 は先頭なので，1) の状況と同じ です。 そこで，1 通りになります。 3) 1 が先頭から3番目の場合 1 の友人は 2 だけなので，2 は 1 の前，先頭又は2番目，にきます。 また，この並び方に関しては，3 〜 7 にとっては，1 とは友人関係にないので，1 の存在は意味がありません。 そこで，2 の位置を決定した後では，1 を除いて考えることができます。 これは，2 〜 7 を同じ規則で並べることになり，しかも， 2 が先頭ならば 1) の状況と同じ 2 が2番目ならば 2) の状況と同じ です。 そこで，1 + 1 = 2 通りになります。 4) 1 が先頭から4番目の場合 1 の友人は 2 だけなので，2 は 1 の前，先頭，2番目又は3番目，にきます。 また，この並び方に関しては，3 〜 7 にとっては，1 とは友人関係にないので，1 の存在は意味がありません。 そこで，2 の位置を決定した後では，1 を除いて考えることができます。 これは，2 〜 7 を同じ規則で並べることになり，しかも， 2 が先頭ならば 1) の状況と同じ 2 が2番目ならば 2) の状況と同じ 2 が3番目ならば 3) の状況と同じ です。 そこで，1 + 1 + 2 = 4 通りになります。 ここまでくればほとんど明らかでしょう。しかも，その計算方法から， 1)の場合 = 1 通り 2)の場合 = 1)の場合 = 1 通り 3)の場合 = 1)の場合 + 2)の場合 = 2 * 2)の場合 = 2 通り 4)の場合 = 1)の場合 + 2)の場合 + 3)の場合 = 2 * 3)の場合 = 4 通り になっています。以下同様にして， 5) 1 が先頭から5番目の場合 5)の場合 = 1)の場合 + 2)の場合 + 3)の場合 + 4)の場合 = 2 * 4)の場合 = 8 通り 6) 1 が先頭から6番目の場合 6)の場合 = 1)の場合 + 2)の場合 + 3)の場合 + 4)の場合 + 5)の場合 = 2 * 5)の場合 = 16 通り 7) 1 が先頭から7番目の場合 7)の場合 = 1)の場合 + 2)の場合 + 3)の場合 + 4)の場合 + 5)の場合 + 6)の場合 = 2 * 6)の場合 = 32 通り これですべてです。そこで，これらを足して， 1 + 1 + 2 + 4 + 8 + 16 + 32 = 64 通り になります。 なお，明らかに，一般に n 人の場合は，公比 2 の等比級数に 1 を足したものなので 1 + 1 + 2 + 4 + 8 + 16 + 32 + ... + 2^(n-2) = 1 + (2^(n-1) - 1) = 2^(n-1) 通り ですね。 (解法2) (解法1)を吟味し直していて，「そうか待てよ」と気付いた解法です。 今度は先頭の人に注目します。 1) 1 が先頭の場合 これは，(解法1)と同じで，1 通りです。 2) 2 が先頭の場合 1 は 2 の後どこでもOKです。 一方，3 〜 7 は，(解法1)と同じ理由で，1) の状況と同じになり，1 通りになります。 したがって，1 の位置の選択の分だけ可能で，(7-1)C1 = 6C1 通り になります。 3) 3 が先頭の場合 1 〜 2, 4 〜 7 ともに 3 の後に並ぶわけですが，1 〜 2 と 4 〜 7 の間には友人関係はないので，独立に考えることができます。 そして，(解法1)の1)と同じような理由で， 1 〜 2 は，...2...1... の順番 4 〜 7 は，...4...5...6...7... の順番 だけが可能です。(例えば，...5...4...6...7... だと，5 の前に友人，4，6 がいない。) そこで，結局，並び方は，1 〜 2 の位置の選択の分だけ可能で，(7-1)C2 = 6C2 通り になります。 4) 4 が先頭の場合 1 〜 3, 5 〜 7 ともに 4 の後に並ぶわけですが，1 〜 3 と 6 〜 7 の間には友人関係はないので，独立 に考えることができます。 そして，(解法1)の1)と同じような理由で， 1 〜 3 は，...3...2...1... の順番 5 〜 7 は，...5...6...7... の順番 だけが可能です。 そこで，結局，並び方は，1 〜 3 の位置の選択の分だけ可能で，(7-1)C3 = 6C3 通り になります。 ここまでくればほとんど明らかでしょう。 5) 5 が先頭の場合 6C4 通り になります。 6) 6 が先頭の場合 6C5 通り になります。 7) 7 が先頭の場合 6C6 通り になります。 これですべてです。そこで，これらを足して， 1 + 6C1 + 6C2 + 6C3 + 6C4 + 6C5 + 6C6 = 1 + 6 + 15 + 20 + 15 + 6 + 1 = 64 通り になります。 なお，1 = 6C0 なので，一般に n 人の場合には，二項定理を使って， (n-1)C0 + (n-1)C1 + (n-1)C2 + ... + (n-1)C(n-3) + (n-1)C(n-2) + (n-1)C(n-1) = (1 + 1)^(n-1) = 2^(n-1) 通り ですね。 |
|
ネコの住む家
12月28日（木） 15:11:18
MAIL:uchi@sco.bekkoame.ne.jp 28938 |