求具有下述性質(zhì)的最小正整數(shù)t

192557

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

198210

求具有下述性質(zhì)的最小正整數(shù)t：將100×100的方格紙的每個(gè)小方格染為某一種顏色，若每一種顏色的小方格數(shù)目均不超過104，則存在一個(gè)1×t或t×1的矩形，其中t個(gè)小方格含有至少三種不同顏色
將每個(gè)小方格視作1個(gè)點(diǎn)，原題等價(jià)于100*100的正方形點(diǎn)集，每個(gè)點(diǎn)染為一種顏色，每一種顏色的S點(diǎn)數(shù)≤104，存在水平或垂直總共t個(gè)點(diǎn)的線段，使線段至少有三種顏色的點(diǎn)。將同色點(diǎn)相連看做同色圖形，對(duì)于某一點(diǎn)集，該點(diǎn)集所有的該線同色圖形中，最短的橫截線段或最短的縱截線段即題設(shè)線段除首尾部分，加上首尾兩個(gè)異色點(diǎn)（+2）構(gòu)成線段并滿足至少有三種顏色的點(diǎn)。
要求存在線段長度t，使任一點(diǎn)集(截取不同顏色圖形的最短橫截線段或最短縱截線段)max+2≤t，令(截取不同顏色圖形的最短橫截線段或最短縱截線段)=L
①用同色封閉圖形填滿點(diǎn)集，則可見三角形、平行四邊形、梯形、其他規(guī)則不規(guī)則四邊形、五邊形、六邊形和其他多邊形的明顯缺點(diǎn)——其L明顯＜水平或豎直的矩形。故舍棄非矩形圖形。
用長方形/正方形水平豎直填滿點(diǎn)集則可見占用相同的S點(diǎn)數(shù)（對(duì)于矩形而言即面積），等面積長方形L總是短于正方形，故選用正方形。

做法m.當(dāng)用完全相同的正方形填滿點(diǎn)集，當(dāng)正方形數(shù)目越多（顏色種類越多），正方形越小，L越短。顏色種類有極限≥97種，正方形≥97個(gè)，欲使L最大，則100*100的正方形點(diǎn)集所需最少完全相同正方形為100個(gè)。故此時(shí)L最大=10，t≥12
當(dāng)不用完全相同的正方形填滿點(diǎn)集，則點(diǎn)集顯然存在正方形小于做法m的完全相同正方形，此時(shí)L顯然小于做法m。舍棄。

②當(dāng)各種顏色的部分同色點(diǎn)圍成同色封閉圖形，由①易得②圍成的同色封閉圖形L必然＜①中相似但更大的同色封閉圖形L
③當(dāng)同色點(diǎn)完全不成團(tuán)分布，由②同理③形成的L必然＜②圍成的同色封閉圖形的L。
綜上，t≥12，tmin=12

95583

這不是去年八一數(shù)學(xué)競賽的題嘛