続・双子がもらった小切手帳（問題）
アリスがトウィードルダムとトウィードルディーの双子を久しぶりに訪問すると，2人ともそれぞれの机の前に座って何やら計算に余念がない。何の計算をしているのかと聞くと，ダムとディーは手元の小切手帳をひらひらと振って見せ，「例によって伯父さんがそれぞれにくれたんだけど……これが問題なんだ」という。
話をさらに聞いてみると，各小切手には金額は書いてあるが，なぜかサインがしてない。ダムとディーが額面にプラスかマイナスの符号を書き込めば，伯父がサインをするという。「額面がマイナスの小切手？ そんなバカな」とアリスは思ったが，不思議の国や鏡の国でならそんなこともあるかもしれない。それにしても，それなら2人ともすべての小切手にプラスの符号を書いて，さっさとサインしてもらえばよい。
アリスがそう提案すると, 「そうはいかないのさ」とダム。ディーを指さし，「伯父さんはサイン後の小切手帳をいったんあいつに渡すっていうのさ。あいつはそれをそのまま受け取ってもよいし，全部を俺につき返してもよい。あるいは小切手帳をどこか1カ所で2つに切り離し，一方を自分のポケットに入れて，もう一方を俺に渡してもよい。だから，全部プラスなんかにしたら，あいつは全額を自分のものにして，俺には何にもなしさ」。それを聞いてディーがいい返す。「ふん，全部プラスなら，おまえだって独り占めするくせに」。
「なるほど」。アリスには伯父の考えが読めてきた。額面を全部プラスにし，サイン後に渡された小切手帳を切り離さずにそれぞれのものにするという協定を2人が結べば，彼らにとって一番得なはずだ。ところが，そういう伯父の期待を察することができても，2人にはそんな協定をする意思はかけらもない。この小切手ゲームの性質上，相手のほうが有利になるのは仕方がないので，ダムもディーも，たとえ自分の総額がマイナスになろうと，相手の得る総額との差を最小にすべく，必死に符号の付け方を工夫していたわけだ。
こんな不毛な競争に読者を巻き込むのは申し訳ない気もするが，知恵を拝借したい。まずウォーミングアップとして，ダムが符号を書き込んで金額が確定した小切手帳があるとして，ディーが自分の得る総額を最大にするには小切手帳を切り離す場所をどのように決めるのがよいかを考えていただこう。例えば6枚つづりで各小切手の額面が2，−3，−5，2，6，1だとしたら，どこで切り離すのがよいだろうか？ これは（数値の加減や比較が単位時間でできるとして）小切手帳のつづり枚数に比例する計算量で解けるはずだ。
次に，符号を付けるダムの側の戦略を考えていただこう。一般に小切手帳がn枚つづりの場合，各小切手への符号の付け方の総数は2n通りある。もちろん，そのすべてを上のやり方で調べれば最善解が求まるが，もう少しマシな（nの多項式くらいの計算量ですむ）方法があるかどうかを筆者は知らない。ただ，小切手の額面の（絶対値の）最大がMの場合，ディーとダムの得る総額の差が2M以下になるような符号の付け方が必ず存在する。読者にはそのことを証明していただきたい。
答えは，2018年7月号に掲載
