2021-いちご-解説
- 考案国：スイス
- 正解
- ビバ子はイチゴのかわりにきのこを置きました。そして、次の図のように枝を抜き取りました。
- ビバ子はイチゴのかわりにきのこを置きました。そして、次の図のように枝を抜き取りました。
- 説明
- イチゴが置かれていた「？」には、5本の棒が置かれています。
- どんぐりや小石を置くと、同じ種類の2箇所とつながっているため、2本の棒をぬき取る必要があります。
- きのこを置くと、きのことつながっている1本をぬき取るだけですみます。
- 実際のコンピュータでは
- ビ太郎が描いた絵は、点と線で関係を表す「グラフ」という構造で考えることができます。
- グラフの中で、「すべての点が、他の点とつながっている」ような点の集まりをクリークと呼びます。この問題の図では、左と右に、4個ずつの点から作られた四角形のクリークが2個あることがわかります。
- イチゴを他の物で置き換えると、置かれている物は3種類になりますので、4個の点を使ったクリークは作れなくなるはずです。そこで、4個の点から作られた2個のクリークを壊す棒を探すと、真ん中の縦の棒をぬき取ればよいことがわかります。
- この問題は、「最小限の色数でグラフを着色する問題」として知られています。そして、スポーツ競技のスケジュール管理、座席表の設計、数独の解答など、多くの用途で利用されています。
注があるものを除き, このサイトの内容物は
