# Tag Info

5

EDIT: All solutions up to mirror symmetry, rotation, colour permutation found by brute force: End of EDIT. One possibility (I write X,O,+ for 0,1,2): A bit on how this was found:

2

It feels like this can be improved but the best I've been able to do so far is As follows

4

Using a modified version of Albert Lang's method on the previous question, the best I've managed so far is As follows

1

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

4

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: Proof: (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".)

4

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

3

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

2

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, gets you to 7. As for a proof, there might be fertile ground in looking at what can stop a path (...

4

Here is an obviously true but devilishly hard to actually prove lemma from which optimality of for the bonus question follows: Lemma: No proof :-( Also, alternative solution for the main question:

7

As a first attempt, longest king chain of 8: As for the bonus,

Top 50 recent answers are included