The majority game with an arbitrary majority

The kk-majority game is played with  nn numbered balls, each coloured with one of two colours. It is given that there are at least  kk balls of the majority colour, where kk is a fixed integer greater than n/2n/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)2(n−k)−B(n−k), where B(m)B(m) is the number of 1s in the binary expansion of mm. However his proof contains an error. We give an alternative proof of this result, which generalizes an argument of Saks and Werman.