ADVERTISEMENT
latest stories:

January 2008 Puzzle Solution

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.

Share this Article:

Comments

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Scientific American Holiday Sale

Give a Gift &
Get a Gift - Free!

Give a 1 year subscription as low as $14.99

Subscribe Now! >

X

Email this Article

X