Олимпиадная задача о делении кучек Кости: индукция и доказательство, 10-11 класс
Задача
У Кости была кучка из 100 камешков. Каждым ходом он делил какую-то из кучек на две меньших, пока у него в итоге не оказалось
100 кучек по одному камешку. Докажите, что
а) в какой-то момент в каких-то 30 кучках было в сумме ровно 60 камешков;
б) в какой-то момент в каких-то 20 кучках было в сумме ровно 60 камешков;
в) Костя мог действовать так, чтобы ни в какой момент не нашлось 19 кучек, в которых в сумме ровно 60 камешков.
Решение
Будем называть кучки с 1, 2, 3, 4 камешками соответственно единичка, двойка, тройка, четвёрка. а) Дождёмся, когда станет 70 кучек. Cреди них найдётся 40 единичек (в противном случае камешков не менее 2·31 + 39 = 101). Если их отбросить, останется 30 кучек, содержащих 60 камней. б) Докажем по индукции, что при a = 2, 3, ..., 20 в некоторый момент найдётся 60 + 2a камней в 20 + a кучках.
База (a = 20). После 40-го хода есть 100 камней в 40 кучках.
Шаг индукции. Пусть a > 2 и имеется 60 + 2a камней в 20 + a кучках. Среди них найдётся двойка или две единички, поскольку
3(19 + a) + 1 > 60 + 2a. Отбросим их и во втором случае дождёмся, когда Костя разобьёт одну из оставшихся кучек на две. В результате a уменьшится
на 1.
При a = 2 имеем 64 камня в 22 кучках.
Покажем, что мы можем набрать сейчас четыре камня двумя или более кучками. Пусть это не так. Если есть единичка, то камней хотя бы
1 + 1 + 1 + 4·19 > 64, если нет, то хотя бы 2 + 3·21 > 64. Противоречие.
Отбросив эти четыре камня, мы получим 60 камней в 20 или менее кучках. Осталось дождаться, когда этих кучек станет ровно 20. в) Пусть Костя отделяет от самой большой кучи по тройке, пока не останется четвёрка. До сих пор была одна куча, где число камешков не делилось на 3. Сумма в любых 19 кучках с её участием не делилась на 3, а без неё не превосходила 57, то есть ни так ни этак не равнялась 60. Затем Костя делит четвёрку на две двойки. Теперь и в дальнейшем каждая кучка не больше тройки, поэтому в любых 19 кучках не больше 57 камней.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь