## Connect all points to form a single tree

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

paramesis
Posts: 7
Joined: Mon Jun 20, 2016 9:26 pm UTC

### Connect all points to form a single tree

This is an adaptation of a puzzle style called "Branch", invented by Inaba Naoki, to a Deltoidal Trihexagonal tiling.

Rules

Draw segments to create a network such that:
1. Every vertex • and node O is connected.
2. Vertices must connect to exactly two path segments. Every branch of the network must form a path from one node to another.
3. Numbers indicate the sum of the lengths of every branch directly connected to that node, in segments.
4. The network is acyclic – there are no loops.

Example

Puzzle

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

### Re: Connect all points to form a single tree

Solution:

Spoiler:
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

paramesis
Posts: 7
Joined: Mon Jun 20, 2016 9:26 pm UTC

### Re: Connect all points to form a single tree

Spoiler:
One segment is missing that would connect the two non-numbered nodes in the lower left. Other than that, the solution is correct!

Here's a harder one.

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

### Re: Connect all points to form a single tree

That was pretty difficult. Here's my solution:

Spoiler:
From the 4:

Code: Select all

`4 _ _ 8 5 6 6 5 10 7 _ 6 7 8 6 6 8 5                |`

I really enjoyed this one. It took me two nights because I got stuck with all of the 5s and 6s on the left. I had figured out that they connect along the entire left edge of the figure, but it took me a while to break where each 5 went after that. I really had to focus on how to get the top two blank nodes to connect in a way that all of the puzzle would be connected.

A hint to get started:

Spoiler:
Start at the 4.

paramesis
Posts: 7
Joined: Mon Jun 20, 2016 9:26 pm UTC

### Re: Connect all points to form a single tree

I'm really glad you enjoyed it, and I like your solution annotation.

Spoiler:
The stream of loop avoidance scenarios to determine where the 5's go felt like it was an entirely different hemisphere of the puzzle that took me quite a few bus rides to figure out.

I have one more puzzle in this set. It shouldn't be quite as hard as the last one, but it plays with patterns a little bit more.

Now that I can post links, here are all three puzzles laid out in a printable pdf. deltoidal-trihexagonal-tree.pdf

Here's a shortcut that may help with larger puzzles:

Spoiler:
If any path between two nodes has an even/odd number of segments, then all possible paths between those two nodes have an even/odd number of segments.

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

### Re: Connect all points to form a single tree

This one was a good increase in difficulty.

I changed the solution notation a bit to make multiple branches easier to read:
Spoiler:

Code: Select all

`    7-11-O-8-13-8-4-O-3        6  O-6                      |        |  |2-4-9-8-5-5-6-O-O-8-8-7-O-2-15-16-8-7-O-3        |                   |        O-O-14-O            O-10-12-1                                 |                                 O    `

I enjoyed the high density of blank nodes and 1-and-2-length paths in this puzzle. I was forced to think in new ways compared to the other two.

CharlieP
Posts: 397
Joined: Mon Dec 17, 2012 10:22 am UTC
Location: Nottingham, UK

### Re: Connect all points to form a single tree

Cauchy wrote:Solution:

Spoiler:
deltoidal-trihexagonal-tree-medium-01 solution.png

How does that solution satisfy rule 1, which says that every node must be connected?
This is my signature. There are many like it, but this one is mine.

CharlieP
Posts: 397
Joined: Mon Dec 17, 2012 10:22 am UTC
Location: Nottingham, UK

### Re: Connect all points to form a single tree

Also, in the first puzzle posted for us to try, is the path between the two vertices at the bottom one "segment" or two?
This is my signature. There are many like it, but this one is mine.

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

### Re: Connect all points to form a single tree

1:

Spoiler:
The two blank nodes are meant to be connected, as you can see from the dotted line. I'm sure Cauchy only represented it that way out of uncertainty. The disconnected node can only connect to its neighbor.

2: The vertex is just missing. It's two segments.

CharlieP
Posts: 397
Joined: Mon Dec 17, 2012 10:22 am UTC
Location: Nottingham, UK

