問題
ある投票が行われた。
投票された幼女の名前が1票ずつ読まれていく。
いま、投票数の過半数（全体の半分より多い数）を得た幼女がいるならば、その名前を特定したい。
しかしあなたが持っているのは1ずつ数字を増減できるカウンターのみ。
さらに、あなたは同時に1つの名前しか覚えられない。
どうすればよいか？
さあ、解いてみよう！
ただよう難問感。
とてもシンプルな問題ですが、どうやればいいのか方向性がまったく見えません。
そもそも「一度に覚えていられる名前は1つだけ」とかもう解かせる気がない。
「1つずつ読まれていく名前」
「1ずつプラスマイナスできるカウンター」
「1つしか覚えられない名前」
登場する要素はそれほど多くありません。
うまく組み合わせて、「全体の半分より多く登場する幼女」の名前を最終的に特定しましょう。
ヒントはなし。
少し下にスクロールすると答えがあります。
正解
- 開始時にカウンターを0にセットする
- カウンターが0の時、「聞いた名前」を記憶してカウンターを+1する
- カウンターが1以上の時、「聞いた名前」が『記憶している名前』と同じだったらカウンターを+1する
- カウンターが1以上の時、「聞いた名前」が『記憶している名前』とちがったらカウンターを-1する ※ただし『記憶している名前』はそのまま
投票数の過半数を占める幼女がいる場合、最後に『記憶している名前』がその幼女の名前である。
解説
「名前が多く出てくる幼女をなるべく長く覚えておく」というのが基本戦略です。
読み上げられた名前が、記憶している名前と同じかどうか。
同じだったらカウンターを+1。
ちがったらカウンターを-1。
ここに、「1つしか覚えられない名前を入れ替えることができるのはカウンターが0の時だけ」という気づきにくいトリックを組み合わせます。
カウンターが0になるタイミングは以下の2つ。
- スタート時
- カウンターが1の時に「聞いた名前」が『記憶している名前』とちがう時(※)
(※)の時、カウンターは0になりますが『記憶している名前』を変えていないことに注意してください。
これにより『記憶している名前』をギリギリまで長く覚えておけるという効果が生まれます。
さて。
この手順では、1回しか読まれなかった名前を覚えたまま終了することもあります。
たとえば幼女A,B,Cの名前が「A,A,B,B,C」の順で読まれると、最終的に（1回しか出てこなかった）幼女Cの名前を覚えたまま終わってしまいます。
ですが、全体の半分より多く呼ばれる幼女がいる場合、この手順をつかえば最後に記憶しているのは必ずその幼女の名前です。
なぜか？
「全体の半分より多く読まれる幼女」の名前を覚えている時、カウンターを減らす回数よりも増やす回数の方が多いからです。
たとえば幼女A,B,Cの名前が「A,A,B,B,B,B,C」の順で読まれるとしましょう。
※「読まれる名前」： 記憶している名前, カウンターの数字
- 「スタート」：無し,0
- 「Aです」：A,1
- 「Aです」：A,2
- 「Bです」：A,1
- 「Bです」：A,0
- 「Bです」：B,1
- 「Bです」：B,2
- 「Cです」：B,1
- 「終了」
このように、終了時には必ず「全体の半分より多く読まれた幼女B」の名前が記憶されています。
読まれる名前の順序に関わらず絶対にそうなります。
なお、この手順は「全体のちょうど半分だけ読まれる幼女」が2人いる時には使用できません。
あくまでも「過半数（全体の半分より多い数）の幼女」がいる場合のみに有効です。
まとめ
問題を解くための手順を定式化したものを「アルゴリズム」と言います。
本問はアルゴリズムの名問として知られており、論理的に考える力を鍛えるにはもってこいの一問となっています。
あなたは解けましたか？
ぼくは解けませんでした。
参考
問題の初出：
1981年6月の『Journal of Algorithms』
解答：
Michael J. Fischer, Steven L. Salzbergの論文『FINDING A MAJORITY AMONG N VOTES』
解説：
Peter Winkler 『MATHEMATICAL PUZZLES』より一部抜粋
140字以内の問題文
投票が行われた
投票された幼女の名前が1票ずつ読まれていく
いま、投票数の過半数を獲得した幼女がいるならば、その名前を特定したい
しかしあなたが持っているのは1ずつ数字を増減できるカウンターのみ
さらに、あなたは同時に1つの名前しか覚えられない
どうする？
