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

Решение по шагам (для понятности, с общим параметром оплаты)

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).