Dan Hoey wrote:
There are a lot of crossing problems, but this one is quite familiar. It has been kicking around rec.puzzles since 1996[...]
Over lunch, I mentioned it to Dimitry Kleinbock, who said he saw it in a Quantum Magazine even before that (and culled it for a Math Circle type thing he was doing in NJ, and he might be able to dig up a citation). But any reference for >4 crossers?
1) If you have 2n people, how many different undominated strategies are there, and what structure does this set have?
I don't see why you want the number of people to be even.
Yup, don't know what I was thinking.
For N people, the minimum number of crossings is 2N-3, but that may not be optimal in all cases. I know that for N=6 we can force 11 crossings, but I don't know if there's an optimal 9-crossing solution for N=5.
Really! Can you show us the N=6 instance? I asked the computer to look at N=5 and N=6 the naive way, where you always have two people cross over and only one come back. In both cases the (small) set of undominated strategies were the roughly obvious generalizations of what happens in N=4. Up to permuting the order of crossings, you get N=4: 12, 1, 13, 1, 14 or 12, 1, 34, 2, 12 N=5: 12, 1, 13, 1, 14, 1, 15 or 12, 1, 13, 1, 45, 2, 12 N=6: 12, 1, 13, 1, 14, 1, 15, 1, 16 or 12, 1, 13, 1, 14, 1, 56, 2, 12 or 12, 1, 34, 2, 12, 1, 56, 2, 12 Which of the three N=6 strategies is preferable depends on how 2 a2 compares to a1+a3 and a1+a5. But having thought about it for as long as it took to write this email, I'm still in the dark about when it's beneficial to send two people back together. --Michael Kleber kleber@brandeis.edu