ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 65210
Темы:    [ Рекуррентные соотношения (прочее) ]
[ Периодичность и непериодичность ]
[ Двоичная система счисления ]
[ Производящие функции ]
Сложность: 4+
Классы: 10,11
В корзину
Прислать комментарий

Условие

День в Анчурии может быть либо ясным, когда весь день солнце, либо дождливым, когда весь день льет дождь. И если сегодня день не такой, как вчера, то анчурийцы говорят, что сегодня погода изменилась. Однажды анчурийские ученые установили, что 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) представляет собой пример производящей функции. Такая функция однозначно определяется данной последовательностью, и наоборот. Идея о том, что исследовать свойства последовательностей можно, изучая свойства их производящих функций, широко применяется в различных областях математики.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Год 2015
Номер 78
класс
Класс 11
задача
Номер 4

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .