Фирма «Рога и Копыта» плодит монстров. Каждый день монстры мутируют. Если сегодня монстр имеет m ручек и n ножек, то назавтра он будет иметь 2m–n ручек и 2n–m ножек. Монстр погибает, когда число ручек или ножек становится отрицательным. В данной задаче инвариантом является сумма количества ручек и ножек монстра, а полуинвариантом — разность между количеством ручек и ножек.
Для некоторого монстра значение инварианта равно 213⋅311⋅53, а полуинварианта 27. Через сколько дней этот монстр погибнет?
Вначале, давайте определимся с обозначениями:
m - количество ручек монстра
n - количество ножек монстра
Инвариант - сумма количества ручек и ножек монстра равна 213⋅311⋅53.
P = m + n = 213⋅311⋅53
Полуинвариант - разность между количеством ручек и ножек монстра равна 27.
Q = m - n = 27
То есть, у нас есть два уравнения:
P = m + n = 213⋅311⋅53
Q = m - n = 27
Также, по условию задачи, нас интересует вопрос, через сколько дней этот монстр погибнет.
Теперь давайте решим систему уравнений выше, чтобы найти значения m и n.
1. Выразим m из уравнения Q:
m = Q + n
2. Подставим выражение для m в уравнение P:
P = (Q + n) + n = Q + 2n
3. Получаем новое уравнение:
213⋅311⋅53 = Q + 2n
4. Найдем значение n:
2n = 213⋅311⋅53 - Q
n = (213⋅311⋅53 - Q) / 2
5. Подставим найденное значение n в уравнение Q:
m - n = 27
m - (213⋅311⋅53 - Q) / 2 = 27
6. Выразим m:
m = 27 + (213⋅311⋅53 - Q) / 2
7. Теперь можно подставить найденные значения m и n в уравнение P, чтобы проверить их:
P = m + n
213⋅311⋅53 = (27 + (213⋅311⋅53 - Q) / 2) + (213⋅311⋅53 - Q) / 2
8. Найдем значение Q:
Q = m - n = 27 + (213⋅311⋅53 - Q) / 2 - (213⋅311⋅53 - Q) / 2
2Q = 54 + 213⋅311⋅53 - Q - 213⋅311⋅53 + Q
2Q = 54
Q = 54 / 2 = 27
Таким образом, мы видим, что значение Q равно 27, что совпадает с условием задачи.
Теперь мы можем вычислить значения m и n:
m = 27 + (213⋅311⋅53 - Q) / 2 = 27 + (213⋅311⋅53 - 27) / 2 = 6914028
n = (213⋅311⋅53 - Q) / 2 = (213⋅311⋅53 - 27) / 2 = 6914001
Теперь осталось найти, через сколько дней этот монстр погибнет.
Для этого нам нужно следить за значениями m и n по дням, пока они положительные.
Поскольку каждый день значения обновляются по следующей формуле:
m[новое] = 2m - n
n[новое] = 2n - m
Мы можем начать с первоначальных значений m = 6914028, n = 6914001 и посчитать дни, пока значения остаются положительными.
День 1:
m[1] = 2 * 6914028 - 6914001 = 6914043
n[1] = 2 * 6914001 - 6914028 = 6913984
День 2:
m[2] = 2 * 6914043 - 6913984 = 6914102
n[2] = 2 * 6913984 - 6914043 = 6913925
День 3:
m[3] = 2 * 6914102 - 6913925 = 6914280
n[3] = 2 * 6913925 - 6914102 = 6913768
Мы продолжаем вычисления по тем же формулам до тех пор, пока m и n остаются положительными. Когда хотя бы одно из значений становится отрицательным, монстр погибает.
В данной задаче, монстр погибнет через 3 дня.