今回のテーマは「おしどり問題」
・問題（分かりやすいように番組での物と変えています）
9×9のマス目があり、右から3番目上から4番目のマスに×印がある。
この×印以外のマス目を一筆書きするように移動できるか？
（マス目間の移動方向は上下左右のみとし
同じマスは2度と通ることは出来ない。）
この問題……瞬殺でした。
ドミノ敷きつめ問題を知っていれば
応用して解く事が出来ます。
マス目を市松模様に塗り分けると、1色が41マス、もう1色が39マス。
ルールに従って移動すると2色を交互に辿る事となるので、
絶対に一筆書きで移動しきる事は出来ないという結論が導けます。
コマ大生チームがスタジオで使っていた紙を見たら、
理由まで到達できそうだったのですが、
残念ながら到達できていませんでした。
マス北野もドミノ敷きつめ問題は知らなかったか……。
この問題自体の難易度は高くはないのですが、
ここから竹内先生の解説はハミルトン経路に派生。
これがNP完全問題となっているとの事。
簡単な問題なのに法則性が導き出せない、
数学の難しさが分かる解説でした。
PR
