You are in a small room in a museum with 999 papyri. Each one displays a single Egyptian hieroglyph. Unfortunately, your familiarity with ancient Egyptian is limited to a few children’s books and several Hollywood films. As the haughty museum curator has reminded you several times, you are an amateur.
In fact, your only certain ability is to look at two hieroglyphs and decide whether they are the same or not. Fortunately, all these hieroglyphs were written by the hand of one very careful scribe, so two hieroglyphs that are the same will look exactly identical.
Your task is to find out whether any single hieroglyph appears on more than half the papyri (i.e., 500 times or more) and if so, which one. Based on your previous research, that single hieroglyph would provide a clue to the existence of an as-yet undiscovered tomb.
The impatient curator gives you only two hours, basically enough time to go through the papyri twice. The 999 papyri are piled up on the left side of a desk; to the right of the desk there is space for one more pile of 999. The middle of the desk itself has room for at most three papyri. The curator insists that you be mindful of the following rules: You should never insert a papyrus in the middle of a pile, because they are very delicate, so you should always put a papyrus on top of a pile or on an empty surface.
The room fits the desk, a chair and nothing else. You have brought with you a lock having three wheels, each of which ranges from 0 to 9. You might find that useful.
Warm-Up:
What would you do if you had space enough for 500 piles of papyri?
Solution:
Put each papyrus on a pile if its glyph matches the one at the top of that pile. Otherwise, start a new pile. If you fill up all 500 of the spaces for piles, then you have at least 500 different kinds of glyphs, so no single glyph could be written on 500 papyri. Otherwise count the contents of each pile and see if any holds 500 or more papyri. (Remember each papyrus has only one hieroglyph.) Alternatively, count the number of papyri in the largest pile.
Problems:
The actual room is as described above: a pile on a desk that has space for one other pile and perhaps three other papyri. You also have the combination lock with three wheels enabling you to count to 999 and space for two piles on the desk. You want to discover whether there is a majority glyph and if so, which it is and how often it appears.
1. How do you do it?
Now here is a problem whose answer I don't know.
2. Suppose you were interested in at least one glyph that appeared at least 334 times (i.e., just over 1/3). Could you find it in two hours (the time it takes to go through the pile twice) if you had three locks instead of one but otherwise the same physical situation?
