Tag Archives: puzzles

computer science edutainment math teaching

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.

computer science expository math musings

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?

read more »

math musings

The Pop Quiz Paradox

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.

“Why not?” the teacher asks.

“Well, if we won’t be able to deduce which day the quiz is before we are given the quiz, it can’t be on Friday. For if after class on Thursday we still haven’t gotten the quiz, we will know that the quiz must be the following day. This contradicts the second requirement for a pop quiz.”

“That makes sense,” he agrees.

“So the quiz can only be given one of the days from Monday through Thursday. By the same argument as before, the quiz can’t be on Thursday: Since we’ve shown it can’t be held on Friday, we will know by Wednesday if the exam is to be held on Thursday. By the same token, the quiz can’t be held on Wednesday or Tuesday. The only possible day you could give the quiz is Monday. But I know now that the pop quiz must be on Monday, which again contradicts the second condition for pop quizzes. So you can’t give us a pop quiz next week!”

The teacher tells the class that he doesn’t see any flaw in the student’s argument, so it appears that he can’t satisfy the requirements for a pop quiz. The students seem pleased to have a weekend free of study having deduced that a pop quiz is an impossibility. Imagine the students’ surprise when the teacher hands out the pop quiz on Tuesday at the beginning of class, thus fulfilling the previous week’s proclamation!

Commentary

I first encountered this paradox in a collection of Martin Gardner‘s writings entitled The Colossal Book of Mathematics, where it is referred to as “The unexpected hanging.” A more detailed account of this paradox can be found in this article by Timothy Chow. The subtlety of the paradox is suggested by the sheer number of references cited in Chow’s essay.