Tuesday Thousand Island Puzzle

Re: Tuesday Thousand Island Puzzle

Gary Smyth

I fear I need some clarification. The way the puzzle is stated to build �as many bridges as possible�. If so, in theory, the number could be infinite. On a different tack, if the islands were in a single long line the answer could be one, but that is not �as many bridges as possible�. Another example might be if one island were in the center and the remainder around it, an answer might be 999 if only one bridge per island, but you state �as many bridges as possible� so each island could have more than one bridge and still the bridges themselves would not cross. Am I reading it correctly?

SWAG

Alex Y

I have a guess, but can't figure out how to obfuscate it. But if I am right and if there were 1,416 islands, there could be 4,242 bridges.

Re: Tuesday Thousand Island Puzzle

David Weaver

Purely from working through the first few cases, I would guess 1997 bridges for 1000 islands with the condition that none cross.

That is not an educated answer, though, just a guess after working through 1 through 6 islands and noticing that after three, each new island allows two new bridges without any bridges crossing.

Re: SWAG

Larry Barrett

I get same answer for 1416. For this to work, (and to answer Gary's question), I think islands a and b can be connected by at most one bridge, and one bridge connects only two islands (doesn't span multiple islands).

Re: Tuesday Thousand Island Puzzle

Alex Y

just a guess after working through 1 through 6 islands and noticing that after three, each new island allows two new bridges without any bridges crossing.

With three islands arranged in a triangle, the three possible bridges are the sides of the triangle.

With four islands arranged in a rectangle, there are six possible bridges: four sides, one diagonal, and one long curved bridge going outside the rectangle, connecting the other two diagonally opposite points.

And the shapes posited above are just for ease of visualizing. The bridges don't depend on the positioning of the islands.

Re: Tuesday Thousand Island Puzzle

Bill Earl

Only one bridge between any two islands.

A long string of bridges end-to-end is rules out by the rules as stated. Each bridge must start and end on an island.

Re: Tuesday Thousand Island Puzzle

David Weaver

Dumb thing for me to assume they had to be straight!!

I'm having an "in the box" kind of day (week, month)...

Need some of those straight up combinatorics questions or something instead of these "thinking man's" questions.

Tuesday Answer

Bill Earl

Alex and Larry caught on pretty quickly. This is a classic graph-theory.

A planar graph with n (>2) nodes has at most (n-2)*3 edges