求具有下述性质的最小正整数t

192557 · 发表于 2023-1-13 13:30:57

求具有下述性质的最小正整数t：将100×100的方格纸的每个小方格染为某一种颜色，若每一种颜色的小方格数目均不超过104，则存在一个1×t或t×1的矩形，其中t个小方格含有至少三种不同颜色

198210 · 发表于 2023-1-13 17:31:11

求具有下述性质的最小正整数t：将100×100的方格纸的每个小方格染为某一种颜色，若每一种颜色的小方格数目均不超过104，则存在一个1×t或t×1的矩形，其中t个小方格含有至少三种不同颜色
将每个小方格视作1个点，原题等价于100*100的正方形点集，每个点染为一种颜色，每一种颜色的S点数≤104，存在水平或垂直总共t个点的线段，使线段至少有三种颜色的点。将同色点相连看做同色图形，对于某一点集，该点集所有的该线同色图形中，最短的横截线段或最短的纵截线段即题设线段除首尾部分，加上首尾两个异色点（+2）构成线段并满足至少有三种颜色的点。
要求存在线段长度t，使任一点集(截取不同颜色图形的最短横截线段或最短纵截线段)max+2≤t，令(截取不同颜色图形的最短横截线段或最短纵截线段)=L
①用同色封闭图形填满点集，则可见三角形、平行四边形、梯形、其他规则不规则四边形、五边形、六边形和其他多边形的明显缺点——其L明显＜水平或竖直的矩形。故舍弃非矩形图形。
用长方形/正方形水平竖直填满点集则可见占用相同的S点数（对于矩形而言即面积），等面积长方形L总是短于正方形，故选用正方形。

做法m.当用完全相同的正方形填满点集，当正方形数目越多（颜色种类越多），正方形越小，L越短。颜色种类有极限≥97种，正方形≥97个，欲使L最大，则100*100的正方形点集所需最少完全相同正方形为100个。故此时L最大=10，t≥12
当不用完全相同的正方形填满点集，则点集显然存在正方形小于做法m的完全相同正方形，此时L显然小于做法m。舍弃。

②当各种颜色的部分同色点围成同色封闭图形，由①易得②围成的同色封闭图形L必然＜①中相似但更大的同色封闭图形L
③当同色点完全不成团分布，由②同理③形成的L必然＜②围成的同色封闭图形的L。
综上，t≥12，tmin=12

95583 · 发表于 2023-1-13 19:37:03

这不是去年八一数学竞赛的题嘛

[数学趣题] 求具有下述性质的最小正整数t