# Finding a majority ball with majority answers

###
Mate Vizer

MTA Alfred Renyi Institute of Mathematics

####
Daniel Gerbner

MTA Alfred Renyi Institute of Mathematics

####
Balazs Keszegh

MTA Alfred Renyi Institute of Mathematics

####
Balazs Patkos

MTA-ELTE Geometric and Algebraic Combinatorics Research Group

####
Domotor Palvolgyi

Department of Computer Science, Eotvos Lorand University

####
Gabor Wiener

Department of Computer Science and Information Theory, Budapest University of Technology and Economics

PDF

**Minisymposium:**
GENERAL SESSION TALKS

**Content:**
Suppose we are given a set of $n$ balls $\{b_1,\ldots,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 n2$ 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)$ inthe non-adaptive case. We also consider some related problems.