# Tag Archives: puzzles

## Numberphile video on the Josephus Problem

Recently, the following Numberphile video on the Josephus Problem has been making the rounds on math-related social media. I watched the video, and I thought Daniel Erman did a remarkably good job at explaining how to solve a mathematical problem. Daniel’s approach is similar to the techniques described in Polya‘s “How to Solve It.” Yet the particular story that Daniel tells also has an appealing narrative arc.

Daniel’s video adheres to the following principles, which I think are fairly universal in mathematical problem solving.

1. Start with a concrete problem. If the problem has a nice story to go along with it, all the better. The Josephus Problem is a great example of a concrete mathematical question. Given a method by which the soldiers kill one another and the number of soldiers, where should Josephus stand to be the last living soldier?
2. Formalize and generalize the problem. What is special about the number 41? The mechanism by which the soldiers kill one another works just as well for any number of soldiers, so consider the problem for $$n$$ soldiers.
3. Consider simpler versions of the general problem. Now that we have the general $$n$$-soldier Josephus problem, we can easily work out a few examples when $$n$$ is small. To quote Polya, “If you can’t solve a problem, then there is an easier problem you can’t solve: find it.” This process of finding simpler and simpler related problems until you find one you can solve is to me the most important general problem solving method.
4. Solve enough of the “simple” problems until you see a pattern. Solving the simpler problems gives one both data and intuition that will allow you to conjecture about a general solution.
5. Generalize the pattern as much as you can so that it fits the examples you’ve solved. Even if the pattern doesn’t give a complete answer (for example, Daniel’s observation that if $$n$$ is a power of $$2$$, soldier $$1$$ is the last living soldier), even a partial solution is likely valuable to understanding a complete solution.
6. Prove your generalization of the pattern to obtain a solution to the general problem. Often, this doesn’t happen all at once. The Numberphile video happens to give a particularly elegant solution in a very short period of time. Don’t get discouraged when not everything falls into place the first time you try to solve the problem!
7. Apply your general solution to the original concrete problem.

In my own research, I follow the strategies above. In particular, Polya’s advice regarding finding and solving simpler problems (steps 3 and 4) is maybe the most valuable single piece of problem solving advice I know of. I think math could be characterized as the art of generalizing simple observations. Often, the simple observations arise by wasting a lot of paper trying to solve simple problems.

The narrative outlined in the steps above is also valuable from a pedagogic standpoint. By starting with a tangible (if slightly morbid) problem, the student/participant immediately has some intuition about the problem before beginning formal analysis. In my experience, one of the biggest challenges students face is connecting abstract statement and theorems to concrete problems. By introducing the concrete problem first and using this problem to motivate the formal development needed to solve the problem, students can begin using their imagination earlier in the problem solving process. This makes learning more interactive, memorable, and effective.

## The Aura of Interactive Proofs

In his essay The Work of Art in the Age of Mechanical Reproduction, Walter Benjamin introduces the idea that original artwork has an aura — some ineffable something that the work’s creator imbues into the work, but which is lost in reproductions made by mechanical means. There is something unique about an original work. Let us imagine that Walter is able to read the aura of work of art, or sense its absence. Thus, he has the seemingly magical ability to tell original art from mechanical forgery.

Andy Warhol is skeptical of Walter’s claims. Andy doesn’t believe in the aura. And even if the aura does exist, he sincerely doubts that Walter is able to detect its presence. In an attempt to unmask Walter for the fraud he undoubtedly he is, Andy hatches a cunning plan to catch Walter in a lie. By hand, he paints an original painting, then using the most advanced technology available, makes a perfect replica of the original. Although the replica looks exactly like the original to the layman (and even Andy himself), according to Walter, there is something missing in the replica.

Andy’s original plan was to present Walter with the two seemingly identical paintings and simply ask which is the original. He soon realized, however, that this approach would be entirely unsatisfactory for his peace of mind. If Walter picked the true original, Andy still couldn’t be entirely convinced of Walter’s powers: maybe Walter just guessed and happened to guess correctly! How can Andy change his strategy in order to (1) be more likely to catch Walter in his lie (if in fact is he lying) and (2) be more convinced to Walter’s supernatural abilities if indeed he is telling the truth?

This is one of my all-time favorite paradoxes:

On Friday, a teacher announces to his class that there will be a pop quiz one day during the following week. In order to uphold the integrity of the quiz, it must satisfy the following two conditions:

1. The quiz will be handed out at the beginning of class one day the following week (Monday through Friday).
2. The students will not be able to (logically) deduce which day the quiz will be held before they are actually given the quiz.

After making this announcement, he notices a lot of murmuring around the class, and after a minute a few students start sniggering. He asks the students what they find so amusing. One of the cleverer students in the class raises her hand and explains:

“You cannot possibly give us a pop quiz next week,” she says.