Michael Kleber <kleber@brandeis.edu> writes:

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).

Neat. I didn't think it was likely to be a Microsoft original. I wonder if I saw that Quantum. I remember thinking the puzzle looked familiar when I saw it in rec.puzzles.

But any reference for >4 crossers?

I don't know of any. I wonder if anything useful comes of bridges that hold three people? Or flashlights that require two people to carry? When I wrote:

...

I know that for N=6 we can force 11 crossings....

I was wrong. Somehow I thought the case with 1,2 small and 3,4,5,6 large would require that, but your strategy

12, 1, 34, 2, 12, 1, 56, 2, 12

is clearly the solution. I haven't got a proof, but I suspect 2N-3 crossings is always best.

Which of the three N=6 strategies is preferable depends on how 2 a2 compares to a1+a3 and a1+a5.

I don't know if it would help to consider the first differences of the parameters (since if the number of crossings is constant, they are all that matter). Then the criteria would be d1:d2 and d1:d2+d3+d4. Dan