Beweisen Sie, dass es einen vierfarbigen Schnittpunkt in einem vierfarbigen gibt $100×100$ Gitter [Duplikat]

Dec 27 2020

EIN $100×100$Gitter ist mit vier Farben gefärbt. In jeder Zeile und Spalte befinden sich genau 25 Blöcke jeder Farbe. Beweisen Sie, dass es einen Schnittpunkt zwischen zwei Zeilen und Spalten gibt, sodass alle vier sich überschneidenden Blöcke unterschiedliche Farben haben.

Ich versuche dies mit Invarianz zu beweisen. Aber ich weiß nicht, wie ich vorgehen soll. Ich weiß auch nicht, ob dies der richtige Ansatz ist, daher werden Ideen geschätzt :)

Antworten

2 Tan Dec 27 2020 at 05:57

Beachten Sie, dass es gibt $\binom{4}{2} \cdot 25^2$ Paare verschiedener Farben in jeder Reihe, also gibt es $100 \cdot \binom{4}{2} \cdot 25^2$Paare verschiedener Farben, die sich insgesamt in derselben Reihe befinden. Beachten Sie das jetzt$100 \cdot \binom{4}{2} \cdot 25^2 > 75 \cdot \binom{100}{2}$. Nach dem verallgemeinerten Pigeonhole-Prinzip gibt es also zwei Spalten mit$>75$Paare verschiedener Farben, die sich in derselben Reihe befinden. Angenommen, es gibt 76 Paare verschiedener Farben, die sich in derselben Reihe befinden. Angenommen, die Namen der Farben stammen aus dem Set$\{0,1,2,3\}$. Wenn die Behauptung nicht wahr ist, dann auch nicht$\{0,1\}$, $\{0,2\}$, $\{0,3\}$ oder $\{0,1\}$, $\{0,2\}$, $\{1,2\}$ sind die möglichen Paare, mit denen wir diese abdecken können $2$Spalten (WLOG). Der erste Fall ist eindeutig unmöglich, da wir eine Grenze von haben$25$ für jede Farbe, und der zweite Fall ist seitdem unmöglich $3$ Farben reichen nicht aus, um insgesamt zu decken $76 \cdot 2=152$Blöcke. Die Behauptung ist also wahr.

Bearbeiten: Wenn Sie nicht verstehen können, was ich unter "Paaren verschiedener Farben in derselben Zeile" verstehe, lesen Sie die folgenden Kommentare von @Mike.