logoChat01.ai

请您帮我解决这个问题：四：给定正整数n是6的倍数。将一个n*n方格表的每个格子染成三种颜色之一，满足...

تم الإنشاء في: ١٨ أغسطس ٢٠٢٦

تمت الإجابة باستخدام GPT-5.6 Thinking بواسطة Chat01

سؤال

请您帮我解决这个问题：四：给定正整数n是6的倍数。将一个nn方格表的每个格子染成三种颜色之一，满足任何两个有公共边的格子的颜色都不一样，并且三种颜色的格子数量都相同。将13或者3*1形状的矩形称为“条形”，如果一个条形中有且只有三种颜色，则称它是“好的”，问至少有多少个好的条形。

Python

python
from itertools import product
def row_states(n):
    rows=[]
    for r in product(range(3), repeat=n):
        if all(r[i]!=r[i+1] for i in range(n-1)):
            hc=sum(r[i]!=r[i+2] for i in range(n-2)) # good if endpoints differ
            cnt=tuple(r.count(c) for c in range(3))
            rows.append((r,hc,cnt))
    return rows
len(row_states(6))


96

Python

python
n=12;m=6
for c in range(3):
    bd=0
    for i in range(n):
        for j in range(n):
            if grid[i][j]!=c: continue
            if i+2<n and grid[i+2][j]!=c: bd+=1
            if i-2>=0 and grid[i-2][j]!=c: bd+=1
            if j+2<n and grid[i][j+2]!=c: bd+=1
            if j-2>=0 and grid[i][j-2]!=c: bd+=1
    print(c,bd)

Python

python
import numpy as np, random, math
# random generate color distributions maybe solve via scipy optimize for desired majorities patterns
from scipy.optimize import linprog
# variables p[v,c] 12
edges=[(0,1),(0,2),(1,3),(2,3)]
def feasible_with_majorities(assign): # assign dict v->c requiring p[v,c]>=2/3+eps perhaps
    Aeq=[];beq=[]
    for v in range(4):
        row=np.zeros(12)
        for c in range(3): row[3*v+c]=1
        Aeq.append(row);beq.append(1)
    for c in range(3):
        row=np.zeros(12)
        for v in range(4): row[3*v+c]=1
        Aeq.append(row);beq.append(4/3)
    Aub=[];bub=[]
    for u,v in edges:
        for c in range(3):
            row=np.zeros(12);row[3*u+c]=1

الفكرة

Derived and optimized Cheeger bounds for balanced colored grid components

Worked for 7m 17s

الإجابة

答案是

3n2.\boxed{\frac{3n}{2}}.

下面给出一个完整证明。关键思想是：一个 1×31\times3 或 3×13\times1 条形是好的，当且仅当它的两个端点颜色不同。

设

n=6k,m=n2=3k.n=6k,\qquad m=\frac n2=3k.

一、把原问题压缩成 4 个 m×mm\times m 方格

按行、列编号的奇偶性，把 n2n^2 个格子分成四类：

(奇,奇)(奇,偶)(偶,奇)(偶,偶)\begin{matrix} (\text{奇},\text{奇})&(\text{奇},\text{偶})\\ (\text{偶},\text{奇})&(\text{偶},\text{偶}) \end{matrix}

每一类都有 m2m^2 个格子。

在同一类中，把原来横向或纵向相距 2 的两个格子连起来。这样，每一类恰好形成一个 m×mm\times m 的方格图。

而原棋盘中的每一个条形

AAA\boxed{\phantom A}\boxed{\phantom A}\boxed{\phantom A}

恰好对应于这个新方格图中的一条边——这条边连接条形的两个端点。

由于中间格子的颜色与两个端点都不同，所以：

  • 两端颜色相同，条形为 ABAABA，不是好的；
  • 两端颜色不同，那么中间格子只能是第三种颜色，所以三格颜色恰为三种，条形是好的。

因此：

好条形的数目 = 这四个 m×mm\times m 方格图中“两端颜色不同”的边的总数。

下面只需估计这个数。

二、一个小引理

考虑任意一个 m×mm\times m 方格，其中某一种颜色占的比例最多，为 1−d1-d。

