ID: 00013700
На доске написано n единиц подряд. Между некоторыми из них расставляют знаки «+» и считают получившуюся сумму. Например, если было написано 10 единиц, то можно получить сумму 136: 1 + 1 + 111 + 11 + 11 + 1 = 136
a) Можно ли получить сумму 132, если n = 60?
б) Можно ли получить сумму 132, если n = 80?
в) Для скольких значений n можно получить сумму 132?
Источник: ФИПИ
Что происходит: написано n единиц подряд, между некоторыми ставят плюсы и складывают. Плюсы разбивают единицы на блоки; блок из k единиц — это число \underbrace{1\dots 1}_{k}.
Ключевое наблюдение: «значение блока минус его длина» всегда кратно 9. Для 1 это 0, для 11 это 11-2=9, для 111 это 111-3=108 и так далее — всегда делится на 9. Значит и «сумма минус общее число единиц» кратна 9. Отсюда 132-n делится на 9, то есть n\equiv 132\equiv 6\pmod 9.
Пункт а). n=60? Проверяем: 60 даёт остаток 6 при делении на 9 — годится. Построим: 8 блоков «11» (это 16 единиц, дают 88) и 44 отдельные единицы; сумма 88+44=132, единиц 16+44=60. Значит — да.
Пункт б). n=80? Но 80 даёт остаток 8 при делении на 9, а нужно 6. Значит из 80 единиц сумму 132 не получить — нет.
Пункт в). Сколько всего значений n подходит? Запишем сумму через число блоков «11» (a штук) и «111» (b штук): 132-n=9a+108b, при этом отдельных единиц n-2a-3b\geqslant 0. Если b\geqslant 2, то блок 111 дважды — это уже 222\gt 132, не годится. Перебирая допустимые a и b, получаем ровно 14 значений n: это 15,24,33,\dots,132 (все дают остаток 6 по модулю 9 и реализуемы). Подходят 14 значений n.
а) да; б) нет; в) 14