Put on your problem solving Hat IV

[dtweah]

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

[avenus]

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

Code: Select all

                               N0
                                         
             N01               N02               N03  

.         N011 N012         N021 N022         N030 N031  

[PAB2706]

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!!

[avenus]

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.