记不同颜色端点的边数为 BB。我们证明

B≥mmin⁡{1,4d}.(1)B\ge m\min\{1,4d\}. \tag{1}

取数量最多的那种颜色，其格子集合为 SS。只考虑一端在 SS、另一端不在 SS 的边，设数量为 ∂S\partial S，显然

B≥∂S.B\ge \partial S.

令

q=min⁡{∣S∣, m2−∣S∣}.q=\min\{|S|,\,m^2-|S|\}.

我们证明

∂S≥min⁡{m,4qm}.(2)\partial S\ge \min\left\{m,\frac{4q}{m}\right\}. \tag{2}

设有 rr 行同时含有 SS 中和 SS 外的格子，有 cc 列也是如此。每个这样的行至少贡献一条横向边，每个这样的列至少贡献一条纵向边，因此

∂S≥r+c.\partial S\ge r+c.

如果 r+c≥mr+c\ge m，(2) 已成立。

否则 r+c<mr+c<m。此时一定存在“纯行”和“纯列”。所有纯行必须是同一种类型，否则每一列都会同时碰到 SS 与其补集，导致 c=mc=m；同理所有纯列也是同一种类型，并且纯行、纯列的类型必须相同。

所以较少的那一部分只能出现在这 rr 个混合行与 cc 个混合列的交叉处，从而

q≤rc≤(r+c)24.q\le rc\le\frac{(r+c)^2}{4}.

故

r+c≥2q.r+c\ge2\sqrt q.

又因为这时 q<m2/4q<m^2/4，所以

2q≥4qm.2\sqrt q\ge\frac{4q}{m}.

于是 (2) 得证。

现在回到比例 1−d1-d。最多颜色至少占 1/31/3。

  • 若 d≥1/4d\ge1/4，则较小一侧至少达到 m2/4m^2/4，或最多颜色本身介于 m2/4m^2/4 和 3m2/43m^2/4 之间，因此由 (2)
B≥m.B\ge m.
  • 若 d<1/4d<1/4，最多颜色超过 3/43/4，其补集大小为 dm2dm^2，所以
B≥4dm2m=4dm.B\ge \frac{4dm^2}{m}=4dm.

于是引理 (1) 成立。

三、四个小方格的“多数颜色”不能过于集中

对四个奇偶类分别编号为

P1=(奇,奇),P2=(奇,偶),P3=(偶,奇),P4=(偶,偶).P_1=(奇,奇),\quad P_2=(奇,偶),\quad P_3=(偶,奇),\quad P_4=(偶,偶).

它们的邻接关系形成一个四边形：

P1−P2−P4−P3−P1.P_1-P_2-P_4-P_3-P_1.

设第 ii 个小方格中最多的颜色所占比例为

1−di.1-d_i.

由上一节，它贡献的好条形至少为

mmin⁡{1,4di}.m\min\{1,4d_i\}.

因此我们只要证明

∑i=14min⁡{1,4di}≥3.(3)\sum_{i=1}^4\min\{1,4d_i\}\ge3. \tag{3}

称

di<14d_i<\frac14

的 PiP_i 为“重”方格，此时它有一种颜色占超过 3/43/4。

这里用到两个简单事实。

首先，每一种颜色在四个 PiP_i 中的总比例为

n2/3m2=43.(4)\frac{n^2/3}{m^2}=\frac43. \tag{4}

其次，若 Pi,PjP_i,P_j 在上面的四边形中相邻，那么对任一种颜色 XX，都有

pi(X)+pj(X)≤1.(5)p_i(X)+p_j(X)\le1. \tag{5}

例如 P1,P2P_1,P_2 合起来就是所有奇数行中的格子。在一条长度 2m2m 的行中，同一种颜色不能相邻，所以至多出现 mm 次；把 mm 条奇数行相加就得到 (5)。其他三对完全相同。

现在分类讨论重方格的个数。

只有 0 个或 1 个重方格

显然 (3) 成立，因为至少三个非重方格各贡献 1。

恰有 2 个重方格

设它们的 dd 之和为 DD。

如果两个重方格相邻，它们的多数颜色一定不同，否则违反 (5)。取第三种颜色 CC。它在两个重方格中的总比例至多 DD；而另外两个方格互相相邻，所以由 (5)，其中 CC 的比例之和至多 1。

