Another Dinner with the Emperor

Tom Walters

Abstract: An old problem is revisited in a new format, and the solution, when viewed graphically, yields a fractal like pattern.

In her charming and important new book, Writing to Learn Mathematics, Joan Countryman retells an old story about a circle of condemned prisoners awaiting execution. Her plot is set in a much more playful format.

You have been invited to the emperor's banquet. The emperor is a rather strange host. Instead of sitting with his guests at his large round dining table, he walks around the table pouring oats on the head of every other person. He continues this process, pouring oats on the head of every second person who has not had oats until there is only one person left. The question is, where should you sit if you do not want oats poured on your head?

Ms. Countryman uses this problem to motivate a discussion about the importance of writing as part of learning math, and her ideas are certainly timely. We will, however, focus on the "math" in the problem which seems suitable for both general math and beginning algebra students.

The class will most likely be full of questions. How many people will be at the dinner? We can never be sure. Does his majesty always start at the same first seat? Yes, and he always moves in the same direction. Can I just stay home? Not likely, we want to stay in his good graces.

Students should do this investigation by making marks for the guests and crossing them out as they are eliminated. For example, four circles will model the case of four guests. Cross out the first circle, skip number two, and then eliminate seat three. Next skip seat four and loop back to cross out number two. This leaves seat four as the place to be. Possible conjecture, take the last seat. But if we move to the case of five guests the answer is to choose seat two to avoid a cleaning bill. Time for more trials and more conjecture.

Students can certainly be working in small groups while looking for patterns and refining their ideas, and written notes made during the discovery process can contribute to a more complete understanding of just what is going on. Students can get immediate results, and as the information about known cases expands, they will see a rising and abruptly falling pattern which is punctuated by the powers of two. The ideal seat turns out to be at 2[ n - (the greatest power of 2 less than n)], not an easy expression to write the first time; in fact, it is perhaps easier to say. Take the largest power of two which is less than n and subtract it from n. Double that result, and that is the seat of choice.

A Table of Early Solutions

Below is a spreadsheet graph for the solutions of the first 32 cases. Students need not go this far before making some conjectures about the pattern, and a graph of the results at an earlier stage will help them visualize the relationship between the change in seat placement and the change in number of guests.

As a math teacher, I am constantly amazed by the power to experiment and visualize that the new technology has given us. The graphing calculator, because of its relative low cost and portability, is a particularly powerful tool, and using it to picture the solutions to this problem can give students new insight into its structure.

The data can be entered in the x and y statistical registers of the TI-81 calculator or into the lists in the newer TI-82 calculator and, after setting the proper viewing windows, students can examine their results in a graph similar to the one above. At this point we can pose an interesting question, namely, what do we see if we plot the data for cases 33-64 in the same viewing rectangle? The surprising answer is that the new graph looks remarkably like the old one. When we add this new interval, the old points are pushed to the left and down so that they correspond to the previous period.

The graph, viewed [0, 64, 0, 64] without scaling, looks like the graph above, [0, 32, 0, 32], only with more data points shown on the screen. The lines are coincidental. A useful feature of the new TI-82 will let us save one of these graphs as a picture and then overlay it onto subsequent results. The self-similar nature of this series of images gives it a fractal like quality, and if appropriate technology is available, could lead to viewing some real fractal patterns. Advanced students could be asked for a closed form solution: seat = 2[n - 2^{int (ln n/ln 2 + .001)}] will give correct solutions when viewed in a "friendly" TI window. Another extension: What happens if the emperor chooses every third or fourth person?

This is another of those rich problems which provides an opportunity for mathematical discussion, writing, experimentation, conjecture, and visualization; skills all students need to develop.

References: Writing to Learn Mathematics, Joan Countryman, Heinemann Books, 1992

Woodrow Wilson Leadership Program in Mathematics lpt@www.woodrow.org
The Woodrow Wilson National Fellowship Foundation webmaster@woodrow.org
CN 5281, Princeton NJ 08543-5281 Tel:(609)452-7007 Fax:(609)452-0066