Find the total number of distinct ways to join the six islands below by bridges such that
Details and Assumptions:
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
@Thanos Petropoulos , we really liked your comment, and have converted it into a solution.
Log in to reply
@Brilliant Mathematics , you accidentally posted my solution under Thanos's name.
True, this is Matt's solution. I haven't posted my solution yet. Nice solution Matt!
First
Second
Third
Fourth
Fifth
Sixth
Seventh
Eighth
Ninth
Tenth
Eleventh
Twelfth
How do you know that you have enumerated every single possibility?
After seeing your solution, the problem needs to be clarified
1. Islands on the left cannot be joined directly to islands on the right
2. We are allowed to build more than 1 bridge between 2 islands
Log in to reply
the second term (the one about "more than one bridge between two islands") is absolutely NECESSARY in the initial text!
Is there any mathematical way for this
Challenge Master: I don't know. I assume Graph Theory is needed, but it's not my strong suit so I couldn't pinpoint what I should do next.
The problem description says "You cannot connect islands that are diagonally opposite". So, nine of your "solutions" are invalid by my interpretation of that constraint. Furthermore, I have an additional eight that you did not list (and these are not equivalent by rotation/reflection).
Here are my 12 configurations, without any diagonals: 1 2 1 2 1 2 − = − = − = 2 3 3 3 3 ∣ 3 − − = − − 3 ∥ 3 3 ∣ 2 3 ∥ 2 1 ∣ 2 1 ∣ 2 1 ∣ 2 1 ∣ 2 − − − 2 ∣ 3 3 ∣ 3 2 3 3 ∥ 3 − − = − = = = 3 ∥ 3 3 ∣ 2 3 ∣ 3 3 ∥ 2 1 ∣ 3 1 ∣ 3 = = 2 ∣ 3 2 3 − = − 3 ∥ 2 3 ∣ 2 2 ∣ 3 3 ∥ 3 2 ∥ 3 − = − − − 1 3 1 2 1 ∣ 3 − − − 2 ∥ 3 2 ∥ 3 2 ∥ 3
Log in to reply
Oh I'm so sorry. I forgot how I formulated this question. If you don't mind, can you rephrase the question for me? Because I don't know how to fix it (even after reading your follow up comment in the report section).
And for some reason, I didn't get any notification from your message.
Log in to reply
@Pi Han Goh I think that the formulation where diagonal bridges are forbidden is fine. And I think that my diagram shows the 12 possible configurations (modulo rotation and reflection). So under Details and Assumptions add as second bullet point: "Diagonal bridges are not allowed."
Log in to reply
@Tom Verhoeff – Thanks for your input. I have made the necessary editsss
Log in to reply
@Pi Han Goh – But you did not correct the answer :( It must be 12, not 13.
Log in to reply
@Babis Athineos – Thanks. I've updated the answer to 12. Those who previously answered 12 has been marked correct.
Babis, in the future, if you have concerns about a problem's wording/clarity/etc., you can report the problem. See how here .
But you said diagonal bridges are not permitted!
Log in to reply
Sorry, I've fixed the last line.
Log in to reply
But in that case, the thirteenth graph is also invalid :(
Log in to reply
@Fabricio Kolberg – I'm so sorry. I'll the admins take care of it. @Brilliant Mathematics , please change the answer to 12.
Log in to reply
@Pi Han Goh – Thanks. I've updated the answer to 12. Those who previously answered 12 has been marked correct.
Fabricio, in the future, if you have concerns about a problem's wording/clarity/etc., you can report the problem. See how here .
Okay, I'm very confused - so long as diagonals are allowed (which the current phrasing says nothing about), there are WAY more than 12 distinct solutions. I found 53 distinct solutions personally, and I'm quite sure that they can't be simplified down to 12. I would list them, but that sounds exhausting.
Log in to reply
Since you have 53 distinct solutions, can you list 1 or 2 of them that are different from what has been shown above?
I might be easier to check against the solutions listed by Tom below.
Can it be solved this way? You put inside the circle (island) the number of bridges the island has. When you take two or more random solutions you can see that the sum of all numbers is always 14. Given digits 1,2,3 in two rows the only way to get 14 is sum of 7 in one row and 7 in the other one (7+7) or 8+6 or 9+5. Then you write down all of possibilities to get a sum of 7, 8, 6, 9 and 5 out of digits 1,2,3. Then you have to cross out all of the possibilities that would make a mirror image or 180-degree rotation. For example you can get a sum of 7 by adding 1,3,3 or 3,3,1 but we can see that 1,3,3 is a mirror image of 3,3,1 so for the porpoise of this task it is the same. When you cross out all of the unnecesery possibilities you are left with 4 ways to connect the islands using the sum 7+7, 2 ways using 9+5 and 6 ways using 8+6, so all together 12 ☺ Please let me know if this is correct
3,3,3 on the top and 1,2,2, with a double bridge between the right and centre 3s (and the rest filled in accordingly) is a valid configuration which isn't on the list - please update this question with some kind of analytic answer
Problem Loading...
Note Loading...
Set Loading...
I agree with Thanos Petropoulos that the answer should be 71. I found this answer using a Python script. What follows is a list of the 71 bridge networks I found, a description of how I wrote the script to find them, and the script itself.
Label the islands A, B, C, D, E, and F clockwise from the top left. Number the eleven possible bridges according to the following list.
The 71 different bridge networks are listed below.
The script I used treats each bridge network as a graph with six vertices A through F and with seven of the bridges as edges. To preserve connectivity, an edge cannot appear three or more times. Therefore, the script considers edge sets with seven edges chosen from the multiset { 1, 1, 2, 2, . . . , 11, 11 }.
Calculating degrees. Given an edge set, the degree of a vertex in the corresponding graph can be found by counting the number of times an incident edge appears in the edge set. The incidences are given in the following table.
Identifying edge crossings. The only pairs of edges that cross are 2, 4 and 8, 10. As long as an edge set does not include one of these pairs, it has no edge crossings.
Testing connectivity. Any graph with the correct degree numbers will necessarily have no isolated vertices. Consider the graph with all eleven possible edges. There are nine sets of two or three connected vertices that could be cut off from the rest of the graph. As long as a graph with the correct degree numbers contains at least one edge from each of the cuts in the table below, the resulting graph will be connected.
Avoiding rotations and reflections. Any valid graph can be rotated and reflected so that deg A = 1 or deg B = 1. By only considering graphs with deg A = 1 or deg B = 1, we will avoid double-counting all rotations and most reflections. If deg B = 1, it is still possible for two valid graphs to be horizontal reflections of one another. However, notice the edges are numbered so that i and j are horizontal reflections of one another if and only if i + j = 12. Using this property, we can easily identify those reflections.
The script I used is shown below. It declares a list for storing valid edge sets and defines functions for
The script uses the combinations function from itertools to generate a list of all possible edge sets. In the main loop, each edge set and its reflection are compared to stored valid edge sets to make sure the edge set isn't a repeat. If an edge set is not a repeat, the degrees are computed. If the graph is in the correct orientation (i.e., if deg A = 1 or deg B = 1) and the degrees are 1, 2, 2, 3, 3, 3 and the edge set has no crossings and the corresponding graph is connected, then the edge set is stored as a valid edge set.