将$13\times13$个格点三染色，求证存在一个同色矩形

abababa

如题，方格棋盘上的$13\times13$个格点用三种颜色染色，求证无论怎么染，都存在一个同色矩形。其中同色矩形是指四个顶点同色的矩形。

realnumber

性质一：涂色后，每条边，横与横，纵与纵都可以整行，或整列交换，出现或不出现同色矩形保持不变.
先考虑某条边,13个点至少有5个颜色一样,(否则,若最多4个,$4\times3=12<13$),不妨记为红色.考虑这5红点相关的矩形区域$5\times13$,这5点红色的边之外的12条平行边,每条最多仅有1个红点或没有红点,
------和下面没接起来,不晓得这个办法,可不可以---
-------
出现$3\times7$格点区域,只能涂2色.那么会出现同色矩形.7点的某边至少出现4点同色,记为蓝色.那么余下2边4点都最多出现1点蓝色,那么一定会有个绿色矩形  
出现  $4\times6$格点区域,只能涂2色,这块$4\times6$格点区域,可以不出现同色矩形
----------

与之垂直的另一条边也会出现至少5点同色，这样行列交叉部分出现$5\times5$区域，每行最多一个红点，每列最多一个蓝点，能否证明其中一定出现绿色矩形，可以证明成立，为方便说明，红点移动到对角线上。但1楼还是未得证，因为可能有一边5红4蓝4绿，另一垂直的一边也是如此.



---------------

abababa

我觉得单独考虑点不太好弄，我是这么想的，先考虑13列，每两列构成一个组，总共有$\binom{13}{2}=78$组，然后再考虑行，每行上的两个同色点构成一组，根据抽屉原理，$13\cdot13=169$个点用三种颜色染色，则至少存在$57$个点同色，就用这种颜色（不妨设为白色）的点，如果设第$i$行有$x_i$个白点，那么$13$行每行上的两个白点构成的组共有$\sum_{i=1}^{13}\binom{x_i}{2}$组，只要这个数大于$78$，根据抽屉原理，就有两个白点组位于同一个两列组上，这样就构成了一个白点矩形。所以只要证明当$x_1+x_2+\cdots+x_{13}\ge57$时有$\sum_{i=1}^{13}\binom{x_i}{2}>78$就行了，不等式我不行，不知道怎么证这个。

realnumber

abababa 发表于 2024-11-21 18:06
我觉得单独考虑点不太好弄，我是这么想的，先考虑13列，每两列构成一个组，总共有$\binom{13}{2}=78$组，然 ...

这个不等式好像可以这样做，先证明$m+n=C_0,C_0$为常数，此时在$\abs {m-n}$最小时，$C_m^2+C_n^2$最小，这样可得，(不妨设$x_1\ge x_2 \ge x_3 \ge ... \ge x_{13}$)在$x_1=...=x_5=5,x_6=...=x_{13}=4$,最小值98>78.

abababa

realnumber 发表于 2024-11-21 18:42
这个不等式好像可以这样做，先证明$m+n=C_0,C_0$为常数，此时在$\abs {m-n}$最小时，$C_m^2+C_n^2$最小， ...

两个变量的好弄，当$m+n=c_0$为定值时，$\binom{m}{2}+\binom{n}{2}=\frac{1}{2}(m^2-m+n^2-n)=m^2-c_0m+\frac{c_0^2-c_0}{2}$，用二次函数就得到取最小值的情况了。
怎么推广到多个变量的情况呢？

abababa

abababa 发表于 2024-11-21 19:12
两个变量的好弄，当$m+n=c_0$为定值时，$\binom{m}{2}+\binom{n}{2}=\frac{1}{2}(m^2-m+n^2-n)=m^2-c_0m+ ...

原来如此，根据点评的提示，不妨设$x_1\le x_2\le\cdots\le x_n$，假设存在$x_i\le x_j$使得当$x_j-x_i>1$时$\sum_{i=1}^{n}\binom{x_i}{2}$取得最小值，因为$x_i,x_j$是整数，因此$x_j-x_i\ge2$，设$x_j'=x_j-1, x_i'=x_i+1$，显然$x_1+\cdots+x_i'+\cdots+x_j'+\cdots+x_n$的值不变，用$x_i', x_j'$替换$x_i, x_j$，此时替换后得到的和$\sum_{k=1}^{n}\binom{x_k}{2}$与原和之差为
\[\left[\binom{x_i'}{2}+\binom{x_j'}{2}\right]-\left[\binom{x_i}{2}+\binom{x_j}{2}\right]\]
由于$x_i+x_j=x_i'+x_j'$，令$x_i+x_j = x_i'+x_j'=m$，则
\[\binom{x_i}{2}+\binom{x_j}{2}=\frac{1}{2}\big(x_i^2-x_i+x_j^2-x_j\big)=x_i^2-mx_i+\frac{m^2-m}{2}\]

显然当$x_i=\lfloor\frac{m}{2}\rfloor, x_j=\lceil\frac{m}{2}\rceil$时取得最小值，此时$x_j-x_i\le1$，因此当$\abs{x_i-x_j}\le1$时$\sum_{k=1}^{n}\binom{x_k}{2}$取得最小值，即$x_1,\cdots,x_{13}$中的任意两个之差都不大于$1$，于是必有$x_1=x_2=\cdots=x_a\le x_b=x_{b+1}=\cdots=x_n$。

当$x_1+x_2+\cdots+x_{13}=57$时，若存在$x_i\ge6$，则由$\abs{x_i-x_j}\le1$知每个$x_i\ge5$，于是$x_1+x_2+\cdots+x_{13}\ge5\cdot13>57$，矛盾，因此每个$x_i<6$，若存在$x_i\le3$，则由$\abs{x_i-x_j}\le1$知每个$x_i\le4$，于是$x_1+x_2+\cdots+x_{13}\le4\cdot13<57$，矛盾。于是每个$x_i$都满足$4\le x_i\le5$，设$x_1,x_2,\cdots,x_n$中有$m_1$个$4$和$m_2$个$5$，则有$m_1+m_2=13, 4m_1+5m_2=57$，于是$m_1=8, m_2=5$，所以$\sum_{k=1}^{n}\binom{x_k}{2}\ge8\cdot\binom{4}{2}+5\cdot\binom{5}{2}=98$。

还剩下一个是要证明$f(x_1,\cdots,x_n)=\sum_{i=1}^{n}\binom{x_i}{2}$的最小值是$x_1+x_2+\cdots+x_n$的增函数。

Aluminiumor

$$C_{n}^2=\frac{n(n-1)}{2}\geq\frac72n-8$$
当 $\sum x_i\geq57$ 时，$\sum C_{x_i}^2\geq\frac72\times57-13\times8=95.5>78$