14
$\begingroup$

Since challenge questions are up in the air, what better time to pose a puzzle-building question that's intrigued me for some time.

Preamble

Consider an infinite square grid made up of nodes and edges as shown in the following figure:

                         infinite square lattice

Each node connects to four edges, which are labeled top, left, right, and bottom as one would intuitively expect. Likewise, every square in the grid has four labeled edges. These labels are depicted in the two figures below.

                              node labels            grid square labels

Every edge in the grid has a parity label, which is either $A$ or $B$. Parity labels obey the following two symmetry rules:

  1. At every node, the multiset of parity labels of the top and right edges must equal the multiset of parity labels on the bottom and left edges.

    For example, if both the top and right edges have a parity label of $A$, then both the bottom and left edges must have a parity label of $A$. If the top and right edges have parity labels of $A$ and $B$ respectively, then then parity labels for the bottom and left edges must either be $A,B$ or $B,A$, respectively.

  2. For every grid square, the multiset of parity labels of the top and left edges must equal the multiset of parity labels on the bottom and right edges.

The idea of the puzzle is to find a rule (or rules) for assigning a parity label to each edge in the grid that satisfies rule 1 at every node and rule 2 for every grid square.

There are several trivial ways to do this, such as assigning $A$'s to all edges, assigning $B$'s to all edges, etc., but one additional complication exists. The grid must start in either of the following two states:

                     symmetry-breaking starting states

Note that rule 2 is satisfied for the fully-assigned grid square in both grids, but rule 1 is not satisfied for the two fully-assigned nodes. This broken symmetry is by design for these particular nodes in these grids.

None of the existing parity labels may be changed, and rule 1 applies everywhere except at the two symmetry-breaking nodes.

The amended goal of the puzzle is therefore to find a rule (or rules) for assigning a parity label to each edge in the grid that satisfies rule 1 at every node except at the two symmetry-breaking nodes, and satisfies rule 2 for every grid square.


Question

It's not intuitively obvious that the puzzle as stated above even has a solution. And indeed, all of my attempts to find a rule to populate the grid have lead to what I'll call "gridlock"—the inability to extend labels further in any direction without violating at least one of the two symmetry rules.

Unfortunately, "COTO gets consistently stuck" is far from a rigorous proof of non-existence of a solution, hence I shall commit the puzzle to the enterprising minds of puzzling.SE.

Does this puzzle have a solution? If so, what is it? If not, is there an elegant proof of this fact?

Answers and intuitions are welcome.

$\endgroup$
  • $\begingroup$ Have you been able to accomplish this for finite grids? If so, any particular shapes that stood out? $\endgroup$ – Josh Caswell Dec 4 '14 at 2:16
  • $\begingroup$ @JoshCaswell: None that were rectangular. My approach was generally to extend the grid as far as possible, and grids where edges are assigned iff they fall inside a rectangle are easily extended. The grid is inevitably quite irregular-looking when no more opportunities for extension exist. As for your second question: absolutely no patterns stood out for me, which is one of the reasons I strongly believe the puzzle isn't solvable. It's like the antisymmetry in the two nodes ripples outwards, ultimately ruining any attempt to restore symmetry. The madding thing is that I just can't prove it. $\endgroup$ – COTO Dec 4 '14 at 2:21
  • $\begingroup$ Yeah, I was thinking that non-rectangular shapes would be it. I'm wondering if there's a connection that can be made with aperiodic tilings. I'll see what I can come up with. $\endgroup$ – Josh Caswell Dec 4 '14 at 2:25
  • $\begingroup$ @JoshCaswell: If it helps, the motivation for this problem derives from trying to compute the resistance between two nodes in an infinite resistor network. There are several false proofs that give values, but it turns out that if you apply Kirchhoff's laws directly (rather than Z transforms, etc.), it's easy to show that the resistance of an infinite R network is ill-defined (it can take on any finite value). If the above problem is solvable, it implies the resistance of an infinite resistor network is ill-defined even if we impose the additional constraint of finite energy dissipation. $\endgroup$ – COTO Dec 4 '14 at 2:30
  • $\begingroup$ I think that each line (horizontal or vertical) of edges must all have the same parity label, unless it contains an exceptional node. This means that without the exceptional nodes, the solutions are given by assigning a parity label to each line. Or am I missing something? $\endgroup$ – xnor Dec 4 '14 at 2:30
6
$\begingroup$

I wouldn't call this 'elegant', but here's an argument that there can be no solution starting with Grid 1.

Diagram 1 Diagram 2

In the first diagram, edges 1-6 must all have the same label: edges 1 and 2 because of the square they share, then edges 3 and 4 because of the vertex they share with 1 and 2, and finally 5 and 6 because of the square they share with 2 and 4. Looking at the orange vertex shows that the common label for edges 1-6 must be A.

