|
|
 |
Условие
Петя и Вася играют в такую игру. Сначала Петя задумывает некоторый многочлен 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 большой. Противоречие.
Замечания
9 баллов
