リストに過半数ある名前を答える問題
【長いリストに書かれた名前が読み上げられていく。リストには同じ名前が何度も登場し、また順番はばらばらであるとする。リストの過半数を占める名前があったとして、それを特定することができるか。ただし、手元にあるのは、数字を増減させることのできるカウンター（計数器）1つで、また、同時に1つの名前しか覚えていられないとする。（「とっておきの数学パズル」、原典「Finding a Majority Among n Votes」）】
「ほんまにできるんか？」
「『できるか』と訊いている以上はできない可能性があるが
一見どう考えても不可能そうならできるのだろうなあ」
「『できる』という前提で進めてみる」
「過半数を占める名前をAとし
その他の名前をB、C、…とする
→最初に呼ばれた名前を基準としてその名前を記憶しておき
同じ名前が呼ばれたらカウンターを1進めることにする
→最初に呼ばれた名前がAとすると、
Aの呼ばれた数だけカウンターの数字が進む
もしリストに載っている名前の総数がわかれば
この方法でAが過半数だとわかる
（名前の総数の半分よりもカウンターの数が大きいから）
→しかしリストに載っている名前の数は不明
→よってAの数がわかってもそれが過半数だとは言えない
→まして最初に呼ばれた名前がB、C、…のどれかとすると
もしリストに載っている名前の総数を知っていたとしても
それが過半数にならないことしかわからない
→名前は1つしか記憶できないから
過半数を占めているAの名前はわからない
→最初に呼ばれた名前を基準としてずっと使うのは無理そう」
「1つの名前をずっと基準に使うのは難しい
→ある条件を満たすことによって記憶している名前を変える必要がある
→この条件はかなり絞られる
・覚えている名前と同じ名前が呼ばれたとき
・覚えている名前と違う名前が呼ばれたとき
→いや、カウンターの数字にも注意しなければならない
・カウンターの数字が特別な値のときに同じ名前が呼ばれたとき
・カウンターの数字が特別な値のときに違う名前が呼ばれたとき」
「最後に呼ばれた名前がBだったとする
→その場合でも過半数がAであることを示さなければならない
→最後に名前が呼ばれたときに記憶していた名前はA以外にあり得ない
→過半数を占める名前が優先的に記憶されるシステムである
→その判別はカウンターの数である可能性が大」
「カウンターは数字の『増減』が可能
→増やすだけでなく減らすこともできる
→増やす場合と減らす場合で条件分けができる
→以下の使い方の可能性が大
・Aの名前が呼ばれたらカウントを増やす
・A以外の名前が呼ばれたらカウントを減らす
→しかしAという名前が過半数であるとは分かっていない
→A以外の基準でカウントの増減をしなければならない
→今覚えている名前を基準にするしかない
→以下の使い方の可能性が大
・呼ばれた名前が記憶しているものと同じならカウントを増やす
・呼ばれた名前が記憶しているものと違ったらカウントを減らす
→これを踏まえ、記憶する名前を優先的にAにする手段を考える
→呼ばれた名前が記憶しているものと同じなら記憶する名前は変えない
（というかその場合記憶する名前の変更はできない）
→呼ばれた名前が記憶しているものと違うときが問題」
「ここで『カウンターの数字による条件』を使うのか！」
「呼ばれた名前が記憶しているものと違うとき
・カウンターの数が1以上なら記憶している名前を変えない
・カウンターの数が0なら呼ばれた名前を記憶し直す」
「ちょっと実験
呼ばれる名前／カウント／新たに記憶する名前
A／1／A
B／0／A
B／1／B
B／2／B
B／3／B
C／2／B
A／1／B
A／0／B
A／1／A
C／0／A
B／0／A
A／0／A
A／1／A
ここまで常に最多かつ過半数の名前が常に記憶されている
→非常にそれっぽい」
「どう証明するか」
「呼ばれた回数のうちAの呼ばれた回数が
半分以下でスタートしたとしても
リストのm番目までにAとそれ以外が同じ数ずつ出る、
そんな数字mが必ず存在する
かりにA以外の名前がBのみだったとしても
同じ名前が連続で呼ばれる回数はAもBも同じ
→m番目まででカウントは0
→Aは過半数を上回るのでm番目から最後までは
明らかにAの数が多い
→必ずAを記憶した状態で終了する」
「というか単にAを記憶してカウントを増やす回数が
明らかに多い」
「同じ名前を呼ばれたときにはカウントを1進め
違う名前が呼ばれたときには
カウンターの数字が1以上であればカウントを1減らし
カウンターの数字が0であれば呼ばれた名前を記憶し直す」