13
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ I spent a lot of time looking at this puzzle on multiple days, but I still don't understand it. What do you mean "the longest king chain is the shortest"? The shortest king chain can always be just one cell. Also do we want the longest chain over 1 to be as long as the chain over 0? I am really confused... $\endgroup$ – Dmitry Kamenetsky Feb 22 at 6:36
  • 1
    $\begingroup$ @DmitryKamenetsky "The length of the longest king chain" (which is the longest out of all 0-chains and 1-chains) is defined for each 5x5 board. The task is to find the board(s) that minimizes the property across all 5x5 boards. Would it be better if I change the question to "the longest King chain is minimized"? $\endgroup$ – Bubbler Feb 22 at 6:47
  • 1
    $\begingroup$ Oh I understand now. I would say "construct a 5x5 such that the length of its longest king chain (over 0 or 1) is as short as possible" $\endgroup$ – Dmitry Kamenetsky Feb 22 at 8:51
  • $\begingroup$ There are some very interesting extensions to this puzzle. You could increase the size of the grid, or you could increase the number of allowed digits. I am happy to show my best results for either. Or you could make a new puzzle for those variations. $\endgroup$ – Dmitry Kamenetsky Feb 23 at 7:22
7
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Both are exactly what I had in mind. But I don't have a convincing argument on why these are optimal, so let's see what others can come up with. $\endgroup$ – Bubbler Feb 16 at 0:59
5
$\begingroup$

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:


enter image description here

enter image description here
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".)

enter image description here
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.

$\endgroup$
3
  • $\begingroup$ It pains me to pierce your bubble of euphoria but I kinda fail to see how this would be "much more" elegant than Gareth's proof, mostly because I'm having a hard time seeing any substantial difference at all. Both seem to me walking the boundary between regions of either colour and perhaps most tellingly both rely on the same auxiliary padding. Also, your statement of the lemma is not stronger than the original one; what you are doing is specialising "0s" and "1s" for "one number" and "the other" which, technically, makes it weaker. +1 for including pictures, though. $\endgroup$ – Albert.Lang Feb 22 at 7:54
  • $\begingroup$ @Albert.Lang I was mainly referring to the first part - reducing it to a previously-solved (and fairly well-known) problem. You're right that my first restatement is not stronger (I had misread the original - thank you for the correction!), but I believe the additional part is. $\endgroup$ – Deusovi Feb 22 at 7:58
  • $\begingroup$ Ah, I just saw this. Seems like this problem has been mentioned in Puzzling before too: puzzling.stackexchange.com/a/22860/1649 $\endgroup$ – justhalf Mar 1 at 4:46
4
$\begingroup$

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
 

$\endgroup$
4
+100
$\begingroup$

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.

enter image description here enter image description here enter image description here

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.

enter image description here

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.

enter image description here

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.

enter image description here

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.

enter image description here

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

$\endgroup$
6
  • $\begingroup$ I, for one, like this one much better! It is just a single mechanism. Congrats on finding this elegant idea. Some visualization will be good though, especially for describing "leftmost direction". I am quite familiar with implementations of wall touching maze solving algorithm so can immediately recognize what you mean, but generally "leftmost direction" doesn't feel immediately intuitive at least for me. $\endgroup$ – justhalf Feb 22 at 5:56
  • $\begingroup$ Agreed, @justhalf, on both counts: It is quite elegant and a picture would be welcome. Now with this very nice proof my only regret is that I buried the lemma here instead of making it a separate question. $\endgroup$ – Albert.Lang Feb 22 at 6:06
  • $\begingroup$ Yeah, I agree that some pictures might help. I may add some. $\endgroup$ – Gareth McCaughan Feb 22 at 11:59
  • 1
    $\begingroup$ @Albert.Lang OK, I added some pictures. Of course they make the answer much longer, but hopefully clearer too. $\endgroup$ – Gareth McCaughan Feb 22 at 19:59
  • $\begingroup$ Whoa, this is a lot of effort. Kudos! $\endgroup$ – justhalf Feb 24 at 12:52
3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Hm, not as short and crisp as I was hoping for. But the central argument seems correct and elegant, though a bit difficult to follow. A picture would probably help (and be popular with the voters here), but seeing you are new here, I'm not sure you have enough reputation to add one. Anyway, good work and welcome to PSE. $\endgroup$ – Albert.Lang Feb 21 at 18:37
2
$\begingroup$

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$

$\endgroup$
2
  • $\begingroup$ Your interpretation of the rule is correct. Your "disconnected pairs" example has paths longer than 7 though. I see a 9 for zeros and 8 for ones. $\endgroup$ – Bubbler Feb 19 at 0:00
  • $\begingroup$ You are right! Rats. I am wrong. $\endgroup$ – user121330 Feb 19 at 0:02
1
$\begingroup$

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

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