Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651917 | Electronic Notes in Discrete Mathematics | 2015 | 7 Pages |
Abstract
Suppose we are given a set of n balls {b1,…,bn} each colored either red or blue in some way unknown to us. To find out some information about the colors, we can query any triple of balls {bi1,bi2,bi3}. As an answer to such a query we obtain (the index of) a majority ball, that is, a ball whose color is the same as the color of another ball from the triple. Our goal is to find a non-minority ball, that is, a ball whose color occurs at least times among the n balls. We show that the minimum number of queries needed to solve this problem is Θ(n) in the adaptive case and Θ(n3) in the non-adaptive case.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics