Однажды рыцарь встретил алчного волшебника. Волшебник сказал: «Раз в день я готов удвоить количество твоих золотых монет, но за это ты должен будешь в этот день заплатить мне монет». После этого рыцарь три дня подряд ходил к волшебнику, и в итоге остался без денег вовсе! Сколько монет было у рыцаря первоначально?

Решение по шагам (для понятности, с общим параметром оплаты) 1) Обозначим: - m – фиксированная сумма монет, которую волшебник требует каждый день. - x0 – исходное число монет у рыцаря. - x1, x2, x3 – количество монет после 1-го, 2-го и 3-го дня соответственно. Каждый день процесс следующий: удвоить текущее число монет и вычесть m. Тогда рекуррентное соотношение: x_k = 2 x_{k-1} - m. 2) Пусть после третьего дня монет не осталось: x3 = 0. Разбираем обратным путём: - Из x3 = 0 = 2 x2 - m получаем x2 = m/2. - Из x2 = m/2 = 2 x1 - m получаем x1 = (m/2 + m)/2 = 3m/4. - Из x1 = 3m/4 = 2 x0 - m получаем x0 = (3m/4 + m)/2 = 7m/8. Итак, исходное количество монет равно x0 = 7m/8. 3) Особенности целочисленности: Чтобы x0 и все последующие значения были целыми, m должно быть кратно 8. В частности, если взять минимально возможно целое m = 8, то: - x0 = 7, x1 = 3m/4 = 6, x2 = m/2 = 4, x3 = 0. 4) Проверка (пример с m = 8): - Начинаем с 7 монет. - День 1: удвоить 7 → 14, заплатить 8 → 6. - День 2: удвоить 6 → 12, заплатить 8 → 4. - День 3: удвоить 4 → 8, заплатить 8 → 0. После третьего дня монеты кончились — всё верно. Ответ: Если оплата за каждый день равна 8 монетам, то исходное число монет у рыцаря было 7. В общем виде при фиксированной дневной оплате m исходное количество монет равно 7m/8 (и целочисленно это возможно когда m кратно 8).