Переформулируем. Пусть дано 200 пар чисел: , причем каждое из чисел взято в отрезке . Требуется доказать, что найдутся две пары чисел и , такие что и (по сути, — координаты фишки на доске).
Доказательство:
Предположим обратное. Расставим пары по убыванию первого числа (то есть числа ). Внутри групп с одинаковым первым числом проведем обратную операцию: расставим числа по возрастанию второго числа (). Например, если размеры доски , а расставлено 7 фишек, то подошла бы следующая расстановка:
Понятно, что такая расстановка возможна. Действительно, если это не так, то найдется число , причем число стоит выше числа . Это противоречит предположению.
Пусть — число переходов числа на более низкое (в вышеприведенном примере таких переходов 3: с 4 на 3, с 3 на 2, с 2 на 1). Заметим, что числа могут повторяться не более одного раза. Внутри групп они строго возрастают. Поэтому последнее число не меньше . При этом, очевидно, . С другой стороны, переходов не больше чем (спуск от 100 до 1). Противоречие, которое завершает доказательство.
пусть сосуд А-12л сосуд В -7л
Пошаговое объяснение:
>А (наливаем в А) итог 12:0
А>В (переливаем из А в В) итог 5:7
В> (выливаем из В) итог 5:0
А>В (переливаем из А в В) итог 0:5
>А (наливаем в А) итог 12:5
А>В (переливаем из А в В) итог 10:7
В> (выливаем из В) итог 10:0
А>В (переливаем из А в В) итог 3:7
В> (выливаем из В) итог 3:0
А>В (переливаем из А в В) итог 0:3
>А (наливаем в А) итог 12:3
А>В (переливаем из А в В) итог 8:7
В> (выливаем из В) итог 8:0
А>В (переливаем из А в В) итог 1:7
получили 1 л в А!!
Переформулируем. Пусть дано 200 пар чисел:
, причем каждое из чисел взято в отрезке ![[1,\; 100]](/tpl/images/1360/3515/a94ff.png)
. Требуется доказать, что найдутся две пары чисел 
и 
, такие что 
и 
(по сути, 
— координаты фишки на доске).
Доказательство:
Предположим обратное. Расставим пары по убыванию первого числа (то есть числа
). Внутри групп с одинаковым первым числом проведем обратную операцию: расставим числа по возрастанию второго числа (
). Например, если размеры доски 
, а расставлено 7 фишек, то подошла бы следующая расстановка:
Понятно, что такая расстановка возможна. Действительно, если это не так, то найдется число
, причем число 
стоит выше числа 
. Это противоречит предположению.
Пусть
— число переходов числа 
на более низкое (в вышеприведенном примере таких переходов 3: с 4 на 3, с 3 на 2, с 2 на 1). Заметим, что числа 
могут повторяться не более одного раза. Внутри групп они строго возрастают. Поэтому последнее число не меньше 
. При этом, очевидно, 
. С другой стороны, переходов не больше чем 
(спуск от 100 до 1). Противоречие, которое завершает доказательство.