9
$\begingroup$

I stole this question from another site :)

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?

Really challenging but I have no clue what to do!

$\endgroup$
  • 2
    $\begingroup$ Just wanted to say that $131072 = 2^{17}$ $\endgroup$ – Banach Tarski May 2 '17 at 11:13
  • $\begingroup$ Yes, and also that 17 is a prime number. I guess this also has some importance. $\endgroup$ – Jason May 2 '17 at 11:24
  • $\begingroup$ Is this from project euler? @Jason $\endgroup$ – The Dead Legend May 2 '17 at 12:02
  • 1
    $\begingroup$ @M. Winter: Your last scenario isn't possible. If a single company serviced all bridges to an island then only that company would need to stay open and the rest could go on strike. Remember, there's a bridge between every island, so the bridges from that one island would lead to all remaining islands. $\endgroup$ – Jens May 2 '17 at 20:32
  • 1
    $\begingroup$ @Jens Absolutely right! Thank you. So I would rephrase the question as "What is the minimum number of companies necessary for any possible arrangement of which country services which bridge?", right? $\endgroup$ – M. Winter May 3 '17 at 7:35
4
$\begingroup$

This answer is to build on the answer of Jens to prove that exactly $8$ companies can go on strike, and no more. I will formalize Jens's construction that shows at most $8$ companies can go on strike, and show that it is always possible for at least $8$ companies to go on strike.

Let the companies be $1,2,\dots, 17$. Consider a set $S$ of $\binom{17}{9}$ islands, and label them each with a unique subset of $\{1,2,\dots,17\}$ of size $9$. Note that $\binom{17}{9}<2^{17}$ so we have at least that many islands. Now between any two islands in $S$, the subsets they were assigned share at least one number $x$. Assign company $x$ to the bridge between those islands. For each bridge between an island in $S$ and an island not in $S$, assign a company at random among the companies in the subset assigned to the island in $S$. For each bridge between two islands not in $S$, assign any company at random. Now in this configuration, each island in $S$ can only be reached by bridges of the $9$ companies in the subset assigned to it, and there is such an island corresponding to every set of $9$ companies. So if any $9$ companies are selected to go on strike, the island corresponding to those companies will be disconnected. This shows that there is a configuration that allows at most $8$ companies to go on strike.