结合 (4)：

43≤D+1,\frac43\le D+1,

故

D≥13.D\ge\frac13.

如果两个重方格相对，它们的多数颜色也不能相同，因为否则这种颜色的总比例至少

2−D>32>43.2-D>\frac32>\frac43.

设多数颜色分别是 A,BA,B，第三色为 CC。另外两个方格都与这两个重方格相邻，因此在每一个中，

p(A)≤d1,p(B)≤d2,p(A)\le d_1,\qquad p(B)\le d_2,

所以

p(C)≥1−D.p(C)\ge1-D.

两个方格合计至少有 2(1−D)2(1-D) 的 CC，由 (4)

2(1−D)≤43,2(1-D)\le\frac43,

仍得到

D≥13.D\ge\frac13.

于是两个非重方格贡献 2，两个重方格贡献至少

4D≥43,4D\ge\frac43,

总和大于 3。

恰有 3 个重方格

这三个在四边形中形成一条长为 2 的路径。

三个多数颜色必须互不相同：相邻者显然不同；两个端点如果多数颜色相同，则这种颜色的总比例超过 3/23/2，与 (4) 矛盾。

设中间重方格的多数颜色为 BB，两端分别为 A,CA,C，三个 dd 之和为 DD。

第四个方格同时与 A,CA,C 两端相邻，所以其中

p(B)≥1−dA−dC.p(B)\ge1-d_A-d_C.

再加上中间方格中至少 1−dB1-d_B 的 BB，得到

43≥2−D,\frac43\ge2-D,

即

D≥23.D\ge\frac23.

因此

1+4D≥1+83>3.1+4D\ge1+\frac83>3.

不可能有 4 个重方格

因为相邻重方格的多数颜色不同，而四个方格只有三种颜色，所以有两个重方格的多数颜色相同；它们只能位于对角位置。

但这两个方格中该颜色的总比例超过

34+34=32,\frac34+\frac34=\frac32,

又与总比例 4/34/3 矛盾。

所以 (3) 完全得证。

于是好条形总数 GG 满足

G≥m∑i=14min⁡{1,4di}≥3m=3n2.G\ge m\sum_{i=1}^4\min\{1,4d_i\} \ge3m =\boxed{\frac{3n}{2}}.

四、构造达到 3n2\frac{3n}{2}

还要证明这个下界可以达到。

写成

n=6k.n=6k.

用三种颜色 R,G,BR,G,B。

前 4k=2n34k=\frac{2n}{3} 行依次交替使用

GBGBGB⋯GBGBGB\cdots

和

BRBRBR⋯ .BRBRBR\cdots.

也就是

GBGBGB⋯BRBRBR⋯GBGBGB⋯BRBRBR⋯⋮\begin{array}{cccccc} G&B&G&B&G&B&\cdots\\ B&R&B&R&B&R&\cdots\\ G&B&G&B&G&B&\cdots\\ B&R&B&R&B&R&\cdots\\ \vdots \end{array}

最后 2k=n32k=\frac n3 行依次交替使用

RGRGRG⋯RGRGRG\cdots

和

GRGRGR⋯ .GRGRGR\cdots.

所有横向相邻格、纵向相邻格显然颜色不同。

每一行恰好各有 n/2n/2 个所使用的两种颜色。每种颜色一共出现在 4k=2n/34k=2n/3 行中，所以每种颜色的格子数都是

2n3⋅n2=n23.\frac{2n}{3}\cdot\frac n2=\frac{n^2}{3}.

再数好条形：

  • 每行都是两色交替，所以没有横向好条形。
  • 在奇数列，只有前后两部分交界处产生 2 个好的竖条；
  • 在偶数列，交界处产生 1 个好的竖条。

奇数列、偶数列各有 n/2n/2 列，所以总数为

2⋅n2+1⋅n2=3n2.2\cdot\frac n2+1\cdot\frac n2 =\boxed{\frac{3n}{2}}.

所以最终答案确实是

3n2.\boxed{\boxed{\frac{3n}{2}}}.

مشاركة هذا السؤال والجواب