Finding a non-minority ball with majority answers

Abstract

Suppose we are given a set of $n$ balls $\{b_1,\dots ,b_n\}$ each colored either red or blue in some way unknown to us. To find out some information about the colors, we can query any triple of balls $\{b_{i_1},b_{i_2},b_{i_3}\}$. As an answer to such a query we obtain (the index of) a {\em majority ball}, that is, a ball whose color is the same as the color of another ball from the triple. Our goal is to find a {\em non-minority ball}, that is, a ball whose color occurs at least $\frac{n}{2}$ times among the $n$ balls. We show that the minimum number of queries needed to solve this problem is $\Theta (n)$ in the adaptive case and $\Theta (n^3)$ in the non-adaptive case. We also consider some related problems.