Now suppose, for contradiction, that there is some configuration that only allows $7$ companies to go on strike, and no more. Then if some set $X$ of $8$ companies go on strike, an island (or group of islands) will be disconnected from the others. Consider what happens if the other $17-8=9$ companies go on strike (call this set of companies $Y$). I claim that the bridges of the companies in $X$ connect all the islands, which is a contradiction to the assumption that only $7$ companies can go on strike. Consider two islands $A$ and $B$. If the bridge between the two islands is operated by a company in $X$, then $A$ and $B$ are connected by that bridge. So assume that the bridge between $A$ and $B$ is not operated by one of the companies in $X$. Now when the $X$ companies go on strike, the bridge between $A$ and $B$ is still operating (it's run by one of the companies in $Y$), but the islands are disconnected, so there must be a third island $C$ that cannot be reached by $A$ and $B$ via bridges run by companies in $Y$. In particular, the bridges between $A$ and $C$ and between $B$ and $C$ are run by companies in $X$, and there is path between $A$ and $B$ via bridges run by companies in $X$. Note that this is essentially an argument that for any graph $G$, either $G$ or its complement is connected. And this shows that in any configuration, at least $8$ companies can go on strike.

I would also like to point out that this argument generalizes to the scenario when you have $k$ companies and at least $\binom{k}{\left \lceil \frac{k}{2} \right \rceil}$ islands, then exactly $\left \lfloor \frac{k}{2} \right \rfloor$ companies can go on strike, and no more. It seems that the situation in which there are fewer than $\binom{k}{\left \lceil \frac{k}{2} \right \rceil}$ islands would be more complex, but it would be interesting to know if there are any results in this direction.

$\endgroup$
  • $\begingroup$ It seems to be a great solution and so is also Jens'! Can you explain a bit further the second paragraph ("Consider a set S..." etc)? I don't understand the part with the subsets. $\endgroup$ – Samuel May 7 '17 at 12:22
  • 1
    $\begingroup$ @Samuel Label a group of islands with a unique label consisting of 9 of the numbers among 1 through 17. For example, {2,3,7,8,9,11,13,15,17}. There are $\binom{17}{9}$ (17 choose 9) = 24,310 possible such labels. So label 24,310 islands with all such possible labels. The rest of the paragraph describes how to select which company to operate which bridge in such a way that each of those 24,310 islands are only touched by bridges operated by one of the 9 companies that are part of that island's label. $\endgroup$ – Perry Elliott-Iverson May 7 '17 at 14:27
3
$\begingroup$

This may not be the final answer. But if my approach is solid, it at least sets a lower bound on the number of companies which must remain working in a worst case scenario.

My approach was to try and think of the worst case scenario for island networks with $n=2^c$ islands, where $c$ is the number of companies.

Let's look at $c=3$ and $n=8$. If only one company services all bridges to an island, only that company needs to remain working (see comments). So let's assume this is not the case. So let's assume all islands are each serviced by exactly two companies.

Let's call the companies A, B and C. There are $\binom {3}{2}=3$ possible combinations of companies which service a given island's bridges and the combinations are AB, AC or BC.

enter image description here

In the picture above we see a scenario where all three combinations are represented. Black lines are A bridges, red lines are B bridges and green lines are C bridges. It is clear that no company by itself can service all islands. Company A has no access to the BC island, company B has no access to the AC island and company C has no access to the AB islands. So at least two companies must remain working.

Let us now look at $c=5$ and $n=32$. We know from above that if exactly two companies service each island, at least two companies must remain working. What happens if exactly four companies service each island? In that case, there are the following combinations: ABCD, ABCE, ABDE, ACDE, BCDE. We see that any two companies will always have themself or their partner represented in any of the combinations and hence have access to the island covered by that combination. Hence, only two companies would need to remain working.

What happens if exactly three companies service each island? We then have the following combinations: ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE. We now see that no two companies will have access to every island. If, for example, companies A and B joined up, they wouldn't have access to island CDE. So at least three companies must remain working.

enter image description here

The above figure is a scenario where all combinations are represented. Blue lines are D bridges, magenta lines are E bridges.

In the same way as was done above, we can look at the network with $c=7$ and $n=128$. If all islands are serviced by exactly four companies, the company combinations would be ABCD, $\ldots$, DEFG. No three companies could cover all islands and all combinations have at least one partner who can be connected to any other island.

So, for $c=17$ and $n=131,072$, if all islands were serviced by exactly nine companies, the combinations would be ABCDEFGHI, $\ldots$, IJKLMNOPQ, and the same conclusion from above applies.

Ergo, a lower bound for the number of companies which must remain working, is $9$.

EDIT

Edited to remove the statement "If all islands were serviced by all three companies, that too would mean only one company needs to remain working" which @M. Winter pointed out is not true. Also modified my final statement and added a complete diagram of the situation for $n=32$.

$\endgroup$
  • $\begingroup$ "If all islands were serviced by all three companies, that too would mean only one company needs to remain working". I don't think so, as even if there is a bridge of company $n$ at any isle, this does not mean that the bridges of $n$ alone will make the graph of isles connected. $\endgroup$ – M. Winter May 5 '17 at 9:59
  • $\begingroup$ @M. Winter: Absolutely right! Thank you. So there is the possibility that a solution exists where the number of companies that must remain open is higher than the lower bound I found. But do you agree that my method above is solid for finding the lower bound that I did? $\endgroup$ – Jens May 5 '17 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.