Положим тогда Достаточно показать, что все числа  – целые. Заметим, что и то есть Значит, при

Так как одно из чисел делится на то при число  – целое.

Достаточно доказать утверждение: многочлен делится на Действительно, после деления (например, столбиком), в частном получится многочлен с целыми коэффициентами, и тогда равенство многочленов влечет равенство из которого следует утверждение задачи, поскольку — целое число.

Для доказательства утверждения сделаем замену положим и докажем, что делится на т.е. что последние два коэффициента многочлена равны

Свободный член многочлена равен Поскольку в многочлене коэффициент при равен коэффициент при многочлена равен Из условий следует, что удвоенный коэффициент при равен Тем самым, задача решена.

Пусть — центр вписанной окружности и , тогда образуют прямую, поскольку — середина дуги , кроме того, тогда — середина дуги . Заметим, что , откуда вписан. Аналогично и вписан . Далее если , то картинка симметрична и образуют прямоугольник, иначе , запишем степень точки

Пользуемся вписанностью , и , в итоге вписан из равенства первого и последнего.

Мы будем называть многочлен вида просто многочленом, а график такого многочлена — просто графиком. Мы будем пользоваться следующей известной леммой.

Лемма. Через любые три точки с разными абсциссами проходит ровно один график.

Доказательство. Один график, проходящий через эти точки, найдётся всегда. С другой стороны, если через три точки проходят графики двух разных многочленов и то разность имеет три корня что невозможно.

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

Рассмотрим ситуацию после ходов. Назовём пару графиков подходящей, если объединение этих графиков содержит все отмеченные Петей точки.

Покажем, что Мы будем считать, что Петя изначально не рисует никаких графиков, а просто отмечает некоторые точки с данными абсциссами. Покажем, как ему действовать, чтобы после ходов нашлись две подходящих пары графиков такие, что все графика различны; это и будет означать, что Вася не смог добиться требуемого, ибо Петя мог нарисовать любую из этих пар.

Будем обозначать точку, появляющуюся после -го хода, через На первых двух ходах Петя выбирает На следующих ходах Петя отметит точки и на графике многочлена и точки и — на графике многочлена Седьмым ходом Петя выбирает точку , не лежащую ни на одном из графиков, проходящем через какие-то три точки из и Тогда существуют графики и проходящие через тройки точек и согласно нашему выбору, эти графики различны и отличаются от и Значит, пары и — подходящие, и все эти четыре графика различны, то есть Вася не сможет добиться требуемого.

Покажем, как Васе добиться требуемого за ходов. На первых ходах он называет произвольных различных чисел.

Назовём график подозрительным, если он проходит хотя бы через три точки, отмеченных Петей на этих ходах. Назовём число плохим, если два различных подозрительных графика имеют общую точку с абсциссой Существует лишь конечное количество подозрительных графиков и, следовательно, лишь конечное количество плохих чисел.

На восьмом ходу Вася называет любое неплохое число После того, как Петя отметит восьмую точку, возможны два случая.

Случай Существует график многочлена содержащий пять из восьми отмеченных точек. Три из этих точек лежат на одном из Петиных графиков; по лемме, этот график совпадает с Значит, Васе достаточно назвать многочлен

Случай Такого графика нет. Это значит, что на каждом из Петиных графиков лежит ровно по отмеченных точки; поэтому оба этих графика подозрительны. Докажем, что существует единственная пара подозрительных графиков, содержащих в совокупности все отмеченных точек; тогда Васе достаточно назвать любой из соответствующих многочленов. Пусть и — две таких пары, причём и содержат Согласно выбору числа это может произойти лишь при Но тогда каждый из графиков и проходит через отмеченных точки, не лежащих на и они совпадают согласно лемме. Значит, и наши пары совпадают.

Решение будет состоять из трёх шагов

Докажем следующую лемму. Лемма. Пусть при некоторых натуральных квадратный трёхчлен имеет целые корни. Тогда и делятся на

Доказательство. По теореме Виета и являются целыми числами. Лемма доказана.

