パズルの国のアリス

大部屋と1人部屋どっちが好き?(問題)

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

 ヤマネの7匹の姪たちがペットを飼い始めたという話がアリスの耳に届いた。「ヤマネなんて,人間から見ればペットみたいなものなのに……ペットがペットを飼うなんて,なんか変だわ」と思ったが,不思議の国が奇妙なのには慣れっこになっている。それに持ち前の好奇心には勝てないので,すぐにヤマネの姪たちを訪ねた。姪たちはペットの世話とその観察に余念がない。

 「あら,アリスさん,早速いらっしゃったわね」とサンデイがアリスに気づいて言う。「お目当てはペットでしょ? でも,アリスさんには初対面ではないの。だって,王宮内の花園にいた蟻ん子たちとその子孫ですもの。ほら,このビンの中を見て」。

 大きなビンの中で飼われているのは,確かにアリスが見たことのある蟻たちだ〔今月の問題とは直接の関係はないが,関心のある読者は「寂しがり屋の蟻たち」(2018年7月号,『ハートの女王とマハラジャの対決』第111話)をご覧いただきたい〕。ビンの側面を覆っている黒い紙を少しはがすと,巣の中の様子がわかる。

 マンデイが寄ってきて説明に加わる。「花園のときも奇妙だったけど,巣の中でも面白い動きをするのよ」と数十匹の蟻をすくい上げて別のビンの中の巣内に放した。巣には複数の部屋があり,蟻たちはとりあえずどこかの部屋の中にもぐり込んだ。「ここからが面白いのよ」とマンデイ。

 見ていると,1分ほどして1匹の蟻が部屋から出てきた。そして,他の部屋の様子をキョロキョロと見回し,やがて仲間がいる別の部屋に移動した。さらにまた1分ほどすると,別の1匹が同じように部屋を移動した。「ね,このように蟻たちは引っ越しを繰り返すんだけど,寂しがり屋の習性はこのときも発揮されるみたいなのよ。だって,自分が前にいた部屋よりも住人の少ない部屋には決して行かないんだから。自分のいた部屋の人数がほかのどの部屋の人数よりも多いなら,仕方なく元の部屋に戻るのよ」とマンデイ。

 まず,ウォーミングアップ問題だ。当たり前のようではあるが,こうして引っ越しを繰り返していくと,やがて全員が同じ部屋に集まってしまうことを証明していただきたい。もちろん自分が直前にいた部屋に戻るような場合は引っ越しには数えない。さらに,もし蟻が全部で21匹いて,最初6つの部屋に1匹,2匹,3匹,4匹,5匹,6匹と分かれていたとしたら,最大でも延べ35回の引っ越しの後には全員が1つの部屋に集まっていることを証明できるだろうか?

 さて,サタデイが飼育室の別のコーナーから「こっちの蟻も面白いわよ」とアリスを呼んだ。サタデイの近くにある飼育ビンの中にいる蟻は偶然に交じった別種か突然変異種らしいという。「どうしてかって? まず巣の作り方が違うの。巣は部屋を円形につなげて作るのよ。しかも,あっちの寂しがり屋と違って,こっちは孤独好きみたい。蟻たちを適当に分けて部屋にいれるでしょ。こういうふうに」。

 1分ほどたつと,今度は同じ部屋にいた2匹がその部屋を離れてそれぞれ左右の両隣の部屋に引っ越した。ほぼ1分ごとにこれが繰り返され,2匹以上の蟻がいる部屋から,その両隣の部屋に蟻が1匹ずつ移動するという。「このように移動を繰り返して全員が1人部屋になると落ち着くのだけど,そうでないといつまでも続くのよ」。

 今,巣には円形につながった部屋が20室あるとしよう。そこに21匹の孤独好きの蟻をでたらめにいれる。この場合,全員が1人部屋になることは決してないから,蟻たちがいつまでも引っ越しを繰り返すことは明らかだが,最初に蟻をどういれても,空き部屋が9室以下になるということが必ず起こることを証明していただきたい。ただし,2つ以上の部屋からそれぞれ2匹の蟻が同時に移動することはないものとする。

解答はこちらです