Докажите, что существует четырехцветное пересечение в четырехцветном $100×100$ сетка [дубликат]

Dec 27 2020

А $100×100$сетка раскрашена в четыре цвета. В каждой строке и столбце ровно 25 блоков каждого цвета. Докажите, что между двумя строками и столбцами существует такое пересечение, что все четыре пересекающихся блока имеют разные цвета.

Я пытаюсь доказать это, используя инвариантность. Но я не знаю, что делать дальше. Я также не знаю, правильный ли это подход, поэтому приветствуются любые идеи :)

Ответы

2 Tan Dec 27 2020 at 05:57

Обратите внимание, что есть $\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}$. Итак, по обобщенному принципу ячеек, есть два столбца с$>75$пары разного цвета, находящиеся в одном ряду. Скажем, в одном ряду 76 пар разных цветов. Скажите, что названия цветов взяты из набора$\{0,1,2,3\}$. Теперь, если утверждение не соответствует действительности, то либо$\{0,1\}$, $\{0,2\}$, $\{0,3\}$ или $\{0,1\}$, $\{0,2\}$, $\{1,2\}$ возможные пары, которые мы можем использовать для покрытия этих $2$столбцы (WLOG). Первый случай явно невозможен, поскольку у нас есть предел$25$ для каждого цвета, и второй случай невозможен, так как $3$ цветов недостаточно, чтобы покрыть в общей сложности $76 \cdot 2=152$блоки. Итак, утверждение верно.

Изменить: если вы не можете понять, что я имею в виду под «парами разных цветов, которые находятся в одной строке», см. Комментарии ниже от @Mike.