Предположим, что натуральные числа (при некотором целом неотрицательном k) нужным образом расставлены в качестве коэффициентов данных квадратных трёхчленов Для определённости пусть Тогда откуда и т.д., Тогда из леммы следует, что минимальное из чисел не меньше, чем а максимальное (назовём его ) — не меньше, чем Но должно быть среди чисел Получаем Отсюда и, значит, Кроме того, откуда сразу следует, что при

Среди подряд идущих чисел менее чётных. С другой стороны, зная, что пробегают числа получим оценку снизу на количество чётных чисел среди всех коэффициентов. Заметим, что в каждой из троек хотя бы одно чётное число, иначе значение трёхчлена в любой целой точке будет нечётно, в частности, такой трёхчлен не может иметь целых корней. Если же чётно (количество соответствующих троек равно ), то и в силу леммы, тоже чётные, значит, в такой тройке все три коэффициента чётные. Итого Сравнивая верхнюю и нижнюю оценки, имеем откуда Противоречие.

Пусть — один из данных прямоугольников, а — центр окружности, на которой лежат восемь вершин из условия задачи. Тогда лежит на серединном перпендикуляре к отрезку Но он совпадает с серединным перпендикуляром к отрезку Поскольку лежит на нём, имеем Аналогично доказываем, что и Тогда равноудалена от всех вершин четырехугольника значит, вписан в окружность с центром что и требовалось доказать.

Положим Предположим противное: для каждого из чисел существует разложение где Заметим, что каждое из чисел и строго больше а также что иначе Значит, каждое из чисел набора лежит в множестве из чисел Таким образом, в этом наборе найдутся два равных числа. Пусть каждое из этих двух чисел равно

Пусть эти равные числа имеют равные индексы в наборе, то есть при некотором Тогда поэтому число делится на простое Так как это может быть лишь при Тогда соответствующее значение равно что при больше, чем Противоречие (так как ).

В противном случае существуют индексы такие, что для которых числа и делятся на Тогда и также делится на Из взаимной простоты чисел и получаем, что делится на а это невозможно, так как

Таким образом, в каждом случае получено противоречие и, следовательно, указанное в условии задачи число всегда найдётся.

Нас просят доказать неравенство для всех натуральных По условию Перепишем корни в степени и приступим к доказательству:

Сократим на

Заметим, что:

Сократим на величину которая является положительной, поскольку

Осталось заметить, что и потому что и Следовательно, их сумма больше

Пусть Заметим, что при всех Значит, поскольку имеет ненулевой корень, он имеет и отрицательный корень, откуда

Далее, поскольку имеем

Так как степень многочлена чётна, а старший коэффициент положителен, при достаточно больших по модулю отрицательных он принимает положительные значения. Теперь из полученного выше соотношения следует, что у этого многочлена есть корень на интервале Значит, и

Итак, мы получили, что при всех Это означает, что последовательность — убывающая.

Разобьём доску на квадратов Покажем, что в каждом квадрате может стоять не более гепардов, не бьющих друг друга — отсюда будет следовать, что общее число гепардов не может превосходить

Рассмотрим произвольный квадрат размера и произвольного гепарда в нём. Гепард бьёт все клетки квадрата, кроме клеток, лежащих с ним в одной строке или в одном столбце. Если один из остальных гепардов в квадрате стоит в одной строке с а ещё один, — в одном столбце с то и стоят в разных строках и столбцах и, следовательно, бьют друг друга; это невозможно. В противном случае, без ограничения общности, все гепарды в квадрате стоят в одной строке с то есть их не больше

Таким образом, мы доказали, что общее число гепардов не может превосходить осталось привести пример, когда эта оценка достигается. Пронумеруем столбцы доски подряд числами Расставим гепардов на все клетки столбцов, номера которых делятся на Этих гепардов будет и они не будут бить друг друга.

Рассмотрим момент после третьего хода (когда выписаны три числа). Если к этому моменту никто еще не выиграл, то следующим ходом Вася выигрывает — ему достаточно найти два выписанных числа одной чётности и выписать своим ходом их среднее арифметическое (оно является целым числом).

Кроме того, заметим, что если три целых числа из множества образуют арифметическую прогрессию, то её разность не больше (иначе разность между наибольшим и наименьшим числами будет не менее что невозможно).

Теперь опишем выигрышную стратегию Васи.

