I had a great time when Michael Rabin visited for the past few months. As he was leaving, he said "I did not get to hear a good puzzle", and I am ashamed. It has indeed been a dry season. Anyway, here is a setting. n people go to dine at an Ethiopian restaurant, are seated on a circle, and order distinct entrees numbered 1,...,n in the order in which they are seated. The waiter brings them the food arranged p(1),...,p(n) on a circular plate, as they tend to do in Ethiopian restaurants. Of course p is some permutation of 1,...,n. Now, the plate has to be rotated in the plane to insure people have the entree they ordered directly in front of them. Questions:
- What is the worst permutation p, that is, no matter how it is rotated, it has the least number of entrees directly in front of the person who ordered them?
- Find a fast algorithm to determine the rotation that will maximize the number of people who will find their entrees directly in front of them.