Выбрана 1 задача 
Убрать все задачи
Эта старинная задача была известна еще в Древнем Риме.
Богатый сенатор, умирая, оставил жену в ожидании ребенка. После смерти сенатора выяснилось, что на свое имущество, равное 210 талантам, он составил следующее завещание: «В случае рождения сына отдать мальчику две трети состояния (т. е. 140 талантов), а остальную треть (т.е. 70 талантов) — матери; в случае же рождения дочери отдать девочке одну треть состояния (т. е. 70 талантов), а остальные две трети (т. е. 140 талантов) — матери».
У вдовы сенатора родились близнецы — мальчик и девочка. Такой возможности завещатель не предусмотрел. Как можно разделить имущество между тремя наследниками с наилучшим приближением к условию завещания?
Решение
|
|
 |
Условие
Натуральные числа a1, a2, ..., an таковы, что каждое не превышает своего номера (ak ≤ k) и сумма всех чисел – чётное число.
Доказать, что одна из сумм a1 ± a2 ± ... ± an равна нулю.
Решение
Докажем это утверждение индукцией по n.
База (n = 2) очевидна, так как единственный возможный набор a1 = a2 = 1.
Шаг индукции. Возьмём удовлетворяющий условию набор a1, a2, ..., an, an+1. Если an = an+1, то сумма a1 + ... + an–1 чётна; учитывая предположение индукции, заключаем, что одна из сумм a1 ± a2 ± ... ± an–1 + an − an+1 равна нулю.
Если же an ≠ an+1, заменим данный набор набором a1, a2,..., an–1, |an − an+1|. Для нового набора выполнены все условия: число |an − an+1| имеет
ту же чётность, что и an + an+1; из an ≠ an+1, 1 ≤ an ≤ n и 1 ≤ an+1 ≤ n + 1 вытекает 1 ≤ |an − an+1|. По предположению индукции одна из сумм
a1 ± a2 ± ... ± |an − an+1| равна нулю. Остаётся "раскрыть модуль": |an − an+1| = ± (an − an+1).
Замечания
В Задачнике "Кванта" задача дана в следующей формулировке.
Даны такие натуральные числа a1, a2, ..., an, ни одно из которых не превосходит своего номера, что сумма всех их чётна. Докажите, что сумма нескольких данных чисел равна сумме остальных.
