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

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

Условие

Автор: Mudgal A.

Петя и Вася играют в такую игру. Сначала Петя задумывает некоторый многочлен P(x) с целыми коэффициентами. Далее делается несколько ходов. За ход Вася платит Пете рубль и называет любое целое число a по своему выбору, которое он ещё не называл, а Петя в ответ говорит, сколько решений в целых числах имеет уравнение  P(x) = a.  Вася выигрывает, как только Петя два раза (не обязательно подряд) назвал одно и то же число. Какого наименьшего числа рублей хватит Васе, чтобы гарантированно выиграть?


Решение

  Трёх рублей не хватит, поскольку, называя произвольные различные числа a, b и c, Вася мог получить соответственно ответы 0, 1, 2, если у Пети оказался многочлен  P(x) = (c – b)x2n + b.  Ответ 0 возможен, так как число  r = a–b/c–b  отлично от 0 и 1, поэтому при некотором n уравнение  x2n = r  не имеет решений в целых числах.

  Лемма. Если многочлен Q(x) с целыми коэффициентами имеет больше двух различных целых корней, то многочлены  Q(x) ± 1  не имеют целых корней.
  Доказательство.  Q(x) = (x – a)(x – b)(x – c)R(x),  где R(x) – многочлен с целыми коэффициентами. Предположим, что при каком-то целом x это выражение равно ±1. Тогда каждая из скобок равна ±1. Значит, какие-то две скобки равны, то есть равны какие-то два из корней a, b и c. Противоречие.

  Покажем, как выиграть, имея 4 рубля. Будем говорить, что ответы, кроме 0, 1 и 2, – большие.
  Первый способ. Вася называет числа 5 и 8. Если на одно из них, например на 8, окажется большой ответ, то Вася называет 7 и 9. Согласно лемме, ответами будут нули.
  Если оба ответа будут маленькие, Вася называет 6 и 7. Если на одно из этих чисел будет большой ответ, то вокруг него ответы нулевые. В противном случае, будет четыре ответа трёх видов, что гарантирует совпадение.
  Второй способ. Вася называет три последовательных числа, а четвёртое – рядом с тем крайним из них, на которое был дан наибольший ответ. Пусть на числа, скажем, 5, 6, 7, 8 были даны ответы p, q, r, s соответственно. Можно считать, что ответ s – последний, то есть  p ≤ r.
  Предположим, что все эти ответы различны. Тогда среди них есть большой, и он стоит с краю, поскольку, согласно лемме, вокруг него ответы нулевые. Это не s, так как  r > 0.  Значит, это p, но тогда и ответ r большой. Противоречие.

Замечания

9 баллов

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

олимпиада
Название Турнир городов
Турнир
Дата 2016/17
Номер 38
вариант
Вариант осенний тур, сложный вариант, 10-11 класс
задача
Номер 6

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

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