I am deeply suspicious of reasoning-about-reasoning puzzles. There is a classic example with solution at the bottom of the post. Of course, maths puzzles which deal with real-world objects require common-sense abstractions and simplifications. For example, in a coin-tossing problem with N coins, the reader need not worry about the fact that if N is large enough, no one could find N coins etc. The problem with reasoning-about-reasoning problems is that it's unclear how to formalise the reasoning process so that the intended solution works. In practice, as in the example below, the rules of logical deduction are never made explicit. In the problem below, the professors stare at each other and then make deductions about the fact that neither has yet made a deduction. However, it's a reasonable abstraction of the logical deduction process to assume that any logical reasoning process can be completed instantaneously. Since they've stared at each other, neither party has made an instantaneous deduction. The inability of the parties to make an instantaneous deduction is supposed to lead to the problem's intended solution. But that's faulty reasoning. Since the parties are clearly unable to make an instantaneous deduction (as explicitly stated in the intended solution), and since the audience is supposed to make deductions from this failure, it is a completely meaningless problem unless the puzzlist can state how long such reasoning processes are expected to take. Otherwise A can look at B's failure to deduce and conclude (for example) that B must be asleep (and therefore a somnambulist). That would not make less sense than the actual problem does.
QUOTED PROBLEM WITH SOLUTION University B. once boasted 17 tenured professors of mathematics. Tradition prescribed that at their weekly luncheon meeting, faithfully attended by all 17, any members who had discovered an error in their published work should make an announcement of this fact, and promptly resign. Such an announcement had never actually been made, because no professor was aware of any errors in her or his work. This is not to say that no errors existed, however. In fact, over the years, in the work of every member of the department at least one error had been found, by some other member of the department. This error had been mentioned to all other members of the department, but the actual author of the error had been kept ignorant of the fact, to forestall any resignations.
One fateful year, the department was augmented by a visitor from another university, one Prof. X, who had come with hopes of being offered a permanent position at the end of the academic year. Naturally, he was apprised, by various members of the department, of the published errors which had been discovered. When the hoped-for appointment failed to materialize, Prof. X obtained his revenge at the last luncheon of the year. ?I have enjoyed my visit here very much,? he said, ?but I feel that there is one thing that I have to tell you. At least one of you has published an incorrect result, which has been discovered by others in the department.? What happened the next year?
Like the previous puzzle, we can use induction to break this problem up into more manageable chunks. We can start to get a feel for how induction might apply by examining some simpler versions of the same question; specifically, we can change the total number of professors from 17 to any other number n and see what happens.
The case n = 1 is a silly one, since in this situation there would be no one to apprise Prof. X of the single tenured professor?s mistake to begin with. So let?s move on.
Consider the case n = 2. Here we have two tenured professors, each with a published error that they don?t themselves know about, but each knows about the error that the other has published. When Prof. X leaves in a huff, he informs the two that at least one of them knows of an error published by the other one. Then what? At the next luncheon meeting, the two professors stare at one another. Both can reason along the following lines:
?If my colleague over there didn?t know of any errors I have published, then she would know that Prof. X was referring to me when he said that one of us did know of an error. That would lead her to deduce that she has, in fact, published an error. But she hasn?t deduced that! She?s just staring at me. That means that she must know of an error that I?ve published. Which means that I?ve published an error, so I have to resign.?
Since both professors can reason in this way, both can deduce that they have published an error, and so both will end up resigning.
Now consider the case n = 3. Prof. X obtains his revenge by informing them that at least one of them has published an error that others are aware of. Each of the three can now reason as follows:
?If my colleagues didn?t know of any errors I had published, then they would know that Prof. X was referring to an error published by one of them. But in that case they could reason along exactly the same lines as outlined above, for the case n = 2, between the two of them. This would cause both of them to resign. But they?re not resigning, we?re all just staring at each other! That means that they must know of an error that I?ve published, so I have to resign.?
Once again, since each of the three can reason like this, all three will end up resigning.