|
|
 |
Условие
День в Анчурии может быть либо ясным, когда весь день солнце, либо дождливым, когда весь день льет дождь. И если сегодня день не такой, как вчера, то анчурийцы говорят, что сегодня погода изменилась. Однажды анчурийские ученые установили, что 1 января день всегда ясный, а каждый следующий день в январе будет ясным, только если ровно год назад в этот день погода изменилась. В 2015 году январь в Анчурии был весьма разнообразным: то солнце, то дожди. В каком году погода в январе впервые будет меняться ровно так же, как в январе 2015 года?
Решение
Поставим в соответствие январю каждого года упорядоченный набор
(a1, a2, ..., a31) из нулей и единиц следующим образом: если k-го января день был ясным, то ak = 1, иначе ak = 0. По условию, 1 января день всегда ясный, поэтому a1 = 1. Сопоставим набору погоды текущего года
(1, a2, ..., a31) многочлен
P(x) = 1 + a2x + ... + a31x30. Тогда набору следующего года будет соответствовать остаток P1(x) от деления многочлена
(1 + x)P(x) на x31 (здесь и далее все коэффициенты многочленов рассматриваются по модулю 2), а через k лет погоду описывает многочлен Pk(x), являющийся остатком от деления (1 + x)kP(x) на x31. Таким образом, задача сводится к тому, чтобы найти наименьшее k, для которого Pk(x) = P(x), то есть ((1 + x)k – 1)P(x) делится на x31.
Нетрудно показать по индукции, что (1 + x)2m = 1 + x2m. Если 2m < 31, то ((1 + x)2m – 1)P(x) = x2mP(x) не делится на x31, так как свободный коэффициент многочлена P(x) равен единице. А ((1 + x)32 – 1)P(x) = x32P(x) уже делится на x31, то есть число 32 является периодом. Остаётся заметить, что он будет наименьшим, так как наименьший период является делителем любого другого, а меньшие степени двойки периодами не являются.
Ответ
В 2047 году.
Замечания
Рассмотренный многочлен P(x) представляет собой пример производящей функции. Такая функция однозначно определяется данной последовательностью, и наоборот. Идея о том, что исследовать свойства последовательностей можно, изучая свойства их производящих функций, широко применяется в различных областях математики.
