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

Ответы

891447819danilDanil 15.10.2020 16:06

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

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

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

ПОКАЗАТЬ ОТВЕТЫ

анора10 15.10.2020 16:06

Переформулируем. Пусть дано 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 — координаты фишки на доске).

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

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

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

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

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