Minimal number of comparisons to determine larger set

Question

There are $2n+1$ balls in a row, on each one printed either $1$ or $0$, but we can not see what is written - we can only see the position in which they are placed. I need to take out a ball that belong to the number printed more times, and I can only ask about two certain balls if they are the same or not. My goal is to do so in minimal number of comparisons in the worst case. Trivial solution takes $2n$ comparisons. Any ideas to do better?

Answer 1

You can justify $2n$ as a worst case. If you make a graph with the balls vertices and comparisons edges it can't be connected unless there are that many edges. If it isn't connected you can flip the identities of any component without changing the results. If things are balanced closely, that will change the answer.

For the average, you can start with $n$ comparisons of disjoint pairs. Any pair which comes up different can be discarded. If the numbers of $0$s and $1$s are close, this should be about half the pairs, saving you later comparisons. Repeating this gets you close to $n+1$ comparisons.