6
$\begingroup$

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$.

Grid Example

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.
    Filled Cells
  • 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.
    Blocked
$\endgroup$
8
  • 3
    $\begingroup$ Look up the Jordan curve theorem. This will prove the result for you, once you draw a diagonal line between the two initial blacks. (One white is on the inside of your path, one on the outside, and a path connecting the two whites must cross a path connecting the two blacks.) $\endgroup$ Apr 12 at 8:01
  • 2
    $\begingroup$ @DavidA.Craven why not turn that into a proper answer? $\endgroup$
    – bobble
    Apr 12 at 13:47
  • $\begingroup$ Is it possible to prove this using graph theory (instead of topology)? I presume that there is a connection between this problem and the planarity of a graph. $\endgroup$
    – Iqazra
    Apr 14 at 9:48
  • 1
    $\begingroup$ @DavidA.Craven: Jordan curve theorem is actually significantly more difficult to prove than simply the non-planarity of K5. See my answer for a completely discrete proof! $\endgroup$
    – user21820
    Apr 14 at 16:53
  • $\begingroup$ @Iqazra: You can put a 5th dot in the centre and connect it to the other 4, and use non-planarity of K5. However, non-planarity of K5 has the same non-trivial core as the related topology theorems, so you need something at least as complicated as my answer in order to get a complete rigorous proof. $\endgroup$
    – user21820
    Apr 14 at 16:57

2 Answers 2

4
$\begingroup$

If you are willing to accept as a known result that K5 (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 K5:

black-white puzzle reduces to K5 embedding

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

$\endgroup$
4
  • $\begingroup$ What is the idea behind adding a red dot that is adjacent to all four vertices? I know that your graph is isomorphic to K_5, and thus it is non-planar. However, I feel that there is a gap between the puzzle (the original 2-by-2 alternating pattern) and the graph that you constructed. $\endgroup$
    – Iqazra
    Apr 15 at 10:35
  • 1
    $\begingroup$ @Iqazra: All problems of this sort, where you essentially want to prove that any two paths within a topological disk must intersect if their endpoints are alternating on the disk boundary, are equivalent to non-planarity of K5. $\endgroup$
    – user21820
    Apr 15 at 10:50
  • $\begingroup$ @user21820: I still don't understand the idea behind the red vertex in the middle and connecting each of the dots to by edges. What are those edges represent in a Yin-Yang puzzle grid? $\endgroup$
    – Meep
    Apr 28 at 3:44
  • $\begingroup$ @Meep: If there is a solution to your Black-White puzzle, then there is some embedding of K5 into the plane, as shown by the diagram. To fully understand this solution, you must first of all understand the precise mathematical statement of non-planarity of K5, as well as basic FOL (first-order logic). As per basic FOL, it doesn't matter what I construct (there is no reason it has to represent anything), as long as I follow the deductive rules and arrive at the desired theorem (i.e. no solution exists). $\endgroup$
    – user21820
    Apr 28 at 5:29
3
$\begingroup$

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:

compactified grid as described

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):

top-left quadrant reflected inside central diamond

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−(n+1). 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: LLLR / RRRL / FLLFLL / FRRFRR.

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 K5, 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 K5, 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.

$\endgroup$
2
  • $\begingroup$ Cool idea! I'm really wondering whether there can be much easier proof to show than a curve connecting bottom and top side of a square will intersect with a curve connecting left and right side of a square. $\endgroup$
    – justhalf
    Apr 16 at 6:36
  • 1
    $\begingroup$ @justhalf: Based on what I know, I'm very sure that it is to some extent impossible to find a simpler proof. No doubt there will be many proofs that on the surface look completely different, but everything will ultimately have some hard discrete combinatorial core that has the same flavour as this one. Even for the simplest case where the curves comprise finite line segments, proving the result requires this kind of tweaking of some minimum-'size' section of the curve, not to say some geometric facts. Whereas here we have a grid, which is even simpler, and yet this is the easiest proof I know. $\endgroup$
    – user21820
    Apr 16 at 12:04

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.