In the second diagram, edge 1 must get the label A (it is adjacent to a vertex with 3 A's), then edge 2 must also get the label A (it is adjacent two a square with 3 A's). But now we're stuck, as there is no way to make the symmetry rule hold at the green vertex.

I drew something similar for Grid 2. It was a slightly more complicated, but I again found that there could be no solution.

$\endgroup$
  • $\begingroup$ It's elegant enough. This is exactly what I was looking for. +1 $\endgroup$ – COTO Dec 4 '14 at 15:28
  • $\begingroup$ @COTO Apologies for the bump, but this is incorrect, as the locations 1 and 2 would not transpose in that way according to rule 2 across a square. $\endgroup$ – theREALyumdub May 22 '18 at 20:36
2
$\begingroup$

This is an extremely late bump so feel free to ignore me, but I found this mathematically interesting, and if it has theoretical implications then what the heck. Also, I take it you mean with rule 1 and 2 that it actually goes both ways, and not merely one way. I'll do a general case first, and then explain how it solves your case.

All Nodes and Boxes Follow The Rules

I claim the following:

Suppose every node and box in the grid follows rules 1 and 2 of symmetry, and two edges connecting to the same node at right angles have the same letter. Then the entire grid is that letter.

This requires two important observations. The first is that any two edges with the same letter like this will either be copied by a single box or a single node. Therefore, they are actually going to make two other right angled edges the same, their partner multi-set (I guess). From there, you can take the other two adjacent right-angled pairs, whether across a box or a node, and extend them using the other rule. Keep alternating rules and extending your rectangle, and you have the whole grid.

One way to think how this works is with a transformation. Draw lines in a square grid 45° off from yours, that pass through every box to make Xs. Then every edge is in one box, so you can draw a totally different type of grid, where the edges' letter is drawn in a box, and the boxes and nodes are just two different types of nodes on the grid. If you prefer, rotate the grid counterclockwise, and every node will have one of rule 1 (the upper right and upper left boxes adjacent to this node must have the same letter as the bottom boxes, a top-bottom rule) or 2 (the upper left and lower left boxes adjacent to this node must have the same letter as the right boxes, a left-right rule). Personally, I find this grid easier to understand, or at least to draw, since nodes and boxes are of the same type (rule nodes), and the edges just fill a box.

From this infinite grid result, we derive the only four solutions for the transformed infinite grid with symmetry at all nodes: all A, alternating A and B, or flip the letters on the previous two to get two more. To see why the alternating grids are the only other solutions, consider what would happen if two adjacent boxes (right-angled edges in the normal grid) were the same letter. If no adjacent boxes are the same letter on a square grid, you have a checkerboard pattern, and a specific, "fixed" box should be either white or black, giving the two solutions for a fixed position.

Your Problem

But your problem doesn't have all nodes following the same rules, and the way I stated the "theorem," it wouldn't apply here. However, you can build out an infinite solution in the same way in your examples, since the example is constructive.

Returning to the grid as you put it forward, every pair should have exactly one node or box that it duplicates to or from. So the outer double A pairs won't work to make an infinite grid in either example, since they duplicate to the broken edges on the inner box; there is a similar problem with taking pairs in any parallel diagonal in your examples.

If we try to build infinite grids out of the pairs in the other diagonal direction, however, we see the problems. These are the squares adjacent to the bad nodes that have two edges unlabelled. In your grid 1, they conflict between making one of the checkerboard patterns on the infinite grid, or making a grid of all A's. In grid 2, they make two conflicting checkerboard grids. Neither of these can be the static grid at the same time: so the pattern is impossible.

Checking these cases is very finite and fast, if you are looking at your static grids, or a transformed version of them. There's no problem going back and forth, as long as you keep your lefts and ups, etcetera correct.

$\endgroup$
  • $\begingroup$ I don't see how this explanation provides an answer. (Maybe an example of applying your ideas to create a working grid would help - just reading this as text without an example grid that shows it in practice isn't doing much for me here) $\endgroup$ – Rubio May 23 '18 at 16:11
  • $\begingroup$ @Rubio I agree, it would be much much easier to understand if I did that and I did draw one myself to see how this worked. I could edit this answer later, if you like. I just thought this was interesting in its own right as purely a mathematics problem. If you buy the premise that the symmetry rules give you only four grid solutions (as I tried to explain above), the OP's problem is just asking how many nodes you need to "break" to introduce other valid solutions. One's not enough, and my guess is not two either. $\endgroup$ – theREALyumdub May 23 '18 at 22:26
  • $\begingroup$ I believe I get the gist of what you're saying: start with a known solution and a complete set of legal perturbations, and show that it's impossible to produce a sub-grid as shown using only these perturbations. Even so, I'd also like a graphical explanation. +1 for your thoughtful response. I should note that this problem cropped up in the context of infinite resistor networks with finite values for all resistors. The symmetry conditions are greatly simplified versions of Ohm's law and Kirchoff's current law. $\endgroup$ – COTO Jun 12 '18 at 17:22

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.