The majority game with an arbitrary majority

Mark Wildon, John R. Britnell

Research output: Contribution to journalArticlepeer-review

25 Downloads (Pure)

Abstract

The k-majority game is played with n numbered balls, each coloured with one of two colours. It is given that there are at least k balls of the majority colour, where k is a fixed integer greater than n/2. On each turn the player selects two balls to compare, and it is revealed whether they are of the same colour; the player’s aim is to determine a ball of the majority colour. It has been correctly stated by Aigner that the minimum number of comparisons necessary to guarantee success is 2(n−k)−B(n−k), where B(m) is the number of 1s in the binary expansion of m. However his proof contains an error. We give an alternative proof of this result, which generalizes an argument of Saks and Werman.
Original languageEnglish
Pages (from-to)1-6
Number of pages6
JournalDiscrete Applied Mathematics
Volume208
Early online date11 Apr 2016
DOIs
Publication statusE-pub ahead of print - 11 Apr 2016

Cite this