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_{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). Противоречие, которое завершает доказательство.