Problem of the Week 1198

Determine the Majority

A sequence of 1198 names (not all distinct) is going to be read out to you, and you are told that one name is in the majority, i.e., it occurs at least 600 times. You have a counter that starts at 0 and that you can increment or decrement whenever you hear a name. But your short-term memory is very low: you can remember only a single name at any given time (but when you hear a name you can check if it is the same as the one in your memory).

Find a strategy that, after all names are read, will allow you to declare the name of the majority person.

Source: M. J. Fischer and S. L. Salzberg, Finding a majority among n votes, J. of Algorithms 3:4 (Nov 1989) 362-380. Also in P. Winkler, Mathematical Puzzles, A Connoisseur's Collection, (A K Peters), p. 104.

[View the solution]