22
$\begingroup$

Inspired by Pipes.

This is a T-Pipe

T-Shaped Pipe

A T-Pipe connects to 3 adjacent cells.

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

Four T-Shaped pipes arranged in a 2x2 square

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.

$\endgroup$
4
  • $\begingroup$ Are holes inside an otherwise rectangular and connected shape allowed allowed? $\endgroup$
    – Bass
    Nov 2, 2022 at 8:01
  • $\begingroup$ No, the rectangle must be completely filled with T-pipes. $\endgroup$
    – Tim C
    Nov 2, 2022 at 15:46
  • $\begingroup$ I must be overseeing something: In the example: Which rule prohibits me from appending the topmost row to the top again and again and again... and make it size 2xinfinite $\endgroup$
    – Tode
    Nov 3, 2022 at 11:07
  • 1
    $\begingroup$ the smaller dimension dragging down infinite tilings being beatable by one one wider than that combined with the fact that 3 or wider at small side guarantees a loop on row repeat caught you $\endgroup$
    – masterX244
    Nov 3, 2022 at 12:27

2 Answers 2

22
$\begingroup$

I found a solution for

3×4:
solution for 3×4 grid

I claim this is optimal.

Proof:

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

blocker version

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.

loop diagram - failed version of above solution

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.

five domino tilings alternate 3×4

$\endgroup$
3
  • 1
    $\begingroup$ Nice proof; +1 and accepted! The conversion to domino tessellations is an interesting approach. When I was creating this problem, I structured my proof by constructing all possible 3x3's (there are only two, and they differ by only a single tile) and then extending them into 3x4s - a valid 3x4 must contain a valid 3x3, after all. $\endgroup$
    – Tim C
    Nov 2, 2022 at 15:58
  • $\begingroup$ @TimC "a valid 3x4 must contain a valid 3x3" I'm not so sure this is obvious due to the connectivity requirement. Could there not be a valid 3x4 in which both 3x3 subsquares have pipes that do not form a single connected network? We know now that this doesn't happen, but for a proof or exhaustive enumeration you'd have to entertain the possibility. $\endgroup$ Nov 3, 2022 at 14:27
  • 1
    $\begingroup$ @JaapScherphuis - That's correct. When I was writing this puzzle, I didn't include the connected network requirement at first. I added that requirement later on after knowing the answer (after I knew that all of the answers had that property) to make it easier by allowing people to use that property to discard answers early. $\endgroup$
    – Tim C
    Nov 3, 2022 at 15:51
19
$\begingroup$

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:

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

$\endgroup$
3
  • 1
    $\begingroup$ +1! This is indeed a correct solution. However, the green tick goes to Deusovi who solved the bonus as well. $\endgroup$
    – Tim C
    Nov 2, 2022 at 15:52
  • $\begingroup$ @TimC, accept whatever answer you choose, of course, but as far as I can tell, this answer also solves the bonus. Unless you dispute its claim that the construction of the two solutions is unique, or find that claim somehow unsatisfactory? $\endgroup$ Nov 3, 2022 at 19:41
  • $\begingroup$ @JohnBollinger I edited that in later for completeness. Didn't find it all that interesting in comparison to the main question after all it's just a bit of very finite case bashing. $\endgroup$
    – loopy walt
    Nov 3, 2022 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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