Имеется несколько камней, массы которых — различные натуральные числа.
а) Можно ли разложить 10 камней с массами 1, 2, 3, ..., 10 по шести кучкам так, чтобы вес каждой кучки не превосходил 10?
б) Можно ли разложить камни массами 370, 372, 374, ..., 468 на семь кучек так, чтобы вес каждой кучки не превосходил 3000?
в) Дополнительно известно, что общая сумма масс камней равна 4000, а масса каждой кучки, как и каждого камня, не превосходит 100. Какое минимальное количество таких кучек придется задействовать, чтобы гарантированно распределить данные камни?
а) Да. Например,
| 10 | 1 и 9 | 2 и 8 | 3 и 7 | 4 и 6 | 5 |
б) Всего имеется 50 камней. При любом распределении 50 камней по семи кучкам, всегда найдётся такая кучка, в которой окажутся минимум 8 камней. Минимальная масса восьми камней равна
что противоречит условию. Значит, 50 таких камней нельзя разложить на семь кучек, чтобы вес каждой кучки не превосходил 3000.
в) Покажем, что любой набор камней, удовлетворяющий условиям задачи, можно разложить не более чем на 51 кучку. Разложим сто различных камней следующим образом: 50, 49 и 51, 48 и 52, ..., 1 и 99, 100. Получаем 51 кучку. Общая масса всех камней при этом равна 
Теперь, убирая любые камни, суммарная масса которых равна 1050, оставляем не более 51 кучки.
Заметим, что 
Таким образом, сумма чисел 50, 51, 52, ..., 100 не превосходит 4000. При этом никакие два из соответствующих камней не могут оказаться в одной кучке, в противном случае, масса этой кучки будет превосходить 100. Значит, чтобы гарантированно разложить любой набор камней, количество кучек не может быть меньше 51.
Набор камней с массами 31, 47, 48, 49, ..., 99, 100 в соответствии с условиями задачи может быть разложен на 51 кучку следующим образом : 31 и 50, 49 и 51, 48 и 52, 47 и 53, 54, 55, ..., 99, 100.
Ответ: а) да, б) нет, в) 51.