| Once upon a time, there was a little
town called Pippin- Town. 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."
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:
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. |
