求具有下述性質的最小正整數t

192557

求具有下述性質的最小正整數t：將100×100的方格紙的每個小方格染為某一種顏色，若每一種顏色的小方格數目均不超過104，則存在一個1×t或t×1的矩形，其中t個小方格含有至少三種不同顏色

198210

求具有下述性質的最小正整數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

這不是去年八一數學競賽的題嘛