Re: [math-fun] Car talk puzzler
Michael Kleber <kleber@brandeis.edu> writes:
Last week's Car Talk puzzler might have some interesting math. (Tom and Ray said this has been floating around, but I haven't heard it before; am I behind the curve here?)...
There are a lot of crossing problems, but this one is quite familiar. It has been kicking around rec.puzzles since 1996, when it was said to be a Microsoft interview puzzle: http://groups.google.com/groups?selm=01bbc5b7%242146dd80%247b839bce%40redpwq... Somewhere along the line it was dressed up as being the four members of the band "U2" who had to get across to make their concert on time. (Do bands start on time now? It's been a long time since I was at a rock concert.)
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. 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. Dan Hoey@AIC.NRL.Navy.Mil
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
participants (2)
-
Dan Hoey -
Michael Kleber