On 24/03/2016 03:41, James Propp wrote:
When we reduce one PSWN by 1, the number of path components cannot reduce by more than one -- for we cannot have components of more than two disconnected paths adjacent to a single square.
This lemma (if I'm understanding it correctly) cannot hold in full generality. Consider the PSWN array
010 101 010
(four separate loops) and the PSWN array
010 111 010
(a single loop); when we turn the former into the latter, a single PSWN changes by 1, but the number of components changes by 3.
It looks to me as if your first array has two loops, one clockwise and one anticlockwise. So I don't think this is a counterexample. But it does suggest a way to make one, because if we have a pattern like this 2 0 1 0 2 it implies four disconnected paths around the central square. They are pairwise *touching*, but fail to connect, which of course is the possibility my "proof" fails to consider. I wondered briefly whether there might be some impossibility about actually fitting this into a complete configuration, but it's pretty easy; e.g., with these PSWNs: 1 1 1 1 1 1 1 2 1 1 1 0 1 0 1 1 1 2 1 1 1 1 1 1 1 corresponding to a single anticlockwise loop on the outside, and two loops in each direction inside. Ah, but wait: this is OK, because decrementing one PSWN can only unify path components when the PSWNs inside them become equal to the PSWN of the square we're changing. And it *is* true that a single square of PSWN x can be adjacent to at most two other squares with PSWN x-1. (Because if two such squares meet at a corner then their path components are not in fact disconnected.) -- g