### Re: Connect all points to form a single tree

Ah, I didn't see the dashed line at all - currently awaiting eye surgery. I was counting the bottom edge as one segment, which is why my "solution" didn't match at all - if I'd drawn it with two lines rather than one I'd have counted differently.
This is my signature. There are many like it, but this one is mine.

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

### Re: Connect all points to form a single tree

CharlieP wrote:Ah, I didn't see the dashed line at all - currently awaiting eye surgery. I was counting the bottom edge as one segment, which is why my "solution" didn't match at all - if I'd drawn it with two lines rather than one I'd have counted differently.

If you were counting the bottom edge as one segment, then you shouldn't have been able to find a solution at all.

Spoiler:
First, the two nodes at the bottom have to be connected to each other. Then they both must connect to the 8 and the 6. This is due to rule 2. Without a vertex in the center, this makes a path of length three leading to the 6, so another path of length three needs to connect to the 6 as well (or a combination of paths that sum to length three), because of rule 3.

It can't connect to either of the two nodes on the right, because that length is only two. The only two nodes of distance three are the 6 in the center of the puzzle and the O next to the 8 in the bottom left. To get to either of those nodes, the segment path from the 6 has to pass through the center vertex of the bottom hexagon.

Now the 8 on the left still needs segments that sum to length five to connect to it. The only paths available are to the O node next to it (distance one) and the vertex at the center of the hexagon. You can see that no matter what, it must connect to the vertex in the center - but that vertex must also connect to the 6 on the right, which is already connected to the 8 along the bottom. This creates a loop, which violates rule 4.

If you were able to get any solution past that, then I wonder if you misunderstood one or more of the rules.

CharlieP
Posts: 397
Joined: Mon Dec 17, 2012 10:22 am UTC
Location: Nottingham, UK

### Re: Connect all points to form a single tree

Xias wrote:
CharlieP wrote:Ah, I didn't see the dashed line at all - currently awaiting eye surgery. I was counting the bottom edge as one segment, which is why my "solution" didn't match at all - if I'd drawn it with two lines rather than one I'd have counted differently.

If you were counting the bottom edge as one segment, then you shouldn't have been able to find a solution at all.

Spoiler:
First, the two nodes at the bottom have to be connected to each other. Then they both must connect to the 8 and the 6. This is due to rule 2. Without a vertex in the center, this makes a path of length three leading to the 6, so another path of length three needs to connect to the 6 as well (or a combination of paths that sum to length three), because of rule 3.

It can't connect to either of the two nodes on the right, because that length is only two. The only two nodes of distance three are the 6 in the center of the puzzle and the O next to the 8 in the bottom left. To get to either of those nodes, the segment path from the 6 has to pass through the center vertex of the bottom hexagon.

Now the 8 on the left still needs segments that sum to length five to connect to it. The only paths available are to the O node next to it (distance one) and the vertex at the center of the hexagon. You can see that no matter what, it must connect to the vertex in the center - but that vertex must also connect to the 6 on the right, which is already connected to the 8 along the bottom. This creates a loop, which violates rule 4.

If you were able to get any solution past that, then I wonder if you misunderstood one or more of the rules.

No, the scare quotes around "solution" were deliberate - I was able to continue with a mistake in place for a surprisingly long time, until I realised, with most of the lines drawn in, that it wasn't going to work. I then tried working backwards to find where I'd gone wrong, getting more and more confused, before giving up and looking at the solution to see if I was even close. I should have probably just started again.
This is my signature. There are many like it, but this one is mine.

paramesis
Posts: 7
Joined: Mon Jun 20, 2016 9:26 pm UTC

### Re: Connect all points to form a single tree

I wrote two more of this type of puzzle. They can be found in Kaleidoscope, a competition Logic Masters India is hosting this weekend:

http://logicmastersindia.com/2016/09P/

if I'd drawn it with two lines rather than one I'd have counted differently.

That could be an idea for a variant, with multiple overlapping paths as you would find in Hashiwokakero. Hope your surgery will go/has gone well.