Если на столе лежит несколько кучек камней, считается, что на столе много камней, если можно найти 50 кучек и пронумеровать их числами от 1 до 50 так, что в первой кучке есть хотя бы один камень, во второй — хотя бы два камня, . . . , в пятидесятой — хотя бы пятьдесят камней. Пусть исходно на столе лежат 100 кучек по 100 камней в каждой. Найдите наибольшее n 6 10 000 такое, что после удаления из исходных кучек любых n камней на столе все равно останется много камней. (При удалении камней кучка не распадается на несколько.)
1 Ответ
Решение.
Если удалить полностью 51 кучку, то, очевидно, не останется много камней. Значит, искомое значение n меньше 5100. (Альтернативно, можно удалить из всех кучек по 51 камню.) Осталось показать, что при удалении любых n = 5099 камней останется много камней. Пусть в кучках осталось a1, a2, . . . , a100 камней соответственно; можно считать, что 0 => a1 => a 2 => … 6 a100 => 100. Покажем, что ai+50 > i при i = 1, 2, . . 50,
то есть кучки с номерами от 51 до 100 удовлетворяют требованиям. Пусть это не так, то есть ai+50 6 i−1. при некотором i 6 50. Это значит, что каждая из первых i + 50 кучек содержит не более i−1 камня, то есть из неё удалено хотя бы 101−i камней. Поэтому общее количество удалённых камней не меньше, чем (i + 50) (101 − i) = 5100 − (i − 1) (i − 50) > 5100. Противоречие.
Ответ. n = 5099.