8
$\begingroup$

A continuation in the Pipes puzzle series.

Problem statement for math nerds: Let $G(N)$ denote the graph consisting of cardinally adjacently linked lattice points on an $N \times N$ toroidal grid. For which $N$ does there exist a spanning tree of $G(N)$ in which every vertex has degree $1$ or $3$?

On the same website I linked to in the last problem, there is a curious variant of Pipes that removes the borders of the game, and instead allows pipes to wrap around in their solution (but as always, they must remain loop-free):

                                      enter image description here

One reason I like Pipes played on a torus besides the added difficulty is that it is more essentially minimalist; there is no "edge" and "center," instead we have a topologically homogeneous space.

What if we endeavored to make a version that's even more minimalist, and even more difficult? There are four types of tile that may comprise a Pipes puzzle: The bulbs with only one neighbor, the corners and straights with two neighbors, and the T's with three neighbors. We obviously need to keep the bulbs in any version of the game, and among all the tiles I would say in my experience playing Pipes that T's are the most ornery, so let's also keep them. The only problem is: Are there even any (square grid) Pipes puzzles to play when you use only bulbs and T's?

(Extra credit: What is the situation—with and without border wrapping—on arbitrary $m \times n$ grids?)

$\endgroup$
6
  • $\begingroup$ To answer someone's now-deleted comment: The source tile can be a bulb. But even if it couldn't be, you could just translate the grid (per toroidal addition, which is modular arithmetic in each coordinate) to guarantee the existence of a T-source solution from a bulb-source solution :) $\endgroup$
    – Feryll
    Apr 19 at 22:04
  • $\begingroup$ Would a solution just showing that this is possible be acceptable? (Also, sorry for deleting my comment; I figured it out by myself :) ) $\endgroup$
    – bobble
    Apr 19 at 22:12
  • $\begingroup$ It would at least serve as a partial answer; a full answer would say, for each $N$, whether or not a single solution exists on an $N \times N$ grid. $\endgroup$
    – Feryll
    Apr 19 at 22:15
  • $\begingroup$ Is there a reason that a "cross" tile is not on your list of possible tiles? I'm wondering if I'm missing something... $\endgroup$
    – Dr Xorile
    Apr 20 at 0:46
  • 2
    $\begingroup$ Crosses aren't a part of the Pipes game (presumably because they would always be in the solved state and so just water down the puzzle), and we're interested in a tile set restriction anyway. $\endgroup$
    – Feryll
    Apr 20 at 1:05
8
$\begingroup$

Suppose we have a solution, which is a tree graph with vertices of degree 1 and 3 only. This graph has the following property:

Any tree graph can be given a 2-colouring of vertices. This is a well-known fact that is easily proved by induction.
These bulb and T graphs have a stronger property: the number of vertices of each colour is odd.

This can be proved by induction:

This is obviously true for the base case where $v=2$, a graph consisting of two bulbs connected together. Induction step: Find any T vertex that has (at least) two neighbouring bulbs. This must exist, because otherwise you could travel from T vertex to T vertex indefinitely without retracing your steps, and this is not possible in a finite tree. You can replace this T and the two neighbouring bulbs by a single bulb. This reduces the number of vertices by 2, but both are of the same colour so the parities of the colours do not change. The resulting smaller tree graph must have an odd number of vertices of each colour by the induction hypothesis, and therefore so does the original tree graph.
By induction, the number of vertices of each colour is odd.

This property has some consequences for the $M\times N$ grids that can be filled with Ts and bulbs.

Clearly the total number of vertices is odd+odd=even, so $MN$ is even.
Furthermore, $M$ and $N$ cannot both be even. The colouring of the tree graph induces a 2-colouring on the grid, which is the essentially unique checkerboard colouring. This has an even number of squares of each colour, which contradicts that there must be an odd number of each.
Together this means that exactly one of the dimensions of the grid must be even.

If the grid is not on a torus, but a rectangular grid with hard borders, then we can strengthen this to say that the even dimension cannot be a multiple of 4. Here the checkerboard colouring of the grid is forced, and the colouring of each line in the even direction has an even number of each colour, and therefore this is not possible for the same reason. This does not necessarily hold on a torus because then there can be paths between adjacent squares of even length by wrapping around the board in the direction of the odd-dimension.

For square grids $N\times N$ this means that

there are no solutions.

Edit:

Here are pictures of general solutions for some grid sizes, not necessarily toroidal.

The top shows a general solution for a $3\times(4n+2)$ rectangle.
The bottom is a general solution for any $(4m+5)\times(4n+6)$ rectangle.
enter image description here

Edit 2:

Here is a solution for a grid that only works on a torus:

A toroidal (or cylindrical) solution for a $3\times4$, which cannot be solved without wrap-around borders at the top/bottom. By repeating the middle section it can be extended to any even length.
enter image description here

$\endgroup$
14
  • $\begingroup$ There's one thing that I don't quite buy (although it's irrelevant to the case of square grids, so I've marked it as accepted): "In fact, the even dimension cannot be a multiple of 4. The colouring of each line in the even direction has an even number of each colour, and therefore this is not possible for the same reason." Outside the even-by-even case, we know there is no toroidal checkerboard coloring, therefore the 2-coloring of the graph might look quite arbitrary on the grid, and I don't see why evenness need be attained on any row/column. $\endgroup$
    – Feryll
    Apr 20 at 9:13
  • $\begingroup$ @Feryll You are right. The path between adjacent squares on the line could wrap around and so be of odd length. I've edited that part to refer to non-toroidal boards only. $\endgroup$ Apr 20 at 9:30
  • 1
    $\begingroup$ @justhalf I just found a way to do any 3x(4k+2) board. $\endgroup$ Apr 20 at 13:13
  • 1
    $\begingroup$ @justhalf I have tried to find a solution to a 4m x 2n+1 grid (which in theory could be solvable only when toroidal), but haven't got one yet. I'll give it another shot. $\endgroup$ Apr 21 at 6:15
  • 2
    $\begingroup$ @justhalf I have added a 3x4 solution that I had completely overlooked. I had thought it impossible. $\endgroup$ Apr 21 at 10:08
6
$\begingroup$

To complement Jaap's excellent answer, a family of non-toroidal grids for odd length $4k+3$:

enter image description here
(and a family that allows $k=0$, for good measure:)
enter image description here

EDIT: And a family covering all the toroidal grids:

enter image description here

$\endgroup$
1
  • $\begingroup$ That general solution is a great find! $\endgroup$ Apr 21 at 13:58
1
$\begingroup$

I thought that I'd found counter-examples to the proofs given in the other answers:

2x2 grid

4x4 grid

However, I then realised that

These violate the constraint that the solution must not contain loops.

Instead we can

use these as a base of a more intuitive proof of impossibility, or a way to more easily visualise why those proofs work...

In particular,

to convert these non-solutions into a solution, we would need to break the loop in precisely one place, which could be trivially done by converting two adjacent T pieces into a straight or turn piece. However, other changes to convert these back to either a bulb or a T piece will necessarily involve making or breaking a link, which will either reconnect the loop, or create a disconnected section.

$\endgroup$

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.