На прямоугольном экране размером m×n, разбитом на единичные клетки, светятся более  (m – 1)(n – 1)  клеток. Если в каком-либо квадрате 2×2 не светятся три клетки, то через некоторое время погаснет и четвёртая. Докажите, что тем не менее на экране всегда будет светиться хотя бы одна клетка.

   Решение

Темы:    [ Китайская теорема об остатках ] [ Многочлены (прочее) ]

Сложность: 4 Классы: 9,10,11 Название задачи: Китайская теорема об остатках для многочленов.

Прислать комментарий

Условие

Пусть m₁(x), ..., m_n(x) – попарно взаимно простые многочлены, a₁(x), ..., a_n(x) – произвольные многочлены.
Докажите, что существует ровно один такой многочлен p(x), что
    p(x) ≡ a₁(x) (mod m₁(x)),
      ...
    p(x) ≡ a_n(x) (mod m_n(x))
и  deg p(x) < deg m₁(x) + ... + deg m_n(x).

Подсказка

Докажите утверждение индукцией по n.

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