首页 | 本学科首页   官方微博 | 高级检索  
     


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 Ap(n,k) 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 n4 even we have34n?2Ap(n,3)34n?12, and for n3 odd we have34n?O(log?n)Ap(n,3)34n?12.We also prove some bounds on the number of queries needed to ask in the case k3.
Keywords:Plurality problem  Partition problem  Worst case analysis
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号