Problem Solving

A group of N islands are connected by bridges. Each island has bridges to at most 3 other islands.
One can travel between any 2 islands by crossing at most two bridges. What is the largest possible
value of N? (Bridges are allowed to go over or under other bridges.)

a. 7
b. 8
c. 9
d. 10
e. 11

starting off from a certain island, the maximum number of islands that can be reached while meeting the specified requirements is 9, so the number of islands canot be greater than 10.

Answer is D

On the **??* below, add bridges in the following way: for each level, drop the last digit in the name of the island and join that island with the one matching the resulting name on the level immediately above.
Ex.:
N011 --> drop 1 to get N01 --> join N011 with N01

i am getting max value to be 7....


@ avenus

a lil difficulty comprehending your post...

can you explain how will u go from N03 to N011 by crossing at most two bridges and maintaining that each island is connected to at most three islands?

thanks

cheers!!

PAB2706 wrote:i am getting max value to be 7....


@ avenus

a lil difficulty comprehending your post...

can you explain how will u go from N03 to N011 by crossing at most two bridges and maintaining that each island is connected to at most three islands?

thanks
cheers!!

That's only supposed to show that the maximum number of islands cannot be greater than 10. It's not the solution. didn't feel like drawing.
My point was that you can find an upper bound for n (number of islands) relatively quickly but that doesn't necessarily mean the upper bound can be reached. not trivially at least. I was hoping to trigger some ideas on how you go from showing that n < 10 to showing that n = 10 in a quick, systematic way. Anyone??

In the figure below, if you consider only the islands and the thick, dark lines, you'll have what I meant in the previous post. Add the dashed lines for the final solution.