パズルの国のアリス

絨毯の絨毯爆撃(問題)

坂井 公(筑波大学) 題字・イラスト:斉藤重之

 不思議の国のトランプ城を鏡の国の赤白の国王夫妻が表敬訪問することになり,トランプ城はその受け入れ準備で大わらわだ。城の入り口から北にまっすぐ伸びて「会見の間」につながる一定幅の長い廊下に赤い絨毯を敷き詰めようという話になった。しかし,短い期間にその長さの絨毯を一業者だけから調達することは不可能だ。というわけで,絨毯の幅と色と材質だけを指定して方々の業者に同時発注して,それらをつなぎ合わせて使えばよいだろうということになった。

 ところが,次々と納入されるまちまちの長さの絨毯を見て,ハートの女王が突然指揮を執り始め,あそこに敷け,ここに敷けと,まったく無計画に行き当たりばったりに廊下に敷いていってしまった。幸い幅は合っているし,たくさんの業者に作らせたので,何とか廊下全体を覆うことはできたのだが,廊下の一部は,5重6重にも絨毯が重なり,はなはだ不体裁ということになった。

 あまりのことに,トランプ王室の他の面々が集まり,ハートの女王に苦言を呈すると,女王は,非常に不機嫌そうな顔をして,「よろしい。重なって余分になっている絨毯は取り除いてもよいとしよう。しかし,残す絨毯は,どれも決して現在の位置からずらしたりしないように」という。

 それでも,ハートの女王からわずかでも譲歩を引き出したということは,大変な快挙である。早速,スペードのエースを中心とするチームが編成され,どういうふうに無駄な絨毯を取り除いていけばよいかを検討することになった。

 さて,ここで読者への問題だが,女王の要求を満たした上でも,廊下のどの部分もせいぜい2重にしか覆われないように余分な絨毯を除けることを証明していただきたい。さらに,そうするためのシステマティックな方法を考えてほしい。また,女王の要求を満たした上で,まったく重なりが無い段階まで絨毯を取り除いても,少なくとも廊下の半分は絨毯で覆われているようにできることを証明していただきたい。

解答はこちらです