Назад
Задача

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

Решение

  Пусть Вася назвал три числа  a < b < c.  Вася мог получить соответственно ответы 0, 1, 2, Если у Пети оказался многочлен  P(x) = (c – a)x² + a,  то уравнение  P(x) = a  имеет одно решение  x = 0,  уравнение  P(x) = c  – два решения  x = ±1,  а уравнение  P(x) = b  не имеет решений. Поэтому Петя даст ответы 1, 0, 2, то есть Васе 3 рублей не хватит.   Лемма. Если многочлен 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 большой. Противоречие.

Ответ

Ответ задачи отсутствует

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет