Регион 10 класс

Пример. Фишку 50 последовательно 99 раз меняем со следующей против часовой стрелки. Получаем требуемое расположение.

Есть несколько способов доказать оценку, ниже мы приведём два из них.

Первый способ. Предположим, что при некотором требуемая расстановка получена.

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

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

Тем самым, мы получаем, что фишки 1 и 100 совершают одинаковый сдвиг по и против часовой стрелки, поэтому они остаются на своих позициях. Противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

Второй способ. Будем считать сдвиги фишек относительно их начальной позиции, причём сдвиг по часовой стрелке будет считаться с плюсом, против часовой — с минусом. Тогда при обмене двух фишек к сдвигу одной из них прибавляется +1, а другой — Значит, в результате проведённых операций общая сумма сдвигов будет равна 0.

Рассуждаем от противного: пусть при каждая фишка в итоге сдвинута на одну позицию по часовой стрелке, т.е. её сдвиг оказался равным (здесь — целое «число оборотов» по часовой стрелке, в частности при фишка сделала оборотов против часовой стрелки). Тогда суммарный сдвиг всех 100 фишек равен

Поскольку он должен равняться 0, имеем

Поскольку фишки с номерами и где не могли меняться местами, поэтому их сдвиги в любой момент заведомо отличаются меньше чем на 100, значит количества оборотов и равны при Отсюда имеем …, Тогда сумма

— чётна, а значит не равна Противоречие.

Первое решение. Без ограничения общности будем считать, что точка лежит на отрезке и Пусть — центр окружности Пусть точка симметрична относительно серединного перпендикуляра к отрезку (см. первый рисунок). Из симметрии

Окружность с центром и радиусом пересекает окружность в точках, симметричных относительно прямой то есть точки и симметричны относительно Аналогично, точки и симметричны относительно прямой

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

Второе решение. Без ограничения общности будем считать, что точка лежит на отрезке Пусть — центр окружности Заметим, что Поскольку

то точки и лежат по одну сторону от прямой (см. второй рисунок). Треугольники и равны по трем сторонам, треугольники и — тоже.

Тогда

(Если луч не лежит внутри угла то луч лежит внутри угла а значит и внутри угла В этом случае либо

либо

в обоих случаях получаем противоречие с равенством треугольников и Аналогично, луч лежит внутри угла )

Поэтому треугольники и равны по двум сторонам и углу между ними, откуда

Приведём одну из возможных выигрышных стратегий для Пети. Он всё время будет делать ходы, параллельные одной из диагоналей доски (назовём её главной).

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

В результате сдвигов и бывшие вертикали, и бывшие диагонали, параллельные главной, стали наклонными рядами. При этом “вертикали” одной лесенки симметричны “диагоналям” другой. Это значит, что на каждый ход Васи Петя может ответить симметричным ходом в другую лесенку (два таких ответа показаны на рис. ).

Тогда после каждого Петиного хода ситуация на «сдвинутой» картинке будет оставаться симметричной, а значит, Петя всегда сможет сходит согласно описанной стратегии. Так как игра закончится (не более чем за ходов), в некоторый момент Васе будет некуда ходить, и Петя выиграет.

1) Упорядочим длины палочек

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Сложив данные в условии задачи неравенства, получим: Преобразуем данные неравенства к виду: и и перемножим (это можно, так как их правые части положительны). Получим:

Раскрывая скобки, имеем:

откуда

или

Так как то значит

Следовательно,

Предположим противное, и множество конечно. Тогда среди всех чисел множества выберем число которое делится на максимальную степень тройки, пусть скажем, делится на но не делится на Если условие выполняется, то для некоторых Левая часть этого равенства делится на Но тогда, поскольку не делится на число должно делиться на что противоречит выбору

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

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сократим на

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

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

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

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

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

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

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

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

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

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

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

Пусть Тогда на доске присутствует дробь

что и требовалось

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

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

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

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

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

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

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

Заметим, что

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