Istituto di Informatica e Telematica     
Aigner M., De Marco G., Montangero M. The Three Color Plurality Problem. In: 21st International Symposium on Theoretical Aspects of Computer Science (Montpellier, 2004). Proceedings, article n. 1. Springer, 2004.
The plurality problem with three colors is a game between two participants: Paul and Carol. Suppose we are given n balls colored with three colors. At any step of the game, Paul chooses two balls and asks whether they are of the same color, whereupon Carol 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(n) does Paul have to ask in the worst case? We show that 3n/2 − 2 ≤ L(n) ≤ 5n/3 −2.
Subject theory of computer science
Three colors
G. Mathematics of Computing

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional