4色の交差点が4色で存在することを証明する $100×100$ グリッド[複製]
A $100×100$グリッドは4色で着色されています。すべての行と列に各色の正確に25ブロックがあります。4つの交差するブロックすべてが異なる色になるように、2つの行と列の間に交差が存在することを証明します。
私は不変性を使用してこれを証明しようとしています。しかし、私はどのように進めるかわかりません。また、これが正しいアプローチであるかどうかもわかりませんので、アイデアをいただければ幸いです:)
回答
あることに注意してください $\binom{4}{2} \cdot 25^2$ 各行に異なる色のペアがあるので、 $100 \cdot \binom{4}{2} \cdot 25^2$合計で同じ行にある異なる色のペア。さて、それに注意してください$100 \cdot \binom{4}{2} \cdot 25^2 > 75 \cdot \binom{100}{2}$。したがって、一般化された鳩の巣原理により、次の2つの列があります。$>75$同じ行にある異なる色のペア。同じ行に76組の異なる色があるとします。色の名前はセットからのものだと言う$\{0,1,2,3\}$。さて、主張が真実でない場合は、$\{0,1\}$、 $\{0,2\}$、 $\{0,3\}$ または $\{0,1\}$、 $\{0,2\}$、 $\{1,2\}$ これらをカバーするために使用できる可能なペアは何ですか $2$列（WLOG）。最初のケースは、制限があるため、明らかに不可能です。$25$ 色ごとに、2番目のケースは不可能です。 $3$ 色は合計をカバーするのに十分ではありません $76 \cdot 2=152$ブロック。したがって、主張は真実です。
編集：「同じ行にある異なる色のペア」の意味が理解できない場合は、@ Mikeからの以下のコメントを参照してください。