気になっている問題

昨日，解法と共に知った問題．メモ．

n個の要素が与えられる．
また，2つの要素を受け取り，同じか否かを判定する判定機が与えられる．
この判定機を用いて n/2よりも多く同じものがあるかを判定したい．
計算時間は判定機の使用回数とする．
例）
{A, A, B, C} = False.
{A, A, A, B} = Ture.
{A, A, A, B, C} = Ture.

判定機は同値性判定を行なうのであって，比較はできない（主に[1]に関係してくる）．

(1) O(n log n)の判定アルゴリズムを構成せよ．
(2) O(n)の判定アルゴリズムを構成せよ．
(3) 「n/3より多く同じものがあるか判定せよ」 という問題を考えた場合，O(n)のアルゴリズムは存在するか．

(1), (2)の答えは知っている．
(1)は易しめ，(2)は結構難しい．
自分は，直観的には線形でできると思わなかった．はじめて考えた人はエライ．

問題は(2)を拡張して，(3)ができるか．

できそうなんだけどなあ．

追記 2010年 11月 30日 火曜日 21:19:13

id:yambiと議論した結果，解けた．