ああ、予想通り、しばらく更新していなかったですねぇ。
ところで、以前こんなのを見ました。
1:以下、名無しにかわりましてVIPがお送りします:2012/11/09(金) 14:25:05.82 ID:m2CFPu340
正20面体の各面を赤、青、黄のいずれかで塗っていくとき、何通りの塗り方が存在するか。
http://netaatoz.jp/archives/7565108.html
googleの入社試験問題です
というものでした。
Googleの試験問題と言うので、
計算した後に早速ググってみたところ、
「58,130,055通り」
という答えが出てきました。が、これは、僕が計算して出した答えと違います。
ちなみにGoogleの(?)答えは、素直に
「3^20通り(正20面体の場合は3^20/20通り)」
http://www.thegooglestory.com/glatpage2.html
のようです。一体どれなんだ…。少なくとも、
3^20/20は整数じゃないし…。
なので、その自分で出した「別解」を書くというのが今日のネタです。
まず始めに、正20面体の一つの面に、3色で色を塗るのは3通り。で、これが他に19面あるのだから、(重複を考えない)全ての組み合わせは、3を20回掛ければよく、
3^20
通りです。
次に、重複を考えてみます。今、正20面体を水平なところに置いたとき、一番上の面と一番下の面
正20面体は、向かい合う反平行な正三角形1組が、
10個集まってできている
が、重複している場合があります。これの一番簡単な例は、
1) 一番上の面と一番下の面:赤と青
その他の面:黄
2) 一番上の面と一番下の面:青と赤
その他の面:黄
でしょう。この二つは、ひっくり返しても同じなので、明らかに重複しています。
「『その他の面』が、いろいろ複雑に塗ってあるときはどうするの?」
…たしかに、これを考えるのが一番難しいわけですが、ここは思い切って、
「『その他の面』は、元の模様とは『リバーシブル』な模様が必ず一組あり、
『リバーシブル』な模様の上下をひっくり返すと、元の模様と同じになる」
という、本当はそれ自体証明が必要そうな仮定が成り立っているとしましょう。まあ、そういうものということで。
すると、上面と下面の組み合わせは、
(上, 下) = (赤, 赤), (青, 青), (黄, 黄),
(赤, 青), (青, 赤),
(赤, 黄), (黄, 赤),
(青, 黄), (黄, 青)
の、9通りあることになりますが、このうち2、3、4行目は、重複しているので、その分は消さなければなりません。そうすると、
(面, 向かいの面) = (赤, 赤), (青, 青), (黄, 黄),
(赤, 青),
(赤, 黄),
(青, 黄)
の、6通りに減ります。つまり、1組の面に関して、重複を考慮すると、組み合わせは6/9=
2/3に減ることになります。
この考え方では、「その他の面」がどうなっているのかは無関係で、全然気にしなくていいことになるので、他の9組の面の組み合わせについても、全く同じことが言えるはずです。つまり、組み合わせは、重複を考慮していない場合とは、比で
(2/3)^10
だけ、減ることになります。よって、求める組み合わせは、
3^20 * (2/3)^10 = 3^10 * 2^10 = 6^10 = 60,466,176通り
となります。
というわけで、自分で考えたら、「58,130,055通り」より4%ほど多い答えが出た、という話でした。