The {em plurality problem} is a game between two participants: Paul and Carole. We are given $n$ balls, each of them is colored with one out of $c$ colors. At any step of the game, Paul chooses two balls and asks whether they are of the same color, whereupon Carole answers yes or no. The game ends when Paul either produces a ball $a$ of the plurality color (meaning that the number of balls colored like $a$ exceeds those of the other colors), or when Paul states that there is no plurality. How many questions $L_c(n)$ does Paul have to ask in the worst case? For $c=2$, the problem is equivalent to the well known {em majority problem} which has already been solved cite{SW}. In this paper we show that $ 3 lfloor n/2 floor - 2 leq L_3(n)leq lfloor 5n/3 floor-2.$ Moreover, for any $cleq n$, we show that surprisingly the naive algorithm for the plurality problem is asymptotically optimal.
The Plurality Problem with Three Colors and More
DE MARCO, Gianluca;
2005-01-01
Abstract
The {em plurality problem} is a game between two participants: Paul and Carole. We are given $n$ balls, each of them is colored with one out of $c$ colors. At any step of the game, Paul chooses two balls and asks whether they are of the same color, whereupon Carole answers yes or no. The game ends when Paul either produces a ball $a$ of the plurality color (meaning that the number of balls colored like $a$ exceeds those of the other colors), or when Paul states that there is no plurality. How many questions $L_c(n)$ does Paul have to ask in the worst case? For $c=2$, the problem is equivalent to the well known {em majority problem} which has already been solved cite{SW}. In this paper we show that $ 3 lfloor n/2 floor - 2 leq L_3(n)leq lfloor 5n/3 floor-2.$ Moreover, for any $cleq n$, we show that surprisingly the naive algorithm for the plurality problem is asymptotically optimal.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
