Переформулируем. Пусть дано 200 пар чисел: , причем каждое из чисел взято в отрезке . Требуется доказать, что найдутся две пары чисел и , такие что и (по сути, — координаты фишки на доске).
Доказательство:
Предположим обратное. Расставим пары по убыванию первого числа (то есть числа ). Внутри групп с одинаковым первым числом проведем обратную операцию: расставим числа по возрастанию второго числа (). Например, если размеры доски , а расставлено 7 фишек, то подошла бы следующая расстановка:
Понятно, что такая расстановка возможна. Действительно, если это не так, то найдется число , причем число стоит выше числа . Это противоречит предположению.
Пусть — число переходов числа на более низкое (в вышеприведенном примере таких переходов 3: с 4 на 3, с 3 на 2, с 2 на 1). Заметим, что числа могут повторяться не более одного раза. Внутри групп они строго возрастают. Поэтому последнее число не меньше . При этом, очевидно, . С другой стороны, переходов не больше чем (спуск от 100 до 1). Противоречие, которое завершает доказательство.
2 votes Thanks 0
Guerrino
при повороте лесенки меняется ведь и условие задачи
Guerrino
существование терминов правее, выше, левее, ниже предполагает пронумерованность, наверное. однако, автор вопроса, по его словам, в 5 классе, возможно там понимают по-другому
Answers & Comments
Переформулируем. Пусть дано 200 пар чисел:
, причем каждое из чисел взято в отрезке ![[1,\; 100]](https://tex.z-dn.net/?f=%5B1%2C%5C%3B%20100%5D "[1,\; 100]")
. Требуется доказать, что найдутся две пары чисел 
и 
, такие что 
и 
(по сути, 
— координаты фишки на доске).
Доказательство:
Предположим обратное. Расставим пары по убыванию первого числа (то есть числа
). Внутри групп с одинаковым первым числом проведем обратную операцию: расставим числа по возрастанию второго числа (
). Например, если размеры доски 
, а расставлено 7 фишек, то подошла бы следующая расстановка:
Понятно, что такая расстановка возможна. Действительно, если это не так, то найдется число
, причем число 
стоит выше числа 
. Это противоречит предположению.
Пусть
— число переходов числа 
на более низкое (в вышеприведенном примере таких переходов 3: с 4 на 3, с 3 на 2, с 2 на 1). Заметим, что числа 
могут повторяться не более одного раза. Внутри групп они строго возрастают. Поэтому последнее число не меньше 
. При этом, очевидно, 
. С другой стороны, переходов не больше чем 
(спуск от 100 до 1). Противоречие, которое завершает доказательство.