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?) Copied from http://cartalk.cars.com/Radio/Puzzler/Transcripts/200322/index.html --------- "It was a dark, moonless night in France, 1943, deep within German-held territory. Out of the inky shadows comes Claudette, the beautiful French resistance fighter, followed by three downed Allied crew members, who she must get back into friendly hands. They must cross a bridge, and they know the Germans are not far behind. It's an old, treacherous bridge, and they have only one flashlight among them to see. The bridge can support only two of them at a time. Three on the bridge, and it's curtains. "Pairs crossing can do so only as quickly as the slower member of the pair, because they need the flashlight to see. Each time a pair crosses, someone has to return with the flashlight, until they're all safely across. "Unfortunately, the three downed airmen are injured. Here are the times each person takes to cross the bridge: Claudette can do it in a minute. Major Johnson has a twisted ankle, and takes 2 minutes. Captain Kangaroo got shot up pretty bad. He has to hop on one foot, and it takes him 5 minutes. Colonel Mustard is in worse shape. It takes him 10 minutes to cross the bridge. "Claudette has rigged the bridge with explosives so that their pursuers can't follow. She's about to set the timer." Here's the puzzler: What's the shortest time she can set and get everyone safely across the bridge before it blows up? --------- Pause reading now if you want to think about it yourself, answer and musings follow. The natural thing to want to do is have Claudette ferry each person across and dash back with the flashlight; this takes 2+1+5+1+10+1 = 19 minutes. The first interesting part is that you can do better. Of course the trick is to have the 5 and 10 minute guys cross the bridge together, and you can accomplish this by sending 1,2 over together, 1 coming back, then sending 5,10 over at once, then 2 coming back with the light, and 1,2 going over together again. This takes 2+1+10+2+2 = 17 minutes instead. So if the four people take time 0 <= a1<= a2 <= a3 <= a4 to cross the bridge, then the first strategy takes time 2 a1 + a2 + a3 + a4, while the second takes time a1 + 3 a2 + a4; you have the option of trading in a1+a3 for 2 a2, which is a good idea here, with 1+5>2+2. So the questions that leap to my mind are: 1) If you have 2n people, how many different undominated strategies are there, and what structure does this set have? One strategy dominates another, of course, if the first is better for all values of the a's with 0 <= a1 <= ... <= a_2n. Then you need to say what "different" means -- probably two strategies are "the same" if their respective unordered multisets of bridge crossers coincide, though some subtlety lurks in that -- the strategies above have 3! and 2! implementations respectively, and they are pretty obvious, but there might be more different-looking strategies that I've defined as "the same", perhaps foolishly. Or even more coursely, we could just identify strategies that take the same total time. 2) What does the complex of regions where each strategy dominates look like? Or how about set of separating hyperplanes? For 4 people it was a1 - 2 a2 + a3, quite suggestive. --Michael Kleber kleber@brandeis.edu