DIMACS TR: 2004-48
Three Optimal Algorithms for Balls of Three Colors
Authors: Zdenek Dvorak, Vit Jelinek, Daniel Kral, Jan Kyncl and Michael Saks
We consider a game played by two players, Paul and Carol. Carol fixes
a coloring of n balls with three colors. At each step, Paul chooses
a pair of balls and asks Carol whether the balls have the same color.
Carol truthfully answers yes or no. In the Plurality problem, Paul
wants to find a ball with the most common color. In the Partition
problem, Paul wants to partition the balls according to their colors.
He wants to ask Carol the least number of questions to reach his goal.
We find optimal deterministic and probabilistic strategies for the
Partition problem and an asymptotically optimal probabilistic strategy
for the Plurality problem.
Paper Available at:
DIMACS Home Page