Variants of the majority problem

✍ Scribed by Martin Aigner

• Book ID: 104294163
• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 324 KB
• Volume: 137
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(03)00186-0

✦ Synopsis

Suppose we are given n balls colored with two colors. How many color-comparisons are needed to produce a ball of the majority color? The answer (ÿrst given by Saks and Werman) is

, where B(n) is the number of 1's in the binary representation of n. We consider in this paper several generalizations and variants of the majority problem such as producing a k-majority ball, determining the color status of all balls, non-adaptive versions and the closely related liar problem. ?