Archipelago of Wonderland

[harry.petrone]

The archipelago of Wonderland consists of 131072 islands. For any two islands, there is a bridge that connects them. There are 17 managing companies that service at least one of these bridges each. The servicing personnel have decided to go on strike and therefore bring out of service some of the bridges but in such a way that with the remaining bridges, all islands can be accessed from any other island, either directly or through some other island. It has therefore been agreed that only some of the 17 companies will allow their personnel to go on strike. What is the maximum number of companies that can safely allow their personnel to go on strike, given the above condition?

[Guest]

Harry,
All I can tell you is that
[tex]131072 = 2^{17}[/tex]
if this is of any help.
And of course that the number of bridges is [tex]2^{16}*(2^{17}-1)[/tex].

[Guest]

I trust R. Baber will post a great solution in no time

[Guest]

I posted a solution on stack exchange here:

https://math.stackexchange.com/question ... 65#2267265

To the original poster: do you know the origin of this problem? I've made some attempts to search the literature, and came up empty. Thanks.