网格染色问题

mathe

“短距复制”和“长距复制”只能应用于5*6矩阵，通用情况，使用范围还是比较有限吧。当然具体到总数为6的情况，我们会发现通常会要求连续4格只有一个黑格，确定一个黑格就会确定一批白格。但是想证明一个通用定理有点困难

hujunhua

mathe 发表于 2020-7-16 10:15
“短距复制”和“长距复制”只能应用于5*6矩阵，通用情况，使用范围还是比较有限吧。当然具体到总数为6的情 ...

在更大的nXn(n>8)网格中，也同样不能出现□□■□□■□□片段。否则照样子子孙孙复制满列。

hujunhua

把30#的6黑格无解的证明中省略的链式反应补充说明一下。
我们把■※※※□、■※※※※□这样的黑白对称为种子 ，两个黑白格互称（彼此的）配子，分为长配子和短配子。
在⬜⬜⬛⬜⬜⬛⬜⬜中，两个黑格都是长配短配俱全，只要在一侧有足够的行数，就能同时实现复制。
只要两个黑格（和两个白格）复制过去，其余两个白格也跟着复制过去。
短距复制轨道为：行1↔5, 行2↔6, 行3↔7, 行4↔8, 无行不成对。
长距复制轨道为：行1←→6, 行2←→7, 行3←→8, 行4与行5无对。

两种轨道并存的，就会结成复制链：5↔1←→6↔2←→7↔3←→8↔4连通了全部8行，
如果在一端点火，链式反应就从端到端贯穿全链。
如果从中间点火，链式反应就双向推进波及全链。

mathe

5黑格的无限扩张图最简单，
本质上只有两种无穷地毯, 每个4*4模块每行每列正好各1个黑格，然后周期复制:
0010001000100010⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜
0001000100010001⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛
1000100010001000⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜
0100010001000100⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜
0010001000100010⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜
0001000100010001⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛
1000100010001000⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜
0100010001000100⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜
0010001000100010⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜
0001000100010001⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛
1000100010001000⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜
0100010001000100⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜
0010001000100010⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜
0001000100010001⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛
1000100010001000⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜
0100010001000100⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜

0010001000100010⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜
1000100010001000⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜
0001000100010001⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛
0100010001000100⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜
0010001000100010⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜
1000100010001000⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜
0001000100010001⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛
0100010001000100⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜
0010001000100010⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜
1000100010001000⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜
0001000100010001⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛
0100010001000100⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜
0010001000100010⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜
1000100010001000⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜
0001000100010001⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛
0100010001000100⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜⬜⬛⬜⬜

mathe

对于无穷大的棋盘，将每个格子填上0/1，要求任意$m×n$的矩行里面的数字之和都是常数h, 其中$0<h<mn，gcd(m,n)=1$.

猜测染色方案必然是周期的，并且按复制定律要么形成长距复制轨道（周期5），要么形成短距复制轨道（周期4）。
问题是如何去证明这一点。

记格子$(i,j)$中填充的0/1为$a(i,j)$, 按前面的对角格等式有
$a(m+i,j)-a(i,j)=a(m+i,n+j)-a(i,n+j)$
$a(n+i,j)-a(i,j)=a(n+i,m+j)-a(i,m+j)$
容易周期扩展得出对于任意整系数参数 `u,v` 有
$a(u m+i,j)-a(i,j)=a(u m+i,v n+j)-a(i,v n+j)$
$a(v n+i,j)-a(i,j)=a(v n+i,u m+j)-a(i,u m+j)$
或者
$a(i,j-v n)-a(i-u m,j- v n)=a(i,j)-a(i - u m,j)$
$a(v n-u m+i,j-v n)-a(i-u m,j - v n)=a(v n- u m+i,u m- v n+j)-a(i- u m,v n- u m+j)$
两式相减得
$a(i,j-v n)-a(v n-u m+i,j-v n)=a(i,j)-a(i - u m,j)-a(v n- u m+i,u m- v n+j)+a(i- u m,v n - u m+j)$
由$(m,n)=1 → &#8707;s,t\ |\ s m-t n=1$, 将 `s` 和 `t` 替换上式的 `u` 和 `v` 得到
$a(i,j-t n)-a(i-1,j-t n) - a(i- s m,j-1) + a(i - s m,j)=a(i,j)-a(i-1,j-1)$

mathe

上面方法还是不能直接证明存在周期。
我们可以现在证明下面一个引理：
对于35#的条件，存在整数K, 在确定任意一个大小为$K \times K$的正方形网格中的数据以后，整个无限网格中所有其它格子的数据也可以被唯一确定。
取$K=m+n$
我们不妨假设这$K\times K$网格为$a_{u,v}$其中$-K\le u\le -1, 0\le v \le K-1$, 我们只要能够证明可以唯一确定$a_{0,v}$,其中$0\le v \le K-1$即可。
我们有方程$a_{0,0}+a_{0,1}+...a_{0,m-1} = a_{-n,0}+a_{-n,1}+...a_{-n,m-1}=b_0$,
依次类推，还可以有方程$a_{0,h}+a_{0,h+1}+...+a_{0,h+m-1}=b_h$, 其中$0\le h\le K-m$
同样我们还可以得出方程$a_{0,h}+a_{0,h+1}+...+a_{0,h+n-1}=c_h$, 其中$0\le h\le K-n$
这样我们一共得出关于K个变量$a_{0,0},a_{0,1},...,a_{0,K-1}$的$2K+2-m-n=K+2$条方程。
如果我们能够证明上面方程对应的矩阵列满秩，那么就可以证明上面的方程组如果存在解，解必然唯一，也就是确定$K\times K$网格中的数据，必然能够确定其右边一列的数据（同理确定左边一列，上面一行，下面一行的数据），依次类推可以确定整个无穷网格中所有位置的数据。
而如果我们能够证明方程组（*)
$a_{0,h}+a_{0,h+1}+...+a_{0,h+m-1}=0$, 其中$0\le h\le K-m$
$a_{0,h}+a_{0,h+1}+...+a_{0,h+n-1}=0$, 其中$0\le h\le K-n$
没有非零解，那么也就能够证明对应矩阵列满秩。

