BREAKING: Target Test Prep releases Brand New 2026 On Demand GMAT prep course

Redeem

Put on your problem solving Hat IV

This topic has expert replies
Post new topic Post Reply
Previous Topic Next Topic
Master | Next Rank: 500 Posts
Posts: 487
Joined: Fri Mar 27, 2009 5:49 am
Thanked: 36 times

Put on your problem solving Hat IV

by dtweah » Tue May 12, 2009 6:21 am
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
Top
Source: — Problem Solving |
Master | Next Rank: 500 Posts
Posts: 238
Joined: Tue Feb 10, 2009 8:44 am
Thanked: 9 times

by avenus » Wed May 13, 2009 4:58 pm
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
Top
Master | Next Rank: 500 Posts
Posts: 260
Joined: Sun Oct 12, 2008 8:10 pm
Thanked: 4 times

by PAB2706 » Thu May 14, 2009 9:32 pm
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!!
Top
Master | Next Rank: 500 Posts
Posts: 238
Joined: Tue Feb 10, 2009 8:44 am
Thanked: 9 times

by avenus » Thu May 14, 2009 11:47 pm
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.
Attachments
Islands.jpg
Top
Post new topic Post Reply
• Page 1 of 1