2005
Three optimal algorithms for balls of three colors
DVORAK, Z; V JELINEK; Daniel KRÁĽ; J KYNCL; M SAKS et al.Základní údaje
Originální název
Three optimal algorithms for balls of three colors
Autoři
DVORAK, Z; V JELINEK; Daniel KRÁĽ; J KYNCL a M SAKS
Vydání
STACS 2005, PROCEEDINGS, BERLIN, SPRINGER-VERLAG BERLIN, 2005, 0302-9743
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Utajení
není předmětem státního či obchodního tajemství
Označené pro přenos do RIV
Ne
UT WoS
Změněno: 6. 11. 2020 11:05, Mgr. Darina Boukalová
Anotace
V originále
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.