而从方程组(*)中我们可以得出$ a_{0,h}=a_{0,h+u m}, a_{0,h}=a_{0,h+v n}$
所以可以得出$a_{0,h} = a_{0, h+u m-v n}$, 由此可以进一步得出对于任意的u,v有$a_{0,u}=a_{0,v}$,由此代回原方程组得出方程组只有零解，所以对应矩阵列满秩。

由此我们证明了这个局部确定整体的引理。

mathe

有了局部确定整体的性质以后，就可以证明周期性了。
我们任意选择一个$K\times K$的初始正方形网格。我们查看整个无穷网格这个正方形网格所在的K行和K列。
由于这K行任意连续K列构成的$K\times K$子正方形的取值只有$2^{K^2}$有限种情况，必然存在两个不同子正方形取值完全相同，在通过楼上部分确定整体的引理可以得出这K行存在周期性。同样可以得出K列的结果也存在周期性。
然后在利用部分确定整体引理可以计算得出整个无穷网格在两个方向都存在周期性，只是周期是多少还没有计算出来。
如果进一步计算分析，会可以得出两个方向周期只能都是m或都是n (待续).

mathe

假设现在数据是每P列是一个周期，每Q行是一个周期。
如果我们对任意相邻的mP列求和，那么得到的和必然有周期n,由于同时Q是一个周期，所以没mP列的和以(n,Q)为周期。由于P列一个周期，所以每P列的和也以(n,Q)为周期。
同理，可以得出每相邻P列的和也以(m,Q)为周期。由此得出每相邻P列的和必然以((m,Q),(n,Q))=1为周期，也就是每相邻P列的和全部相等，同样每相邻Q行的和得到的数也全部相等。

mathe

选择连续mn行求和，得到的和必然同时以m和n为周期，得出和为常数，而且这个常数和行的位置没有关系，所以mn必然是周期

mathe

在得出mn同时为横向和纵向周期以后，我们可以选择任意一列，假设在一个周期内对于数据为$x_0,x_1,...,x_{mn-1}$, 我们还可以利用周期性扩展到无穷项 （也即是$x_{i+mn}=x_i$)
同时，在这一列向前若干个m列的对应的数据为$c_0,c_1,...,c_{mn-1}$,而向前若干个n列对应的数据为$d_0,d_1,...,d_{mn-1}$，我们可以适当选择使得c列和d列相邻
于是根据胡氏对角扩展公式，有
$x_i-c_i=x_{i+u m}-c_{i+u m}$
$x_j-d_j=x_{j+v n} - d_{j+v n}$
取$j=i+ u m$,代入得出$x_i-c_i+c_{i+ u m} - d_{i+ u m} = x_{i+ u m} - d_{i+u m}=x_{i+u m+ v n} - d_{i+ u m + v n}$
注意到将u取遍$0,...,n-1$,v取遍$0,...,m-1$时， $i+ u m +v n$会取遍模$mn$的同余系
所以我们知道$\sum_{u=0}^{n-1}\sum_{v=0}^{m-1}x_{i+u m+ v n} = \sum_{u=0}^{n-1}\sum_{v=0}^{m-1} d_{i+ u m + v n}$ (连续mn行任意两列和相同）
所以我们得出$\sum_{u=0}^{n-1}\sum_{v=0}^{m-1}(x_i-c_i+c_{i+ u m} - d_{i+ u m}) =0$
于是$\sum_{u=0}^{n-1}(x_i-c_i+c_{i+ u m} - d_{i+ u m}) =0$， 即
$n(x_i-c_i) = \sum_{u=0}^{n-1} d_{i+um} - \sum_{u=0}^{n-1}c_{i+um}$

这个结论很强，也就是说如果我们对于某个数据$x_i$,如果其前面m列同行的位置上$c_i$与其不同，那么必须所有$c_{i+um}$和$c_i$相同，所有的$d_{i+um}$和$x_i$相同。
这时替换i为$i+u m$上面的结论不变，所以所有的$x_{i+u m}$也都相同。
这说明对于任意一行中的一个数据$x_i$,如果从$x_i$出发在这一行每隔m个数据得到的数不全部相等，那么从$x_i$出发在这一行每隔n个数据得到的数必然全部相等。
然后我们可以反证得出这一行必然以m或者n为周期。比如假设某个每隔m个数的间隔全部是1，那么对于任意0，就不可能每隔n个数还是0（因为这两个集合必然相交），
所以所有的0必须每隔m个数还是0，由此再次得出所有的1同样每隔m个数还是1，也就是周期必然是m.
显然我们等于得出每行数周期必须是m或n