МОШ 2025, 11 класс, задача 2
Кусок сыра массой кг разрезали на кусков массами меньше г. Оказалось, что их нельзя разбить на две кучки так, чтобы масса каждой кучки была не меньше г, но не больше г (кучка может состоять из одного или нескольких кусков). Докажите, что найдутся три таких куска, что суммарная масса любых двух из них больше г.
(Д. Горяшин)
Ответ
Решение. Первый способ. Пусть — массы кусков в граммах. Упорядочим их по величине: . Тогда , иначе кучка из одного куска массой и кучка из всех остальных кусков противоречат условию.
Теперь достаточно показать, что . Предположим противное: пусть , тогда (иначе снова есть две кучки, противоречащие условию: кучка из кусков массами , и кучка из всех остальных кусков). Поэтому . Будем теперь класть на весы по одному куски массами именно в этом порядке. Начальная масса кучки на весах будет равна , а конечная — , так как . Поскольку масса каждого очередного куска меньше г, в некоторый момент на весах окажется кучка, масса которой будет не меньше г, но не больше г, что противоречит условию.
Второй способ. Из условия следует, что масса каждого куска меньше г. При любом разбиении кусков на две кучки масса одной из них будет меньше г, а масса другой — больше г. В первом случае назовём кучку лёгкой, а во втором — тяжёлой. Лёгкой кучке соответствует тяжёлая (из остальных кусков), и наоборот. Также назовём произвольный кусок большим, если при добавлении его к некоторой лёгкой кучке она становится тяжёлой, а в противном случае назовём кусок маленьким (при добавлении его к любой лёгкой кучке она остаётся лёгкой). Масса любого большого куска больше г.
Рассмотрим кучку, состоящую из всех маленьких кусков. Она лёгкая, поэтому ей соответствует тяжёлая кучка из остальных кусков. В этой тяжёлой кучке не менее двух кусков, причём они все большие. Выберем один из этих кусков и переложим к кучке из маленьких кусков. Полученная кучка также лёгкая, так как её можно получить, добавляя последовательно к этому большому куску все маленькие куски. Ей снова соответствует тяжёлая кучка, также состоящая из не менее двух кусков.
Таким образом, найдены три больших куска, любые два из которых образуют тяжёлую кучку, т. е. имеют суммарную массу больше г.
Замечание. Такая тройка больших кусков единственна. Действительно, если бы было хотя бы больших куска, то составленная из них тяжёлая кучка имела бы массу более г. Кроме того, при сужении промежутка г, в который не должны попадать массы кучек при произвольном разбиении, утверждение задачи перестаёт быть верным, что показывает пример разрезания на куска массами , , и г.