Make a wide rectangle out of T-Pipes without loops

Question

Inspired by Pipes.

This is a T-Pipe

A T-Pipe connects to 3 adjacent cells.

This is a 2x2 square containing only T-Pipes.

I call the square above is a valid arrangement, because it fulfills the following constraints:

• The arrangement is rectangular
• The rectangle contains only T-Pipes
• The rectangle contains no loops
• All pieces are connected

What is the largest valid arrangement, measuring first by the smaller dimension, then by the larger dimension? (e.g. 1x99 < 2x2 < 2x3 < 3x3... etc.)

Bonus: If there are multiple such arrangements, find all of them and prove that you have found all of them. If there is a single such arrangement, prove that there are no others.

Answer 1

I found a solution for

3×4:

I claim this is optimal.

Proof:

Consider the opposite problem. Instead of placing Ts, we'll place walls to block off the cells.



Note that every dot here has a "path to freedom". If this wasn't true, then you could circle the area around the separated "dots" to form a loop.



So, we must place as many internal blockers as we have dots. In other words, given an $m×n$ grid, we must place at least $(m-1)(n-1)$ internal blockers.

Of course, no square can have two blockers around it, or then it wouldn't be a T anymore. We can only place one internal blocker per two cells in the grid.


If we had a $3×5$ grid, we'd need to place 8 (from $2×4$) internal blockers - but we'd only be able to place 7.5 (from $3×5/2$). So 3×5 is impossible.

If we had a $4×4$ grid, we'd need to place 9 (from $3×3$) internal blockers. But we'd only be able to place 8 (from $4×4/2$). So 4×4 is impossible.


All other larger cases fail in the same way: if we try to improve this by adding on some more rows and columns, to get a $(3+m)×(4+n)$ grid, then we find:
$$\text{amount needed} ≤ \text{amount usable}$$ $$(2+m)(3+n) ≤ (3+m)(4+n)/2$$ $$6+3m+2n+mn ≤ \frac12(12 + 3n + 4m + mn)$$ $$6+3m+2n+mn ≤ 6 + \frac32n + 2m + \frac12mn$$ $$ m + \frac12n + \frac12mn ≤ 0$$ If $m$ and $n$ are positive, or if one is positive and the other is zero, the left side will always be positive, and this inequality breaks. Therefore we can't add any more rows or columns on without needing more blockers than we have.

---

What about other arrangements of the same size?

On a 3×4, we need to place 6 blockers internally, and we have 6 blockers to work with. So every blocker must be internal. (Or in the T-pipe version, all segments that lead outside the grid must be used.)

This means we have to divide the 12 squares into 6 adjacent pairs. This means we're looking for a domino tiling of a 3×4 grid.

There are only five such tilings (up to rotation and reflection). Of these five, three don't work - they would give loops. One of the others (the second on the right column) corresponds to the solution I found; the other is new.

Answer 2

A loop-less connected arrangement, in other words

a tree

has an edge fewer than

vertices.

As each T-pipe has 1 vertex and 1.5 edges there is an excess of edges which can only be mitigated at the boundaries: Each half-edge pointing outside can be ignored, at most

2n+2m

in an mxn rectangle. For the maximum to be attained every boundary tile must have a half-edge pointing out and each corner tile two half-edges. Then, regarding the difference of the numbers of vertices and edges (which must be one) each boundary tile is neutral, each inner tile adds half an edge and each corner removes half an edge. To end up with one more vertex than edges there must be exactly

2

inner tiles and the rectangle must be

3x4.

Arrangement:

    ┻┫┣┻
    ┳┫┣┳
    ┫┣┫┣
 

Bonus:

Because of the requirement that corner tiles have two half edges point outwards each has only two possible orientations:

    ****  ****
    ****  ****
    ┫***  ┳***
 

Further note that this forces the orientation of the non connected neighbour:

    ****  ****
    ****  ┻***
    ┫┣**  ┳***
 

We can now rule out two of the three (up to symmetry) configurations of two corner tiles sharing a short side of the rectangle:

    ┫***  ┻***
    ┫***  !***
    ┫***  ┳***
 

The left configuration cannot connect to the rest of the rectangle and the right one can not legally fit a boundary tile between the two corners.

That leaves:

    ┫┣**
    ┻***
    ┳***
 

and up to symmetry two ways of orienting all four corners:

    ┻**┻  ┫┣*┻
    ┳**┳  ┻**┳
    ┫┣┫┣  ┳*┫┣
 

Either has a unique extension to a legal rectangle:

    ┻┫┣┻  ┫┣┻┻
    ┳┫┣┳  ┻┻┳┳
    ┫┣┫┣  ┳┳┫┣