Пусть первым ходом Петя выписал число . Предположим, что Тогда Вася выписывает то из чисел или , чётность которого отлична от чётности числа (обозначим это число через ). После этого хода выписано два числа разной чётности; значит, они не могут быть первым и третьим членом прогрессии из целых чисел. А поскольку они также не могут быть соседними членами прогрессии. Тем самым, Петя не сможет выиграть третьим ходом. Но в этом случае, как мы видели ранее, следующим ходом Вася выиграет.

Если же то Вася отвечает, выписывая то из чисел и которое по чётности отличается от Дальнейшие рассуждения аналогичны первому случаю.

Заменим в условии сто на и докажем утверждение индукцией по Обозначим число, записанное на -й минуте через Так как оно имеет хотя бы один простой делитель, то есть база доказана.

Переход. Заметим, что То есть делится на все простые делители (по предположению их хотя бы ), а также оно делится на простой делитель отличный от простых делителей поскольку Получили требуемое.

Достаточно показать, что хотя бы одно из двух чисел и больше Действительно, если, например, то делится на и значит,  – составное число. Из условия следует, что значит, делится на Но тогда, если то и что противоречит условию.

Заметим, что Приведём пример Пашиных чисел, при которых требуемое выполняется. Пусть среди его чисел двоек, чисел, равных а остальные — единицы.

Чтобы добиться требуемого за хода, Паша выбирает коробок, в которые он всегда кладёт по два камня — через хода в них окажется камней. Остальные коробки он разбивает на группы по коробок; на -м ходу он положит по камня во все коробки -й группы и по одному камню — в коробки остальных групп. Тогда через хода в каждой коробке каждой группы будет по камней, то есть во всех коробках будет поровну камней.

Осталось доказать, что за меньшее число ходов требуемое невыполнимо. Пусть Паша сделал ходов. Тогда в какую-то коробку попало камня на одном ходу и в ней будет не меньше, чем камней. С другой стороны, поскольку в какую-то коробку ни на одном из ходов не попадёт камня, то есть в ней будет не больше камней. Поскольку имеем а значит, в коробке меньше камней, чем в Таким образом, Паша ещё не добился требуемого.

Если то просто сделаем и получим корень Пусть теперь тогда Сделаем и на это уйдёт не более рублей. В нашем распоряжении осталось хотя бы рублей, покажем, что их достаточно, чтобы увеличить или уменьшить до ближайшего квадрата. а значит оно располагается между квадратами, расстояние между которыми не превосходит Таким образом, нам хватит рублей, чтобы сделать квадратом и получить трёхчлен который имеет целые корни, что и требовалось.

По теореме Виета равен модулю суммы всевозможных произведений чисел из наборов а равен модулю произведения всех корней. Покажем, что не делится на Для этого заметим, что По условию все корни взаимно просты, отсюда и следует, что не делится ни на один из корней, но тогда он не имеет общих множителей с что и требовалось.

Уравнение относительно является квадратным, а значит, для наличия действительного корня необходимо и достаточно, чтобы дискриминант, равный , был неотрицательным, то есть . Если скобочка положительна, то при условие не выполняется. Если отрицательно, то при снова не выполняется. Если же , то есть , то неравенство справедливо при любом .

Понятно, что приведённый трёхчлен, проходящий через , имеет вид . Тогда их сумма равна

Старший коэффициент равен количеству трёхчленов, которые имеют корни в указанных точках. Покажем, что дискриминант положителен:

Достаточно доказать, что:

После раскрытия скобочек и привидения подобных получим:

Последнее неравенство верно, так как переменные различны.

Переформулируем задачу в непрерывном виде , тогда нашлось такое (, что , то есть

Может ли быть так, что ? Нет, поскольку в многоугольнике хотя бы 3 стороны и выполнено неравенство ломаной — если вычесть из обеих частей , то остальные стороны будут образовывать ломаную, соединяющую начало и конец стороны, что соответствует длине . Но тогда , далее , но подставляя это аналогично (*), получим , что выполнено из , что и требовалось.

Пусть приписали число , тогда , то есть или . Произведение неотрицательно, при этом , однако при равенство невозможно, то есть возможно только , для , которое подходит в силу равносильности преобразований.