パズルの国のアリス

平均化フラスコ(解答)

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

 2つの容器の場合は簡単だが,整理して考えるなら,最終段階から逆向きに考えるといい。水全体の量を1とすると,もし,均等化ができたなら,そのとき両フラスコに入っている水はともに1/2である。すると,その前は,どちらかがその半分であったわけだから,1/4:3/4に分かれていたはずだ。さらにその前となると,半分になっていたのがどちらかということによって,1/8:7/8か3/8:5/8かに分かれていたに違いない。

 以上から,量が均等化できるための条件は,「水の全体量を1とするとき,2つの容器の量が,ある自然数nとkによって,k /2nと1-k /2n =(2n-k)/2nと表せる場合だ」と容易に一般化できよう。実際,水がそのように分かれていたとき,分子のkは奇数でかつk<2n-kだとしても一般性を失わないない。すると,次の段階で水の量は2k/2n= k/2n-1 と(2n-2k)/2n =(2n-1-k)/2n-1となり,分母の肩のベキは必ず小さくなるので,やがて水の量は両方とも 1/2 になる。実は,kが奇数ならば,均等になるまでには,ちょうどn-1回の操作が必要であることも,納得していただけよう。

 さらに,水が入った容器がm個与えられたとき,水の全体量を1とすると,白の騎士の装置で全容器に1/mずつの水を均等に分けて入れられるための必要十分条件は,どの容器i の水量も,共通の分母m2nを用いて,ki /m2n の形の分数に書けることなので,証明にチャレンジされたい。ただし,分子 k1,…,kmの最大公約数は1とする。

 3つの容器のうち2つを等量にする問題は,やや難かしい。解答はほかにも考えられるが,次の方法が,わかりやすくて手間も少ないようだ。容器を水の量を少ない順に並べてA,B,Cとし,その水の量をa,b,cとしよう。a≦b≦c である。

 bがaの倍数の場合が簡単なので,まず,その場合を考えよう。b=naとしnの2進表記が1nk…n2 n1であったとする。つまり,niはどれも0または1で,n = n1+n2・2+ … +nk・2k-1+2kとする。この場合は,最初に左のフラスコにAの水を入れ,右にはBかCの水を代わる代わる入れて k 回操作することで,左のフラスコとBの水を同量の2kaにすることができるのだ。

 bもcも十分多いので,この操作の間,常に水は左に流れ,k回の操作後,左の量が 2ka になることは容易にわかる。問題は右のフラスコにどちらの水を入れるかだ。これは,i 回目の操作では,n iが1ならばBの水,n iが0ならばCの水を入れるといい。i 回目の操作で流れる水の量は,2i-1a だから,ni が0と1のどちらでも,i 回目の操作が終わった段階でBに入っている水の量が(n i+1・2i +…+ nk・2k-1+2k)aであることは帰納法で容易に示せる。従って,k回目の操作が終わった段階でBの水は2ka になる。こうして,左のフラスコの水をAに戻せば,AとBは同量になる。

 例えば(a,b,c )=(1,13,16)としてやってみよう。13は2進表記すると1101 だから,このとき,(左のフラスコの水を毎回Aに戻したとして)上の操作によるA,B,Cの量の変化を記せば,

(1,13,16)→(2,12,16)→(4,12,14)→(8,8,14)

となる。

 では,bがaの倍数でない場合はどうすればよいだろうか。この場合も,b=na+r(0≦r<a) という形には表せる。ただし,上と異なり,r=0ではない。nの2進表記を用いて上と同じ操作を行なうと,左のフラスコには 2kaの水が入るが,Bには2ka+rの水が残る。これは同量ではないが,Bの水を右のフラスコに入れもう一度操作を行なうと,左が 2k+1a,右がrになる。これでは一見うまくいかないように思うが,rをBに戻し,2k+1aをAに戻して,また3つの容器を量の順に並べれば,r<aだから,一番少ない容器の水の量は,最初の状態より減っている。水の量はいつでも整数値だから,これを繰り返せば,やがて2番目に少ない容器の量が一番少ない容器の整数倍になる。

 例えば(a,b,c)=(3,8,10)としてみよう。同様に操作すると,8=2・3+2だから,第 1 段階で

 (3,8,10)→(6,8,7)→(12,2,7)

となる。容器を並び替えて,同じ操作を行えば,

 (2,7,12)→(4,5,12)→(8,1,12)

となる。こうなると8は当然1の倍数だから,最後に

 (1,8,12)→(2,8,11)→(4,8,9)→(8,8,5)

として,同量の8ミリリットルを2つの容器に入れることができる。(3,8,10) からなら,

 (3,8,10)→(3,16,2)→(1,16,4)→(2,15,4)→(4,13,4)

とするほうが,もちろん手早く目的が達せられる。しかし,一般的なアルゴリズムで,効率の良いものを設計するというのはなかなか難しいようだ。

 また,3つの容器の水の量が整数比を持たなくとも,2つの容器の水の量を同じにできることはある。例えば,

 (2+2√2,1,4+2√2)→(4+4√2,1,2)→(3+4√2,2,2)

などだが,こういうことが可能なための条件が簡単に述べられるだろうか?

参考にした本
Mathematical Puzzles:A Connoisseur's Collection(2004)
Mathematical Mind-Benders(2007) P. Winkler著

問題はこちらです