Question

на доске 100 на 100 стоит 200 фишек. Докажите что найдутся две фишки одна из которых строго правее и строго выше другой​

Answer 1

Допустим таких конфигураций не существует.

Тогда не существует и аналогичных конфигураций "строго левее и строго выше" и так далее, потому что если бы они были, мы бы могли их поворотами доски или отражениями привести к конфигурации "строго правее и строго выше"

Значит координаты любых двух фишек на нашей доске не могут быть обе различными. Значит фишки максимум занимают одну вертикаль и одну горизонталь, но так можно разложить лишь 199 фишек. А у нас 200. Значит, мы получаем противоречие исходному предположению.

Answer 2

Переформулируем. Пусть дано 200 пар чисел: $(x_{1},y_{1}), (x_{2},y_{2}),\;...,\; (x_{200},y_{200})$, причем каждое из чисел взято в отрезке $[1,\; 100]$. Требуется доказать, что найдутся две пары чисел $(x_{i},y_{i})$ и $(x_{j},y_{j})$, такие что $x_{i}>x_{j}$ и $y_{i}>y_{j}$ (по сути, $x,y$ — координаты фишки на доске).

Доказательство:

Предположим обратное. Расставим пары по убыванию первого числа (то есть числа $x$). Внутри групп с одинаковым первым числом проведем обратную операцию: расставим числа по возрастанию второго числа ($y$). Например, если размеры доски $4\times 4$, а расставлено 7 фишек, то подошла бы следующая расстановка:

$(4,1)\\(4,2)\\(3,2)\\(3,3)\\(2,3)\\(2,4)\\(1,4)$

Понятно, что такая расстановка возможна. Действительно, если это не так, то найдется число $y_{i}$, причем число $y_{j}$ стоит выше числа $y_{i}$. Это противоречит предположению.

Пусть $k$ — число переходов числа $x$ на более низкое (в вышеприведенном примере таких переходов 3: с 4 на 3, с 3 на 2, с 2 на 1). Заметим, что числа $y$ могут повторяться не более одного раза. Внутри групп они строго возрастают. Поэтому последнее число не меньше $200-k$. При этом, очевидно, $200-k\leq 100 \Leftrightarrow k\geq 100$. С другой стороны, переходов не больше чем $100-1=99$ (спуск от 100 до 1). Противоречие, которое завершает доказательство.

Answer 3

Это задача, которая может быть решена с использованием принципа Дирихле (также известного как принцип ящика или принцип дополнения). Принцип Дирихле гласит, что если n+1 или более объектов распределены в n "ящиках" (или категориях), то по крайней мере в одном из "ящиков" будет содержаться более одного объекта.

В данной задаче "ящики" можно представить как клетки на доске 100x100, а "объекты" - как фишки. Если на доске 100 на 100 стоит 200 фишек, и мы рассматриваем каждую клетку как "ящик", то у нас есть 100 * 100 = 10 000 "ящиков" и 200 "объектов", которые мы должны распределить по этим "ящикам".

Согласно принципу Дирихле, если у нас есть 200 объектов и 10 000 "ящиков", то по крайней мере в одной из клеток (ящиков) должно быть более одной фишки. Это означает, что существует как минимум одна пара фишек, одна из которых строго правее и строго выше другой, так как каждая клетка на доске имеет координаты (x, y), и мы можем рассматривать их в качестве точек на плоскости, где "правее" означает большую координату x, а "выше" - большую координату y.