How to prove Yin-Yang alternating 2 by 2 is not allowed

Question

Yin-Yang is a puzzle where one needs to fill each cells with either black circle or white circle following these rules:

1. Each color's circles must be connected to one another according to four-way orthogonal adjacency (diagonal connection is not allowed).
2. There is no $2 \times 2$ square containing four circles of the same color.

Suppose we have an alternating $2 \times2$ pattern anywhere in an $m \times n$ grid where $m,n \geq 2$.

How can I prove that this pattern will always breaks the rule number 1 anywhere in a grid?

Here is what I have tried so far:

• Suppose we are able to connect the black circles and any empty cells inside the connected path are colored.
  
  
• In order to to connect the white circles, the circles needs to be connected to a colored cell or to a cell that is not colored.
  
• It is not possible for both of them to connect to an uncolored cell, because one of them will be surrounded by colored cells or the red line.
  

Answer 1

If you are willing to accept as a known result that K₅ (i.e. the complete graph with 5 vertices) is non-planar (i.e. you cannot embed it into the plane, where each vertex maps to a point, and each edge maps to a continuous path connecting the endpoints, and no two of these paths intersect except where they meet at endpoints), then it is easy to answer your question.

Take the 4 dots as vertices and connect each adjacent pair by an edge. Add a 5th vertex in the centre and connect it to the other 4 by edges. Observe that if the puzzle has a solution then we would be able to add 2 more continuous paths to finish the embedding of K₅:

Thus the non-planarity of K₅ implies that there is no solution.

Answer 2

This kind of problem can very often be solved by a judicious application of well-ordering on ℕ, which informally says that for every property Q on ℕ that you write down, if some k∈ℕ satisfies Q then some minimum k∈ℕ satisfies Q. Well-ordering on ℕ is in turn equivalent to ordinary induction on ℕ, over PA⁻. (You don't need to know about PA⁻, but see here if you are interested to know the axioms of PA⁻ as well as the deductive rules needed.)

Using well-ordering on ℕ is in some sense a special case of using the extremal principle, although actually they are both equivalent. Either way, the idea is that if we have a finite set S of objects each with some sort of size (e.g. length), then we can extract more information by looking at a member of S that has minimum/maximum size (which is guaranteed to exist by well-ordering). So here I will give a completely discrete proof based on this technique.

---

Part 1

For convenience, we shall use a different grid, where there is a grid point at the centre of each original cell and a grid line through the centres of any row or column of original cells. Then the problem would be in terms of paths following the new grid lines than in terms of paths of original cells.

We 'turn the central square outside-in' in a discrete manner. To do so, first squash the grid outside the central square, making rows k and −k have height 2^−(k+1), and making columns k and −k have width 2^−(k+1), where the central square is in row 0 and column 0. The top-left quadrant looks like this:

 

Next we 'reflect each quadrant into the central square', and map the grid lines that connect adjacent quadrants to suitable rectangular curves that stay within the central diamond that passes through the 4 dots. The result for the top-left quadrant looks like this (with the central diamond in red):

 

The above outside-in transformation allows us to turn any pair of paths that follow the grid lines into a pair of rectangular paths that stay within the central diamond. Moreover, if the original pair satisfies the desired condition (i.e. they do not intersect and one path connects the black dots and the other path connects the white dots), then so does the transformed pair.

Furthermore, if the original paths do not go beyond n grid lines away from the central square, then the transformed paths would be contained within the grid lines of a finer regular grid with cell size 2⁻⁽ⁿ⁺¹⁾. In the above example diagram, if the original paths do not go beyond 3 grid lines away, then the transformed paths would be contained within a finer regular grid with cell size 1/16 (as indeed depicted).

So from now on we only consider pairs of paths following the grid lines of some finer regular grid that satisfy the desired condition and stay within the central diamond.

Part 2

I claim that no such pair exists. If it does, then by well-ordering some such pair (P,Q) has minimum total length. Each path can be viewed as a sequence of moves where each move is one of: F (go forward 1 unit) / L (turn left / R (turn right). We can assume an initial direction at the start of each path, so that the path itself starts and ends with F. Note that there is no (consecutive) LL or RR in any of P or Q, otherwise we can use the following mappings to shorten their total length: LLL↦R / RRR↦L / FLLF↦LL / FRRF↦RR.

Define a u-turn to be a sequence of moves in which: (a) every move is F except for the first and last; (b) the first and last moves are either both L or both R. Define the size of a u-turn to be simply the number of moves in it.

There are two cases.

Case 1: Neither P nor Q has a u-turn.

We can assume that P starts from the top-left dot and Q starts from the bottom-left dot. Since P and Q do not have any u-turn, each of them has strictly alternating L and R, so P must start facing right or down, and Q must start facing right or up.

Let V(0) be the left side of the central square, and V(k) be the k-th vertical grid line to the right of V(0). Let n be the number of vertical grid lines between the left and right sides of the central square. For each k∈[1..n+1], let p(k) be the lowest point that P reaches on V(k) (which exists by well-ordering), and similarly let q(k) be the highest point that Q reaches on V(k). We can easily check that, for each k∈[1..n], if p(k) is above q(k) then p(k+1) is above q(k+1), since P and Q do not intersect. (I will leave this bit as an exercise.) Therefore, by induction, p(n+1) is above q(n+1), which is impossible because p(n+1) is no higher than the bottom-right dot and q(n+1) is no lower than the top-right dot.

Case 2: Either P or Q has a u-turn.

By well-ordering, let U be a u-turn that is in either P or Q and has minimum size. This choice of U is the crucial idea in the entire proof. Note that the moves just before or after U must both be F. So the path at U looks like this:

| · · · |
+ − − − +

where | and − denote the straight segments, and + denotes the turning points, and · denotes a grid point that is 'just inside' the u-turn. Let S be the set of these grid points 'just inside' U. I claim that neither P nor Q goes to any grid point in S. Why? If it does, then there are two cases:

1. Either P or Q goes into S and comes out from S. Again by well-ordering, there is a first move in P or a first move in Q that goes into S, but that move E must be made facing the same direction as upon the F just before performing U (from the top in the above diagram), and by a similar argument as before, we get another u-turn V starting just after E. It is easy to check that V has smaller size than U, contradicting the definition of U.

2. Either P or Q starts or ends within S. This is impossible, because the dots are at the boundary of the central diamond, so it cannot be directly between two points along either path P or Q, since P and Q stay within the central diamond.

Therefore neither P nor Q goes to any grid point in S. Hence we can remove the F just before U and the F just after U, shortening the path containing U but preserving the fact that P and Q satisfy the desired condition. This contradicts the definition of P,Q.

Therefore, no pair of paths in the grid satisfies the desired condition.

---

For interested readers, this technique can be used (in conjunction with a compactness argument) to prove any of the related theorems, including non-planarity of K₅, the Poincare-Miranda theorem, Brouwer's fixed point theorem, ...

This fact is totally relevant to this post because people very often cite one of these related theorems, especially non-planarity of K₅, in order to prove the kind of result we want here. What most people do not realize is that all these related theorems are highly non-trivial to prove, in fact even more difficult than the result we want. Since I gave here a purely discrete proof of the result we want, this ought to naturally invite the question of whether the related theorems are 'significantly' harder. The answer is no; the same technique plus a standard compactness argument is enough to easily prove those related theorems. This tells us that the proof I gave here is actually a proof of the core of the topological phenomenon we are interested in here, despite being purely discrete.