Abstract:
Suppose we are given a set of n balls {b_1,… ,b_n} each colored either red or blue in some way unknown to us. 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 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 non-minority ball, that is, a ball whose color occurs at least 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.
Joint work with D. Gerbner, B. Keszegh, D. Palvolgyi, B. Patkos and G Wiener
|
