On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
Solution:
1. We are going to view the lock wheels as a counter from 0 to 999. We reset it to 000 at the beginning. We view the leftmost wheel as the hundreds place, the second from leftmost wheel as the tens place, and the rightmost wheel as the ones place.
Take the top glyph and put it on the center of the desk. Set the counter to 1 (001 read from left to right). Then proceed according to this algorithm:
After the top glyph and until the end of the left pile,
take the next glyph g
if g matches the glyph on the center of the desk then
put g on the right pile
add one to the counter
else
subtract one from the counter
if the counter value is greater than 0
move g to the right pile
else if the counter value is 0
move the papyrus from the desk to the right pile
put g on the center of the desk
set the counter to 1
end if
end if
After passing through all the papyri in the left pile, there will be one papyrus on the desk and 998 on the right pile. Set the counter to 1 (001) and count the number of occurrences of the glyph (that is, the number of papyri) in the center of the desk. If the counter value is 500 or more, that glyph is a majority. If not, then no glyph is in the majority.
Why does this work? Suppose that some symbol appears at least 500 times. Then it will be on the center of the desk after emptying the left pile, because it will enjoy 500 increments (additions of one) and suffer at most 499 decrements (subtractions of one). Any other symbol appearing at most N < 500 times will suffer more than N decrements. If no symbol is in the majority, then the second pass will show a count below 500.
Further reading:
The technical report "A Fast Majority Vote Algorithm" by J. Strother Moore (University of Texas technical report 32 from 1981) is the source of this algorithm. A whole literature of "heavy hitter" algorithms has followed. In that literature, the paper of G. Manku and R. Motwani called "Approximate frequency counts over data streams" from VLDB 2002 contains a suggestive approach to the second problem. You can find both papers through your favorite search engine.
