The plurality problem with three colors is a game between twoparticipants: 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 3 \lfloor n/2 \rfloor - 2 <= L(n) <= \lfloor 5n/3 \rfloor-2.

The Plurality Problem with Three Colors / M., Aigner; G., De Marco; Montangero, Manuela. - STAMPA. - 2996:(2004), pp. 513-521. (Intervento presentato al convegno 21st Annual Symposium on Theoretical Aspects of Computer Science tenutosi a Montpellier, FRANCE nel APR, 2004) [10.1007/978-3-540-24749-4_45].

### The Plurality Problem with Three Colors

#### Abstract

The plurality problem with three colors is a game between twoparticipants: 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 3 \lfloor n/2 \rfloor - 2 <= L(n) <= \lfloor 5n/3 \rfloor-2.
##### Scheda breve Scheda completa Scheda completa (DC)
2004
21st Annual Symposium on Theoretical Aspects of Computer Science
Montpellier, FRANCE
APR, 2004
2996
513
521
M., Aigner; G., De Marco; Montangero, Manuela
The Plurality Problem with Three Colors / M., Aigner; G., De Marco; Montangero, Manuela. - STAMPA. - 2996:(2004), pp. 513-521. (Intervento presentato al convegno 21st Annual Symposium on Theoretical Aspects of Computer Science tenutosi a Montpellier, FRANCE nel APR, 2004) [10.1007/978-3-540-24749-4_45].
File in questo prodotto:
Non ci sono file associati a questo prodotto.
##### Pubblicazioni consigliate

I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11380/465770`
• ND
• 8
• 3