New answers tagged graph-theory
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
