博士

やあ、ロボ子！今日はちょっと面白いパズルのお話をするのじゃ。

ロボ子

博士、どんなパズルですか？

博士

6つの色付きキューブを9つの穴に配置するパズルじゃ。赤が2つ、緑が2つ、青が2つ。残りの3つの穴は空っぽにするのじゃ。

ロボ子

なるほど。色の配置に制約があるんですね。

博士

そう！隣り合うキューブが同じ色にならないように配置する必要があるのじゃ。これがなかなか難しいのじゃ。

ロボ子

配置の総数を求める問題なんですね。多重集合 {R2, G2, B2, E3} の長さ9の異なる配置の数を求める、と。

博士

そうそう！制限なしだと、配置の総数 Ntotal は7560通りになるらしいぞ。

ロボ子

かなり多いですね。隣接する色の制約を考慮すると、どうなるんですか？

博士

まず、1色が隣接する場合を考えるのじゃ。例えば、赤が隣接する場合の数 N(AR) は1680通り。緑と青も同じじゃから、N(AG)とN(AB)も1680通りじゃ。

ロボ子

対称性があるからですね。

博士

その通り！次に、2色が隣接する場合、例えば赤と緑が隣接する場合の数 N(AR∩AG) は420通りじゃ。

ロボ子

そして、3色すべてが隣接する場合は、N(AR∩AG∩AB) = 120通り、と。

博士

そう！ここで包除原理を使うのじゃ！これを使うと、条件を満たす配置の数 Ngood が求められるのじゃ。

ロボ子

包除原理を適用すると、Ngood = 3660通りになるんですね。

博士

正解！このパズル、Lean, Haskell, Rust で実装されてるらしいぞ。すごいじゃろ？

ロボ子

それぞれの言語で実装されているんですね。アルゴリズムの表現方法の違いを見るのも面白そうです。

博士

そうじゃな。このパズル、意外と実用的な応用も考えられるのじゃ。例えば、データセンターのサーバー配置とか、製品の在庫管理とか。

ロボ子

サーバーの配置ですか。冷却効率を最適化するために、発熱量の高いサーバーが隣接しないように配置する、とか？

博士

まさに！ロボ子は頭が良いのう！他にも、化学物質の保管場所で、反応しやすい物質同士が隣接しないように配置するとか、色々考えられるのじゃ。

ロボ子

なるほど、応用範囲が広いですね。制約条件を少し変えるだけで、様々な最適化問題に対応できそうです。

博士

そう！このパズルは、単なる遊びじゃなくて、実世界の問題を解決するためのヒントになるのじゃ！

ロボ子

勉強になりました！

博士

ところでロボ子、このパズル、全部のキューブを同じ色にしたらどうなると思う？

ロボ子

えっと…全部同じ色だと、隣接しないように配置する意味がなくなりますね。

博士

そう！つまり、全部同じ色だと…ただのカラフルな積み木になるのじゃ！