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.
In this problem, we know that if there is exactly 1 thief, we can catch him on the first day because there is at least 1 thief. (How does the solution change if we do not know there is at least 1 thief?) Thus, the base case is that 1 thief can be caught on the first day.
Knowing only how to catch up to N thieves, we can catch N+1 thieves as well. Suppose there are N+1 thieves, but we only know how to catch up to N thieves. We try our technique, but on the day we are supposed to catch the thieves, our technique fails because the number of thieves is not less than N. It must be the case, then, that there are more than N thieves; otherwise, we would have caught them. Each of the N+1 masters with an apprentice thief sees only N thieves, but he knows there are more than N thieves! The next day, each master is forced to conclude that his own apprentice is a thief, so he denounces his apprentice -- the N+1 thieves are declared one day after N thieves can be declared! This conclusion is the inductive step.
Putting the pieces together, we know how to catch 1 thief, and we catch him on the 1st day. By the second line of reasoning, we know how to catch 2 thieves, and will do so on the second day. Since we know how to catch 2 thieves, we can catch 3 thieves (also by the second line of reasoning) on the 3rd day. We can catch 3 thieves, so we can catch 4 as well on the 4th. The reasoning continues for any number of thieves so, by mathematical induction, we can catch any number of thieves, and we know the day is equal to the number of thieves.
For advanced study, this problem also represents a problem in knowledge systems -- individual knowledge vs. group knowledge, implicit and published knowledge.