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?

5 Comments

1. 1. NegativeZero 12:25 AM 1/8/08

   1. has me stumped, however I think 2. is quite possible. Start all three locks at 0. Taking a letter off the pile one at a time check it against the three positions on the table. If a position is vacant, place it there and increment the lock by one. If the new letter matches one of the ones on the table, increment the corresponding lock. Otherwise, select the position on the table with the lowest value on the lock. Replace the letter at that position with the new letter, and set that lock back to 1, placing the replaced letter onto your 'used' stack. If something occurs 334 or more times it should dominate the set to the point that it isn't replaced as often and should be the one with either the highest-value or second highest-value lock. You can then use your second pass to count how many times the most common two actually occurred. I'm sure there are cases where this might not work, but for the majority of the time you would arrive at your desired answer.

   Reply | Report Abuse | Link to this

2. 2. jkhereford 02:19 PM 1/8/08

   Solution to 1: Take a laptop and portable flat bed scanner. Scan all your papyri within the two hour time frame their giving you. Handle your comparison and analysis later, possibly with the aid of an image recognition algorithm.

   Reply | Report Abuse | Link to this

3. 3. rhinotlc 02:00 PM 1/9/08

   Simple. Look through all 999 pages of glyphs one at a time. At the end of that first scan, it should be immediately obvious if you saw one glyph far more than any other (500 is just over half of 999). On your second pass, put those glyphs into pile 2, put all others on pile 3. After pass 2, count the number of pages in pile 2. Alternately, if you won't have time to recount pile 2 (effectively being a third pass), use the locks to count the pages of that frequent glyph.

   Reply | Report Abuse | Link to this

4. 4. norbertf 05:02 PM 1/20/08

   The text for the solution to the Warm-Up is imprecise:
   There could be 500 different glyphs but still one of them could occur 500 times, 499+500=999.
   Only once you would need a 501st stack are you sure that no one glyph can occur more than 500 times.

   Reply | Report Abuse | Link to this

5. 5. gospel_alien 12:58 AM 1/23/08

   Three is the best solution. If you went through the papyri could you actually remember which glyph was repeated and how many times? A lock will not go back through and pull the one you think is being repeated.

   Reply | Report Abuse | Link to this