14
$\begingroup$

There was a Puzzle competition last weekend, in which there were a couple of puzzles titled "Elastic bands".

Fill in each circle with a letter so that the two networks are identical; that is, if two letters have a line connecting them in one network, then those two letters have a line connecting them in the other network, and vice versa.

2 puzzles


I couldn't solve either of these correctly. What I do know is that this puzzle requires us to solve two graph isomorphisms.

My approach:

count the degrees of vertices, their neighbours and try to map the node names to vertices. I also tried counting the cycles of neighbours of each node and fit the vertices accordingly.

This failed miserably.


Question: How do you correctly solve these puzzles? Is there an efficient way, in terms of speed, of solving using logic?


Note : The arrows on the right-hand diagrams are for the answer key (write the answer from that node, going clockwise).


source : http://gp.worldpuzzle.org/sites/default/files/Puzzles/2018/2018_PuzzleRound1.pdf

$\endgroup$
  • 4
    $\begingroup$ Well, I also joined this contest last week and managed to solve the first one. There is indeed a unique property for it (the first one): there is only one triangle on it (look at L-F-I). So yeah, I started to get the matches from that property. But I do really want to know what is the best approach for this puzzle as well. $\endgroup$ – athin Feb 21 '18 at 8:30
  • 1
    $\begingroup$ @athin I was trying that, had submitted my answer but when checked the answer, found it incorrect. $\endgroup$ – ABcDexter Feb 21 '18 at 8:33
8
$\begingroup$

I've done a method to complete the first one and second one.

enter image description here enter image description here

Here is how I proceed Puzzle 1

First I noted the three points of the triangle FIL (dark brown), and the three linked points of that triangle CDH (yellow).
From there I identified the K point as being the linked to two of the CDH points (D and H). C is then identified as the last yellow point.
C is link to E and G and the only point linked to this two is J. J third-linked point must be D Finally it is easy to identified the missing points by simple deduction.

Here is for puzzle 2! tricky one

Noticing pattern and putting colors
I have noticed a pattern with a 2L (two neighboors) node linked to two 4L node and these two are linked to a common fourth node 4L.
This pattern happens twice for K(2L) - DF(4L) - L(4L) and I(2L) - JL(4L) - F(4L).
I put colors in the graph: yellow for center 4L, green for right 4L and dark brown for 2L. You will notice that two nodes have a double spot: F and L.
D and J are the one with only a yellow spot. K and I are with the dark brown spot.
Filling the grid
I noticed A was the only one linked to two semi-identified points (FJ), this is how i identified A, F and J. And then all other semi-identified points. The rest is filled with easy deductions.

My idea for a global way of solving

I think this kind of puzzle always have a pattern to be found, could be a triangle like for the first one or something more complex like the second, or something easier like one node linked which is the only linked to others. My strategy is to write down every node on a paper with the names of its linked nodes, I also note the number of linked nodes for his neighboors. when i find a pattern, I go on and add color and, for these puzzle at least, it fills easily after that.

$\endgroup$
  • $\begingroup$ That is indeed the right answer, and possibly the correct approach to the first one. Could you try the second one, please. $\endgroup$ – ABcDexter Feb 21 '18 at 9:50
  • 1
    $\begingroup$ @ABcDexter I updated a possible method for the second one. $\endgroup$ – Untitpoi Feb 21 '18 at 10:23
  • 3
    $\begingroup$ I don't believe there is a tractable global way of solving. The fact that there isn't a tractable global way of solving this particular problem is at the heart of one of the ZeroInformation proofs used in cryptography. $\endgroup$ – Cort Ammon - Reinstate Monica Feb 21 '18 at 18:42
7
+50
$\begingroup$

Untitpoi's answer to the first problem covered most of the detail of what I ended up doing.

In terms of my approach to reach the same solution as Untitpoi's answer, this was a little different - rather than working directly with the graphs as given, I instead started drawing a topologically equivalent graph on paper without the mess of crossing over lines. In particular, I started by drawing

the nodes that are connected in triangles on both graphs. For the first one there is only a single triangle, and for the second there is a single triangle, and a chain of 3 triangles each sharing a common vertex.

I then connected further nodes onto that separate graph, looking for unique patterns. In particular, on the first chart, it was easy to notice, as Untitpoi did, that

only node K is connected to two different nodes (D and H) which are themselves connected to the FLI triangle. This breaks the symmetry of the triangle, uniquely identifying node C too.

The rest follows quite simply by labelling the target graph with the possible letters for each node that remains ambiguous.

For the second puzzle, note that

AJF form a triangle, and there are another chain of triangles: BCH-HGN-NED The second chain uniquely identifies node G without even drawing anything else.

Having identified the first node for certain,

the connected nodes must be H and N, and the nodes connected to those can be differentiated because C and E are not connected to anything else, whereas B and D are both connected to two other nodes.

We can then observe that

B is connected to J and M, which includes one of the nodes of the isolated triangle, whereas D is connected to K and L neither of which is part of a triangle. This uniquely identifies all of J, M, B, C, D, E, H, N and reduces the possibilities for the others with no other observations.

By this point, my graph on the separate piece of paper looked something like this:

A M\_ G _/K / \ B\_ / \ _/D_ J---F _/| _H---N_ | \L \____/ C/ \E
note that extending the (seemingly symmetric) links from B and D broke the symmetry, as one of them connected to triangle AJF.

I expect finishing off from there will be simple... and indeed it was, resulting in the following labelling (starting clockwise from the node labelled with an arrow):

C, M, I, K, H, F, D, J, N, L, B, E, G, A

In order to slightly generalise the technique which worked for both of these:

  1. Look for triangles on the source graph.
  2. Draw a new graph where these triangles are connected in a more obvious way, but without the other nodes for now.
  3. Extend this graph using the nodes connected to the nodes that form part of the triangle, until the symmetry is broken, so that at least some nodes can be uniquely identified (or at least narrowed down to two possibilities).
  4. Draw circles representing the solution on a new piece of paper, and initally draw just the lines that represent the triangles.
  5. Add lines to the copy of the solution graph this equivalent to the partial graph from step 3.
  6. Label the nodes that were identified in step 3.
  7. Continue to extend both charts as new nodes are identified.
  8. When you run out of lines to add, and/or nodes to label, you're done!

For a more general case (where we may have a graph consisting entirely of triangles, or with no triangles) step 1 etc. will need to be rephrased to look for some other identifiable characteristic that can be easily recognised.

$\endgroup$
  • 1
    $\begingroup$ Interestingly, it seems there is many ways to solve this, i went for a different approach for the second one. you should add an image to illustrate your answer. $\endgroup$ – Untitpoi Feb 21 '18 at 10:18
  • $\begingroup$ Let me try with both the techniques. If both are equally good, I shall accept one and award bounty to other :) $\endgroup$ – ABcDexter Feb 21 '18 at 10:37

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.