パズルの国のアリス

続・双子がもらった小切手帳(解答)

 ダムが符号を決めた小切手帳を,ディーが自分に最も有利なように2つに分けるという最初の問題は簡単だ。n枚つづりの小切手帳の場合,全部を相手または自分のものにする場合を含めて,分け方はn通りしかないので,そのすべてを調べてそれぞれの総額の差が最大になるようにすればよい。これをシステマティックに行うには,次のような方法がよいだろう。いま,小切手の額面が先頭から順にa1a2,・・・,anとなっているとしよう。k枚目までの累計額を

と書くことにすれば〔ただしS(0)=0〕,Sk)の表を作るのは,次々に計算していけばよいだけだから易しい。例に挙げた2,−3,−5,2,6, 1の場合,下の表Aのようになる。

小切手帳をk枚目とk+1枚目の間で切り離す場合,一方が受け取る小切手総額はSk)であり,もう一方は

だ。だから,その差|Sn)−2Sk)|が最大になるようにkを選んで切り離し,Sk)とSn)−Sk)のうち大きいほうを受け取ればよい。2,−3,−5,2,6,1の場合,Sn)=3であり,Sk)はk=3のときに最小の−6,k=6のときに最大の3となる。|3−2×3|=3<|3ー2×(−6)|=15だから,k=3を選ぶことにすると,小切手帳は2,−3,−5と2,6,1に分かれ,ディーは先頭の3枚をダムに渡して−6を与え,残りの3枚を取ることで9を得るから,その差は15になる。

 2,3,5,2,6,1の場合,ダムが3と5にマイナス符号を付けるというのは良策とはいえない。問題で述べたように,この場合は6が額面の絶対値の最大だから,うまく符号を付ければ,差を12(=2×6)以下に抑えることができる(この上限はかなりよいものだ。実際,同じ額面Mの小切手ばかりからなる偶数枚つづりの小切手帳が与えられた場合,ダムがどんな符号付けをしても,ディーは2M以上の差をつけて勝利できるということが簡単にわかる。これは読者に考えていただこう)。

 しかし,額面の絶対値の最大がMであるようなどんな場合でも,差が2M以下になる符号の付け方が存在するということの証明は,相当の難問のように思うし,実際にそのような符号の付け方をシステマティックに見つけるというのも容易ではないだろう。

 まず,累計Sk)の絶対値が最小になるように符号を決めていくというアイデアが浮かぶ。例えば,Sk−1)≦0ならk枚目の小切手をプラスとし,Sk−1)>0ならk枚目の小切手をマイナスとすればよい。すると各小切手の額面の絶対値がM以下なので,任意のkに対して|Sk)|はM以下になり

Sn)−2Sk)|
≦|Sn)|+2|Sk)|≦3M

となるから,問題の|Sn)−2Sk)|が3Mで抑えられることは示せる。だが,Sn)とSk)が反対符号でその絶対値がMに近い場合がありうるので,2Mで抑えることは簡単ではない。

 これを解決する巧妙なアイデアは,累計を考えるときに,0から始めるのをやめて絶対値がM以下の任意の値wから始めることだ。つまり,このときのk枚目までの累計をSwk)と書くことにすれば,Sw,0)=w。各小切手の符号は,先ほどと同様に,Swk−1)≦0ならk枚目はプラス,Swk−1)>0ならk枚目はマイナスとする。例として,各小切手の額面の絶対値pkが2,3,5,2,6,1の場合に,w=−6,−5,−4のときのSwk)を示すと,下の表Bのようになる。

 各Swk)の絶対値は明らかにMを超えることがない。また,上述のように符号を付けた小切手のk枚目までの累計額をSk)とすれば,明らかにSwk)=wSk)が成り立つ。従って,そのように符号を付けた小切手帳については,wSwn)=0ならば

  |Sn)−2Sk)|
=|2w+Sn)−2(wSk))|
=|wSwn)−2Swk)|
=2|Swk)|≦2M

となり,どこで切り離しても,その差額が2M以下になることが保証される。

 以下,wSwn)=0となるw∈[−MM]が実際に存在することを示そう。fw)=Swn)はwについての関数である。連続ですらないが,それほどめちゃくちゃな動きをするわけではなく,実はほとんどの部分ではwCCは定数)という形の一次関数である。実際,表Bの場合,容易に想像されるように−6≦w≦−5のときはfw)=Sw,6)=w+3である。

 問題は,fw)が不連続になる点wがあることだが,それはあるkについてSwk)=0となっている場合に起こる。つまりwがその点を通過するときにk+1枚目以降の小切手の符号が変わるからだ。表Bでは,w=−5のときにS(−5,2)=0となり,そこを境目に3枚目から先の小切手の符号が変わる。ところが幸いにして,この変化もめちゃくちゃなわけではなく,k枚目より後ろの小切手が一斉に符号を反転させるのだ。その結果fw)の符号も反転するが,その後はまたしばらくfw)=wCという形に戻る。

 こうして,yfx)のグラフは,ほとんどいたるところで傾き1の直線を描き,ときどきx軸を挟んで対称点に跳ぶということになる。実際,例えば先の各額面の絶対値が2,3,5,2,6,1の小切手帳の場合に,yfx)のグラフを描いてみると,下図左のようになる。このグラフからだけではわかりにくいので,y=|fx)|のグラフを描くと下図右の破線と実線からできた折れ線になる。これは連続だから,y=−xのグラフと必ず交わる。

 同図のようにy=−xy=|fx)|=fx)の部分と交点を持てば,そのx座標wwfw)=wSwn)=0が達成される。あまり起こらないことだが,y=−xy=|fx)|=−fx)の部分と交点を持つ場合がどうなるか気になるので,その場合を検討しておこう。その場合,y=−fx)(グラフの破線部分)とy=−xの傾きは同じだから,折れ線y =|fx)|とy=−xはある区間で完全に重なっている。定義よりfw) が左に連続なことがわかるので,その重なり部分の最左点でグラフy=−xはグラフyfx)に接し,そのx座標wwfw)=0がやはり達成される。

 以上により,あるw∈[−MM] でwfw)=0となることが示された。例えば各小切手の額面の絶対値が2,3,5,2,6,1の場合,上図右よりw=−3.5のときにwfw)=0となるので,その場合のSwk)を表にすると下の表Cとなり,小切手の額面は2,3,−5, 2, 6,−1とするのがよいことがわかる。

実際,このときの|Sn)−2Sk)|はk=5のときが最大で2×4.5=9となるが,2×6=12よりも小さい。ディーは5枚目と6枚目の間で小切手帳を切り離し,最後の6枚目をダムに渡すのがよいが,これ以上にダムとの差を広げることはできない。

 ダムにとって,この符号付けはあまり不満のないものとはいえようが,残念ながら,最善の結果をもたらすという保証はない。最善の結果が欲しいなら,2n通りの符号付け全部を調べるしかないのだろうか? また,fx)のグラフを描くことでwfw)=0を満たすwを見つけられ,そのwに対する符号付けを考えることで,差が2M以下になる符号付けが得られることはわかった。しかし,fx)のグラフを描くことはそれほど簡単だろうか? グラフの不連続点が2n個近くもあれば,全部の符号付けを考えるのと大差ないことになる。不連続点の数があまり多くないという保証はあるだろうか? このあたり読者の知恵を借りたいところである。

問題はこちらです