Minimize the longest King chain on a 5x5 binary board

Question

Given a grid filled with numbers, let's define a King chain to be a path on the grid such that

1. the path can be traversed with chess King's moves (moving to one of 8 adjacent cells at a time),
2. the numbers on the path are all equal, and
3. the path does not visit any cell more than once.

Also, let's define the length of a King chain to be the number of cells visited by the chain.

For example, if the given grid is the following:

 |1 2 3 4
-+-------
A|1 0 0 0
B|0 1 1 1
C|1 0 0 1
D|0 1 0 1

then the longest King chain over zeros has length 7 (D3 - C3 - C2 - ... - A4), and the maximum length is the same for ones (D2 - ... - D4).

Now, can you find a 5x5 grid filled with zeros and ones which minimizes the length of its longest King chain, under the constraint that every pair of zeros and every pair of ones are connected via some King chain?

Bonus: What if we remove the constraint?

Answer 1

As a first attempt, longest king chain of 8:

 0 1 1 0 0
 0 0 1 0 1
 1 1 0 1 1
 1 0 1 0 0
 0 0 1 1 0

1s split the grid into four quadrants of zeros, so any path of zero can be at most of length 7 (2 of the quadrants + center). Path of 1 goes from any side, loops around the middle, and exits for length of 8.

As for the bonus,

 0 0 0 0 0
 1 1 1 1 1
 0 0 0 0 0
 1 1 1 1 1
 0 0 0 0 0

 Max length of 5

Pretty sure it can't be lowered - I don't think there's a way to envelope any group of four King-connected zeros using less than 5 connected ones.

Answer 2

Another proof of Albert's lemma (and one that I believe is much more elegant than the others presented):

I will prove a stronger lemma instead. Namely:

The original lemma stated that there is either a king's path of 0s going from top to bottom, or a king's path of 1s going from left to right.
I will show that this is true even if the kings cannot move along the ⤡ diagonal.

Proof:

This is a game of Hex, which is impossible to tie.

