Variants of the majority problem
β
Martin Aigner
π
Article
π
2004
π
Elsevier Science
π
English
β 324 KB
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 a