Personal Comment: Really hard. No special advise.
Pippin Town Enigma
What we know: Once upon a time, there was a little town called PippinTown. In PippinTown, there lived several masters and their apprentices.
Each master was an expert in his area and did not speak with other masters. Each master, though, had one apprentice.
One day, the mayor of the town called all the masters into the town square for a meeting. The mayor said, "I have some sad
news to report. I have been informed that there is AT LEAST ONE apprentice who is a thief and has been stealing from his
master. I have verified it myself." Surprisingly, the masters were not surprised. Each master knew which of the other
apprentices were thieves, but did not suspect his own.
"Now," the mayor continued, "to avoid name calling, each master is responsible for reporting his own apprentice if he discovers
that his apprentice is a thief." The masters agreed that this was a good plan. "On the first day of the upcoming year, we will
meet here again in the town square at noon. If any master knows that his apprentice is a thief, he should declare so. If no one
comes forth, everyone can go home, and we will meet again each day until the thieves have been exposed."
Enigma:
Assuming that the mayor's words are true, on which day is each of the thieves exposed? Hint: the number of masters and
apprentices does not matter.
Solution:
The problem is best approached systematically. A haphazard attempt at a solution makes the problem more difficult than it
really is. For the sake of argument, suppose there are 100 masters. It turns out that the number of masters does not matter, but
a concrete number makes the explanation easier to give.
On the first day of the new year, all the masters meet in the town square....
First, suppose there is exactly one apprentice who is a thief. On the first day, the thief's master looks around the town square at
the other masters. None of the other masters' apprentices are thieves, and he sees this. The mayor, though, said that there is at
least one thief. Since he sees no thieves, the master is forced to conclude that his own apprentice is a thief. The master declares
his apprentice a thief. The other masters, on the other hand, know that his apprentice is a thief. They think to themselves, "Ah
ha! His apprentice is the thief whom the mayor mentioned" and take no action.
If there is 1 thief, he is declared on the first day.
Next, suppose there are exactly 2 apprentices who are thieves. On the first day, the masters meet in the town square. The 2
masters whose apprentices are thieves each look at the other and think, "Ah ha! His apprentice is the thief whom the mayor
mentioned." Each master waits for the other to denounce his own apprentice. The 98 other masters see the 2 masters and keep
quiet. They assume that the 2 apprentices are the only thieves, since the masters think they see all the thieves and do not
suspect their own apprentices. Because no one says anything, the mayor sends everyone home, without anyone declared a
thief.
The following day, all the masters return. The 2 masters are puzzled by the events of the previous day. If there were exactly one
thief, they each independently reason, that thief would have been declared on the first day (as the first case above). Since no
thief was declared, it must be true that there is more than one thief. In other words, there are at least 2 thieves. Each of the 2
masters looks around and sees only one suspect -- the other master. There are at least 2 thieves, so each master is forced to
conclude that his own apprentice is the unseen thief. Both masters declare their apprentices to be thieves. (Something to think
about: does it matter if one master declares before the other?)
If there are 2 thieves, both are declared on the second day.
If there are 3 thieves, the same type of reasoning occurs. On the first day, all 3 masters wait for the other masters to denounce
their own apprentices. Since no one suspects his own apprentice, none of the masters says anything, so everyone goes home.
On the second day, the masters know that there must be at least two thieves. Each of the 3 masters sees the other two and
believes that those two masters' apprentices are the thieves. Again, every master waits for the others to declare their own
apprentices but, again, no one says anything. On the 3rd day, each master realizes that there must be more than two thieves --
that is, 3 or more thieves. Seeing only two others, each is forced to conclude that his own apprentice is a thief, and each of the
3 masters declares his apprentice a thief.
If there are 3 thieves, all 3 are declared on the third day.
The general pattern is that, if there are N thieves, all N thieves are declared on the Nth day. No thief is declared before the Nth
day, and no thief is declared after the Nth day. Notice that the overall number of masters does not matter.
See who got this right
Previous
Enigma | Enigma
Index | Next Enigma
This window to the Fourth Dimension is hosted by Geocities