# The Dominant Glyph

Image: Cartoon by Cloe Liane Shasha

• ### Why Is the Penis Shaped Like That?

Why do testicles hang the way they do? Is there an adaptive function to the female orgasm? What does it feel like to want to kill yourself? Does “free will”...

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?

View
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.

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.

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.

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.

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.

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Click one of the buttons below to register using an existing Social Account.

## More from Scientific American

• The Artful Amoeba | 2 hours ago

### For Plants, Polyploidy Is Not a Four-Letter Word

• Expeditions | 4 hours ago

### Chimps in Uganda: Resilience

• Guest Blog | 8 hours ago

### Dear American Consumers: Please don t start eating healthfully. Sincerely, the Food Industry

• Dog Spies | 9 hours ago

### Dogs and Cats in the Home: Happiness for All?

• News | 10 hours ago

More »

## Latest from SA Blog Network

• ### For Plants, Polyploidy Is Not a Four-Letter Word

The Artful Amoeba | 2 hours ago
• ### Chimps in Uganda: Resilience

Expeditions | 4 hours ago
• ### Dear American Consumers: Please don t start eating healthfully. Sincerely, the Food Industry

Guest Blog | 8 hours ago
• ### Dogs and Cats in the Home: Happiness for All?

MIND
Dog Spies | 9 hours ago
• ### Science in Aggregate: Week 20

Overthinking It | 10 hours ago

## Science Jobs of the Week

The Dominant Glyph

X

### Subscribe Today

Save 66% off the cover price and get a free gift!

X

X

###### Welcome, . Do you have an existing ScientificAmerican.com account?

No, I would like to create a new account with my profile information.

X

Are you sure?

X