A plurality problem with three colors and query size three |
| |
Affiliation: | 1. Alfréd Rényi Institute of Mathematics, Budapest, Hungary;2. Department of Computer Science, ELTE, Budapest, Hungary |
| |
Abstract: | The Plurality problem - introduced by Aigner - has many variants. In this article we deal with the following version: suppose we are given n balls, each of them colored by one of three colors. A plurality ball is one such that its color class is strictly larger than any other color class. Questioner asks a triplet (or a k-set in general), and Adversary as an answer gives the partition of the triplet (or the k-set) into color classes. Questioner wants to find a plurality ball as soon as possible or show that there is no such ball, while Adversary wants to postpone this.We denote by the largest number of queries needed to ask in the worst case if both play optimally. We provide an almost precise result in the case of even n by proving that for even we have and for odd we haveWe also prove some bounds on the number of queries needed to ask in the case . |
| |
Keywords: | Plurality problem Partition problem Worst case analysis |
本文献已被 ScienceDirect 等数据库收录! |
|