Таблицы Брадиса

Решения задач из предыдущих выпусков

Решения задач из предыдущих выпусков

Математическое просвещение - Винберг Э. Б

9.   Докажите, что при игре «Жизнь» а) в квадрате 2010 х 2010; б) на бесконечной плоскости найдётся конфигурация без прообраза.[63]

(Фольклор)

10. Докажите, что существует такое х < 4 ■ 99! , что х(х + 1) делится на 100!.       (С. В. Конягин)

11.   Известно, что если зафиксировать одну переменную, то функция /(ж, у) по другой будет многочленом. Верно ли, что она будет сама многочленом от двух переменных? (Б. П. Панеях)

12.   По некоторым рёбрам клеток плоской решётки проведены перего­родки. Пьяница с равной вероятностью идёт из квадрата, где он находится, в любой соседний квадрат, куда он может пройти. Дока­жите, что он с вероятностью 1 вернётся в исходную точку.

(А. Я. Канель, М. Б. Скопенков)

Решения задач из предыдущих выпусков

5.6.   УСЛОВИЕ. а) Все коэффициенты многочлена Р(ж) целые и среди них есть нечётные. Докажите, что найдётся многочлен ф(ж), имеющий ровно два нечётных коэффициента и делящийся на Р(ж).

б) Существует ли многочлен Р(ж, у) с целыми коэффициентами такой, что всякий многочлен Я(ж, у), делящийся на Р(ж, у), имеет более миллиона нечётных коэффициентов?

Решение. а) Поскольку нас интересует только чётность коэффициен­тов, будем рассматривать многочлены над Z2. Наша цель — показать, что при некоторых Пі = П2 многочлен ж”1 — ж”2 делится на ^(ж).

Рассмотрим остатки от деления на ф(ж) многочленов вида ж”. Они представляют собой многочлены степени не выше deg(Q) — 1, и количество различных остатков не превосходит

2^«(х). Значит, при каких-то Пі = П2 остатки повторятся и многочлен ж”1 — ж”2 будет искомым.

б) Ответ: да, существует!

Рассмотрим многочлены с коэффициентами по модулю 2. Если член ж”ут входит с ненулевым коэффициентом, то отметим точку с координа­тами (п, т). Выпуклая оболочка множества отмеченных точек есть мно­гоугольник Ньютона многочлена Р(ж, у).