【Google入社問題】正多面体の塗り分けを考えてみる

google入社試験,塗り分け,ポーヤの計数定理

465

初めに

世界的な大企業「Google」の入社試験に、以下のような問題が出題されました。

「正二十面体の各面を3色のいずれかで塗っていく時、何通りの塗り方が存在しますか？」

一見簡単そうに見える問題ですが、正多面体の塗り分けは回転させることにより重複が発生するため、その重複を排除する必要があります。

範囲を考える

20面を3色に分けるのですから、最大3^20通りであることは容易に想像できます。
従って、
$0 < A n s < 3486784401$

集合として考える

正二十面体の回転やひっくり返しを行うと重複してしまう訳ですが、その重複を人間の頭でシミュレーションしながら考えることは困難です。

そこで、多面体から各色への写像として考えてみます。

$f : {1, 2, 3, 4, ・・ 19, 20} \to {C o l o r A, C o l o r B, C o l o r C}$

正多面体の回転やひっくり返しは、集合の順番の置換に対応しますから、ポリア（ポーヤ）の数え上げ定理で写像を計算できます。

ポリアの定理Iより、
$P (x_{1}, x_{2}, \dots, x_{n}) = \frac{1}{| G |} \sum_{π \in G} | D_{2} |^{k (π)} = \frac{1}{| G |} \sum_{π \in G} m^{k (π)}$

ここで、置換群 |G| = 60 (個) より、5次対称群の部分群である交代群として考えると、
正二十面体のn色塗り分けは、
$A n s = \frac{1}{60} n^{20} + \frac{1}{4} n^{10} + \frac{1}{3} n^{8} + \frac{2}{5} n^{4}$

n = 3 より、Ans = 58,130,055 と求まりました。

$0 < 58130055 < 3486784401$

であるから、これは題に適しています。

$(1 - 58130055 / 3486784401) ・ 100 ≒ 98.3328463044$

より、実に約98.3%の塗り方が重複してしまうという事ですね。

色の種類を増やしてみる

nの値の変化に伴って、塗り分けの通り数はどのように変化するのか計算してみます。

もちろん手動で計算するのは大変ですから、JavaScriptで処理させます。

コード

      window.CalcColor = function(n) {
  return (
    (1/60) * Math.pow(n, 20) +
    (1/4) * Math.pow(n, 10) +
    (1/3) * Math.pow(n, 8) +
    (2/5) * Math.pow(n, 4)
  )
}
for (let i = 1; i <= 10; i++)
  console.log("n = " + i + " : Ans = " + window.CalcColor(i));

結果

n = 1 : Ans = 1
n = 2 : Ans = 17824
n = 3 : Ans = 58130055
n = 4 : Ans = 18325477888
n = 5 : Ans = 1589459765875
n = 6 : Ans = 60935989677984
n = 7 : Ans = 1329871177501573
n = 8 : Ans = 19215358684143616
n = 9 : Ans = 202627758536996400
n = 10 : Ans = 1666666669200004000

また、重複率は以下のようになります。

1^20 = 1, 重複率0%
2^20 = 1048576, 重複率98.3001708984375%
3^20 = 3486784401, 重複率98.33284630436776%
4^20 = 1099511627776, 重複率98.3333074953407%
5^20 = 95367431640625, 重複率98.33333063653785%
6^20 = 3656158440062976, 重複率98.33333290455174%
7^20 = 79792266297612000, 重複率98.33333324242055%
8^20 = 1152921504606847000, 重複率98.33333330956506%
9^20 = 12157665459056929000, 重複率98.33333332604536%
10^20 = 100000000000000000000, 重複率98.3333333308%

このように、重複率は $98. \dot{3} ％$ に近づいていくことが分かります。