Puzzle Undone
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.
Labels: aggregator
posted by metoo at 8:16 AM
9 Comments:
Re the permutation that can be matched least well: if n is odd, doesn't the reverse of the permutation in which they ordered the food have ans=1?
Re an algorithm for maximizing matched entrees: can't you simply in linear time bucket sort the entries of the plate by rotation angle, and pick the biggest bucket?
The reverse permutation is what I had in mind. n=1 it is.
Bucket sorting is what I had in mind, but I had to run and published the blog stopping at the moment when I wanted to point out the connection to substring Hamming computation, ....
Now I have to run again (bicycle beach waiting), hope the next post from you is a new puzzle from this setting. :)
Proving that for even n there's always a rotation that satisfies two people seems to be less trivial (if indeed it is even true; I've verified it only for n=2 and n=4).
I wrote a program to test cyclic permutations on up to nine elements and found that the same pattern of being able to prevent two people from both getting their order for odd n but not being able to prevent it for even n persists. Based on that, here's another related puzzle.
For n = 1, 3, 5, 7, 9 the number of ways of cyclically permuting the orders in such a way that only one person can get the correct order is 1, 1, 3, 19, 225. E.g. for n = 5 there are three possible orderings of this type: the reverse ordering [5, 4, 3, 2, 1] works, but so do the two other orderings [2, 4, 1, 3, 5], [3, 1, 4, 2, 5].
The puzzle is: there are two sequences in OEIS that begin 1, 1, 3, 19, 225. Is the Ethiopian restaurant sequence one of these two or is it a third and different sequence?
Cool puzzle with sequences, and fun question! Enumerate permutations that have a rotation satisfying precisely k people seems like an algorithms problem.
Btw, hope you were thinking about this on a beach. I was doing this.
-- metoo
This comment has been removed by the author.
For the enumeration problem I think A003111 is the sequence we are looking for. Here is why:
(I consider permutations on the set {0, ..., n-1} instead of {1, ..., n}: this makes modular arithmetic easier).
We can always rotate a permutation p so that p(0) = 0. Rotations define an equivalence relation on the set of permutations. Let's say that for each class the permutation p s.t. p(0) = 0 is the canonical representative of the equivalence class. We say an equivalence class is good if no permutation in the class has more than one fixed point.
Now consider the following function:
q(i) = p(i) - i mod (n-1)
There is a unique q for each p. Also rotating p t times corresponds to adding t mod n-1 to each q(i). It follows that p can only satisfy one person no matter how it is rotated iff q is a permutation.
A003111 counts the "Number of complete mappings of the cyclic group Z_{2n+1}". From their definition:
"A complete mapping of a cyclic group (Z_n,+) is a permutation f(x) of Z_n such that f(0)=0 and such that f(x)-x is also a permutation."
In other words, A003111 counts the canonical representatives of good classes.
----
Interesting consequence: the permutation p(i) = 2i mod n also works for the puzzle. For n=5 this gives [0, 2, 4, 1, 3].
aaand finally corrections:
wherever i said mod n-1 i meant mod n.
also q(i) = p^{-1}(i) - i. this measures how far we move i in p. now the claim that rotating p corresponds to adding 1 mod n to each q is true. from there the rest goes through. A003111 counts p^{-1} for good p's.
A proof that for every permutation of 2k elements, there is a rotation which satisfies >= 2 customers. Adapted from Paige.
From my previous comment: p is the permutation. q(i) = p^{-1}(i) - i is the distance we moved i from its original location in p. Each rotation of p satisfies at most one customer iff q is a permutation.
By contradiction. Assume there exists a p s.t. q is a permutation. Let S = (0 + 1 + 2 + ... + 2k - 1) mod 2k. Because q is a permutation,
S = q(0) + ... + q(2k-1) mod 2k.
But
q(0) + ... + q(2k-1) mod 2k= (p^{-1}(0) + ... + p^{-1}(2k-1)) - (0 + ... + 2k-1) mod 2k = 0,
since p^{-1} is also a permutation. Then S = 0. However S = (2k - 1)k mod 2k = -k mod 2k \neq 0. QED
Post a Comment
<< Home