(A proof of the reduced statement follows. This proof is similar to Gareth's answer to the same question, but does not rely on an arbitrary choice of "leftmost".)

Consider the edges to be made up of a bunch of vertices of one color. Starting from the top, draw a border like this, always keeping red on one side and blue on the other.

This border cannot end inside a triangle, because if the path enters a triangle, it must have two vertices of one color and one of another. So it must end on a corner.
The border cannot end on the opposite corner, because the colors would flip. So the path will end on an adjacent corner. If the border ends on the left corner, then all the vertices on the right of the border will be a chain connecting the two blue sides; if it ends on the right corner, then the vertices on the left of the border will be a chain connecting the two red sides.

Answer 3

Here's (what I think is) a simpler proof of Albert's lemma than the one in loopy_wall's answer. We'll find either a king-path of 0-squares connecting N and S sides, or a king-path of 1-squares connecting W and E sides. The basic idea is to walk along the boundary between 0-squares and 1-squares until we reach an edge of the board. So here's an example board; red is for 0-squares, 1 for 1-squares. Alongside it, I've shown the path we will end up taking along the boundary, and then the king-path it enables us to construct.

So here's the actual construction. Stuff in italics is explanatory and accompanies the diagrams.

First of all, let's add imaginary 0-squares just outside the N and S sides of the board, and imaginary 1-squares just outside the W and E side of the board. (Obviously these make no difference to the existence of the paths we seek.) We don't add imaginary squares outside the corners.

We'll start at the NW corner of the board. If the square in this corner (inside the board, not one of our imaginary extra squares) is a 0-square, we shall start walking south along its western side; if it's a 1-square, we shall start walking east along its northern side. Either way, we have 0 to our left and 1 to our right.

At every new square-corner we reach, we have 0 behind us to our left and 1 behind us to our right. Pick the leftmost available direction that also has that property. (There always is one, unless we have hit a corner.)

Here's how we begin with the board above: we start at the NW corner; then we head S rather than E because that puts red (0) on our left and blue (1) on our right as required; at the next grid-point we turn left to keep red on the left and blue on the right.

At this point we could continue either northward or southward and have red on our left and blue on our right! We choose to go northward, because that lets us turn left as far as possible / right as little as possible while satisfying that condition.

If we reach the SW corner (or indeed the S side), then to our left we have constructed a N-S 0-path. If we reach the NE corner (or indeed the E side), then to our right we have constructed an E-W 1-path. We cannot return to the NW corner or reach the SE corner -- the edges there have 0 on the right or 1 on the left.

If neither of those happens then we must go around for ever, in a loop. Is this possible? Suppose it happens and consider the first edge we traverse twice. We've already established that we can't return to the NW corner, so this isn't the very first edge in the path.

But it also can't be a later edge. Suppose our sequence of edges goes ..., e, f, ..., e', f, ...; e, e', f all have 0 on the left and 1 on the right, and f is the leftmost such edge after e and also after e'. That is, if you imagine pointing backwards along e and swinging your arm clockwise until it reaches f, it's always pointing into a 0-square when you do that; likewise with e',f. But if e,e' are not the same edge, one of those arm-swings must go past either e or e', which is impossible because each of those edges has 0 on one side and 1 on the other.

Here's part of a path, showing edges e,f. The arrow indicates the direction in which the path is traversed. Of course a real path has only horizontal and vertical edges; this is purely schematic.

The pink region is composed of 0-squares, because f was the leftmost-possible edge with 0 to the left and 1 to the right after e. The diagram would look qualitatively the same if we looked at e',f instead of e,f.

Here's what we get with e,e',f. In this diagram e' is to the right of e, but of course they could be either way around.

And the problem is that e lies strictly inside that 0-only region created by e',f, which is impossible because it needs to have 1 on its right. (If e were on the right and e' on the left, the problem would be that e' lies inside the 0-only region created by e,f.)

So: we can't loop, so we must hit a corner, and at that point we have constructed one of the kinds of paths we wanted.

---

(Is this actually an answer to the question? Yeah, kinda, because it justifies an answer of 5 to the bonus question, as remarked by Albert. But really I'm posting it because Albert wanted a nice proof of his lemma and seemed not 100% satisfied with loopy_wall's, and maybe he might like this one better.)

Answer 4

Here is an obviously true but devilishly hard to actually prove lemma from which optimality of

5

for the bonus question follows:

Lemma:

For any nxm rectangle there is either a north-south path of one number or an east-west path of the other (or both).

No proof :-(

Also, alternative solution for the main question:

    01010
    01010
    10101
    10101
    10100
 

Answer 5

Proof of Albert's lemma (which solves the bonus question; please note that some repetitive details are omitted to keep down overall length to something reasonable):

Instead of 0s and 1s it will be more convenient to use black and white because we will want to split up each colour into connected components b1,b2,b3,... and w1,w2,w3,... The individual squares of a connected component, for example b1, will be numbered b11,b12,b13,... Let us assume m,n >= 2. Consider the boundary of a black-and-white mxn rectangle.
Example (with boundary typeset in italics):
b11 b12 w11 b21 w12 b22
b13 w13 w14 w15 b23 b24
w16 w17 b31 w18 b25 w21
b41 w19 w1A w1B b26 w22
The lemma follows from:
Technical lemma: Given four squares on the boundary wxj,byk,...,bym,wzn,...,[wxj] (meaning we start at white square number j of connected component x and make one full round on the boundary counter-clock-wise finding two black squares m and n of connected component y, the first of them directly following wxj and the second directly preceding a white square wzn). Then at least one of the following two is true:
S1. There is another black square of connected component y between (ccw) wzn and wxj
S2. z=x, i.e. the given white squares are actually in the same connected component

Please note that we do not require byk and bym to be distinct.

We will prove this by induction. Assume it has been shown for all smaller rectangles.
Case 1: There is an entire side of the boundary between wzn and wxj. If S1. does not hold we can remove this side without breaking y and use induction assumption. If S2. is true, it will also be true in the full rectangle. If S2. is false, then S1. is true in the reduced rectangle. Let byj1,byj2,... all the black squares of connected component y that lie on the boundary of the reduced rectangle between wzn and wxj. If not all of them lie on the newly created bit of the boundary, S1. holds also on the full rectangle. It also holds, if any of the squares above an y square in the newly created edge of the boundary is black. Otherwise, i.e. if all squares above the component y squares are white, consider the connected stretches of component y on the boundary of the reduced rectangle between bym and byk. These are interrupted by white squares (and possibly black squares not in y). This will look like byj1,wus,...,wvt,byj2. Now apply the Technical lemma to wvt,byj2,...,byj1,wus,...,[wvt]. By construction, S1. does not hold; hence S2. must and we have u=v. But now the "submerged" connections like wus-wvt alternate with superficial (in the full rectagle) white stretches, which implies that S2. (x=z) holds.

Case 2: All the rest. If S1. does not hold, we choose a side to remove as in case 1, but it will contain at least one of wzn,wxj and possibly its/their neighbour bym,byk. If the latter is the case we choose as replacement for bym/k the first/last black square in the boundary of the reduced rectangle that is connected to bym/k in the union of the boundaries of the full and reduced rectangles. If this is not possible because bym and byk are (ccw) connected in the union, it is easy to verify Technical lemma for the full rectangle. Otherwise we can apply Technical lemma to the reduced rectangle similar to case 1.

It remains to root the induction by directly showing Technical lemma for all rectangles of width 2. This is left as an exercise.

Answer 6

Every pair of zeros and every pair of ones are connected via some King chain

is confusing. If you mean that every $1$ can be reached from every other $1$ by the traversal rules (similarly for $0$), then I think 8 is a minimum. If we can have disconnected pairs,

    11000
    00011
    11100
    10101
    10101  

gets you to 7.

As for a proof, there might be fertile ground in looking at what can stop a path (board edges and lines/cups) in combination with the possible lengths of dead ends. It would be hard to beat an algorithm that built paths like this:

 10101010            1010101
 10101010            1010101
 10101010            1010101
 10101010     or     0101010
 01010101            0101010
 01010101            0101010
 01010101            0101011  essentially @Albert.Lang 's solution
 01010101  

Which have path length $l$ for a given square dimension $d$ of

$l = 2d-2$

Answer 7

I finally wrote a heuristic solver that finds good solutions. I found many solutions that achieve the longest chain length of

8, but none that do better. So I believe 8 is the optimal.

Here are some example solutions

0 0 1 0 1
1 0 1 0 1
0 1 0 1 0
0 1 0 1 1
1 1 0 0 0

1 0 0 1 1
1 1 0 1 1
0 0 1 0 0
1 1 0 1 0
1 0 0 1 1

0 0 0 0 0
1 1 0 1 1
1 1 0 1 0
0 0 1 0 1
1 1 1 0 1

0 0 1 1 0
1 1 0 0 0
0 1 0 1 1
1 0 1 0 0
1 0 1 1 0

0 1 1 0 1
0 0 0 1 1
1 1 1 0 0
1 0 0 1 0
1 0 1 1 0