Закл (финал) 11 класс
Ошибка.
Попробуйте повторить позже
У школьников есть стопка из карточки, которые пронумерованы числами от до Первый школьник перемешивает стопку, затем берет сверху из получившейся стопки по одной карточке, и при каждом взятии карточки (в том числе при первом) записывает на доску среднее арифметическое чисел на всех взятых им на данный момент карточках. Так он записывает чисел, а когда в стопке остается одна карточка, он возвращает карточки в стопку, и далее все то же самое, начиная с перемешивания стопки, проделывает второй школьник, потом третий, и т.д. Докажите, что среди выписанных на доске чисел найдутся два одинаковых.
Подсказка 1
Попробуйте посмотреть, какие множества чисел могут получаться у школьников на 1 шаге, на 2 шаге, на 100 шаге?
Подсказка 2
Попробуйте в явном виде найти все возможные значения, находящиеся в этих множествах. Как найти одинаковые среди них?
Подсказка 3
Рассмотрите первое, второе и сотое множества, а именно их объединение. Сколько в нëм чисел?
На -м шаге у каждого из человек было выписано одно из чисел множества
На -м шаге — одно из чисел множества
На -м шаге выписано одно из чисел множества
где — сумма всех чисел (а вычитается — число на оставшейся в конце карточке).
Видим, что так что Далее, но числа принадлежат значит,
Итак, мы показали, что чисел, выписанных на -м, -м и -м шагах, могут принимать не более различных значений. Следовательно, какие-то два из них равны.
Ошибка.
Попробуйте повторить позже
На плоскости фиксирован остроугольный треугольник с наибольшей стороной Пусть — произвольный диаметр его описанной окружности, причём точка лежит на меньшей дуге а точка — на меньшей дуге Точки и — основания перпендикуляров, опущенных из точки на прямую из точки на прямую и из точки на прямую Докажите, что центр описанной окружности треугольника лежит на фиксированной окружности (не зависящей от выбора точек и ).
Пусть описанная окружность треугольника является единичной с центром в и треугольник положительно ориентирован. Заметим, что тогда Обозначим угол через Введем обозначение Тогда откуда Вычисляем
Обозначим через центр описанной окружности треугольника Заметим, что Тогда
Получаем, что ориентированный угол равен То есть откуда находим
То есть координата центра описанной окружности треугольника имеет вид где не зависят от а бегает по единичной окружности. Тогда понятно, что и бегает по окружности, полученной из единичной умножением на и сдвигом на
Ошибка.
Попробуйте повторить позже
В треугольнике биссектрисы и пересекаются в точке Прямая, проходящая через точку параллельно пересекает лучи и в точках и соответственно. Точка — центр описанной окружности треугольника точка — центр описанной окружности треугольника Докажите, что
Пусть описанная окружность треугольника является единичной с центром в нуле. Обозначим через комплексное число, отвечающее повороту на против часовой стрелки, через — отвечающее повороту на по часовой стрелке. Тогда центр вписанной окружности имеет координату Обозначим середины дуг и через и соответственно. Тогда . Найдем координату точки Во-первых откуда При этом лежит на хорде откуда Решая полученную систему, находим Аналогично Заметим, что Тогда ориентированный угол откуда Итого, имеет комплексную координату
Аналогично Тогда
Последнее выражение очевидно вещественное, что и требовалось доказать.
Ошибка.
Попробуйте повторить позже
Пусть — ненулевой многочлен с неотрицательными коэффициентами такой, что функция — нечетная. Может ли оказаться, что для различных точек на графике выполняются условия: касательная к графику в точке проходит через точку касательная в точке проходит через точку касательная в точке — через точку
Первое решение. Покажем, что при данных условиях на многочлен каждая следующая точка касания лежит по другую сторону от оси чем предыдущая.
Пусть — данный многочлен, — его производная. Пусть — это -я точка касания, а -я. Тогда касательная в точке имеет уравнение Значит, откуда Разделив это равенство на и перенеся все слагаемые в правую часть, получим при четной степени выражение:
Пусть и одного знака (считаем, что с любым числом одного знака). Если то выражение в скобках положительно, если же то оно отрицательно. Такие же знаки будут иметь выражения при остальных степенях: Значит, если и одного знака, то равенство невозможно. Итак, любые две последовательные точки касания должны находиться по разные стороны от оси И в силу нечетности касательная в точке не может пройти через точку
______________________________________________________________________________________________________________________________________________________
Второе решение. Заметим, что функция при и нечетном выпукла на и вогнута на Многочлен представляется в виде суммы нескольких функций такого вида, потому что является нечетной функцией, а его коэффициенты неотрицательные. Тогда функция также выпукла на и вогнута на Это означает, что касательная в точке графика с положительной абсциссой вторично не пересекает график в точках с неотрицательной абсциссой, и наоборот. Кроме того, касательная к графику в нуле не имеет с ним больше общих точек. Это означает, что абсциссы точек отличны от нуля, а их знаки чередуются. Тогда у точек и абсциссы одного знака, поэтому касательная в точке не проходит через точку
Не может
Ошибка.
Попробуйте повторить позже
При некоторых натуральных число оказалось представлено в виде суммы слагаемого, каждое из которых равно целой неотрицательной степени числа а также в виде суммы слагаемого, каждое из которых равно целой неотрицательной степени числа При каком наибольшем это могло произойти (хоть при каком-то )?
Пусть Поскольку любая степень числа дает остаток от деления на то сумма таких степеней дает остаток от деления на С другой стороны, степени числа дают лишь остатки или от деления на поэтому сумма степени числа может давать остаток от деления на только если все слагаемые равны Но тогда противоречие. Значит,
Для есть пример:
Ошибка.
Попробуйте повторить позже
(a) Даны монет попарно различных масс и чашечных весов, При каждом взвешивании разрешается выбрать какие-то одни весы, положить на их чаши по одной монете, посмотреть на показания весов и затем снять монеты обратно. Какие-то одни из весов (неизвестно, какие) испорчены и могут выдавать случайным образом как правильный, так и неправильный результат. За какое наименьшее количество взвешиваний можно заведомо найти самую тяжелую монету?
(a) Докажем сначала, что за взвешивание можно найти самую тяжёлую монету. Более точно, мы докажем по индукции по что самую тяжёлую из данных монет можно определить за взвешивание, имея трое весов, одни из которых, возможно, испорчены.
Если то взвесим данные две монеты по очереди на трёх разных весах. Если при одном из взвешиваний весы оказались в равновесии, то эти весы испорчены, значит, мы можем определить более тяжёлую монету по показаниям любых из остальных весов. Если равновесия ни разу не было, то какая-то из монет перевесит хотя бы два раза — она и есть более тяжёлая, так как неверный результат могут давать только одни весы. Это даёт базу индукции.
Пусть теперь Выберем две монеты и двое весов и сравним за первые два взвешивания эти монеты друг с другом на первых и на вторых весах. Возможны два случая:
Оба раза перевешивала одна и та же из двух монет; назовём её монетой а вторую из них — монетой Так как хотя бы одни из двух весов правильные, то монета действительно тяжелее монеты Значит, не самая тяжёлая. Задача сводится к тому, чтобы определить самую тяжёлую из монеты: монеты и монет, не участвовавших в первых двух взвешиваниях. По предположению индукции мы можем сделать это за взвешивания. Вместе с первыми двумя взвешиваниями получаем взвешивания.
Либо одно из первых двух взвешиваний дало равновесия, либо результаты первых двух взвешиваний противоречат друг другу: один раз перевесила одна монета, а другой — другая. Значит, одни из двух использованных весов точно испорчены. Возьмём третьи весы. Тогда они обязательно правильные. Используя из, мы легко можем определить самую тяжёлую монету за взвешивание: сравниваем первую монету со второй, более тяжёлую из них — с третьей, более тяжёлую из них с четвёртой и так далее до последней. Вместе с первыми двумя взвешиваниями получаем (так как ) взвешивание.
Покажем теперь, что менее, чем за взвешивание, заведомо определить самую тяжёлую монету нельзя. Достаточно показать, что её нельзя определить ровно за взвешивания, так как можно добавить произвольные взвешивания и игнорировать их результаты. Предположим противное: имеется алгоритм действий, позволяющий определить самую тяжёлую монету за взвешивания.
Пронумеруем монеты числами Сделаем первые взвешивания согласно алгоритму. Предположим, что в каждом из них перевешивала монета с большим номером. Согласно принципу Дирихле, среди монет с номерами найдётся такая, которая за произведённые взвешиваний "проигрывала"(оказалась более лёгкой) не более одного раза; обозначим номер этой монеты через Конечно же, монета с номером ни разу не "проигрывала". Покажем, что такие результаты взвешиваний возможны. Действительно, такое могло произойти по крайней мере в следующих ситуациях.
(A) Монеты упорядочены по возрастанию масс и все весы (в том числе, испорченные) показывали правильные результаты во всех взвешиваниях.
(Б) Монеты упорядочены по возрастанию масс, за исключением монеты номер которая самая тяжёлая. При этом те весы, на которых монета номер "проиграла испорчены, и в этом взвешивании показали неверный результат, а в остальных взвешиваниях все весы показывали верные результаты.
Рассмотрим два случая:
В последнем, м взвешивании, не участвует монета с номером Предположим, что опять перевесила монета с большим номером. Тогда каждая из ситуаций (А) и (Б) по-прежнему возможна.
В последнем взвешивании участвует монета с номером Предположим, что она перевесила. Тогда, с одной стороны, возможно, что имеет место ситуация (А), и последнее взвешивание выполнялось на испорченных весах. С другой стороны, возможно, что имеет место ситуация (Б), и в последнем взвешивании весы показали правильный результат.
Итак, каким бы ни было одно оставшееся взвешивание, его результат может быть таков, что после него каждая из ситуаций (А) и (Б) будет по-прежнему возможной. Тогда каждая из монет и может быть самой тяжёлой, то есть нам не удалось определить самую тяжёлую монету.
_________________________________________________________________________________________________________________________________________________________________________________
(b) Очевидно, что точно хватит, поскольку мы можем провести алгоритм из предыдущего пункта. В качестве оценки рассмотрим конкретный набор монет с массами Очевидно, что чаша с самой тяжёлой монетой в этом случае всегда будет перевешивать (). В таком случае, можно сделать такую же оценку, как в предыдущем пункте, если понимать слово “проигрывала” как “не была самой тяжёлой” (потому что если монета оказалось на чаше, которая не перевесила, то она точно не самая тяжёлая). То есть чтобы точно определить самую тяжёлую, нам понадобится хотя бы взвешивание.
Ошибка.
Попробуйте повторить позже
Дано натуральное число На клетчатой плоскости изначально отмечено клеток. Назовем крестом клетки множество всех клеток, находящихся в одной вертикали или горизонтали с Если в кресте неотмеченной клетки отмечено хотя бы других клеток, то клетку также можно отметить. Оказалось, что цепочкой таких действий можно отметить любую клетку плоскости. При каком наименьшем это могло случиться?
Обозначим через ответ в задаче; положим Докажем сначала, что
После отмечания исходных клеток можно отметить хотя бы одну клетку ; это значит, что либо в столбце, либо в строке этой клетки уже отмечено других клеток - пусть для определённости в строке
Мысленно отметим все клетки строки Ясно, что любую клетку по-прежнему можно отметить. Удалим из клетчатой плоскости строку и сдвинем вместе две получившиеся полуплоскости так, чтобы снова получилась клетчатая плоскость. Теперь мы можем отметить любую клетку этой новой плоскости, отмечая на каждом шагу клетку, в кресте которой уже есть не менее отмеченных клеток (поскольку из этого креста удалена одна клетка строки ). Следовательно, изначально на этой плоскости должно было быть отмечено не менее клеток. Значит, на исходной плоскости сначала должно быть хотя бы отмеченных клеток не из ; отсюда и следует
Поскольку из доказанного неравенства (*) следует, что
Осталось показать, как отметить клеток так, чтобы затем можно было отметить любую другую клетку плоскости. Покажем по индукции, что подходит пример, показанный на рисунке, состоящий из двух «лесенок» высот и ; нетрудно понять, что в нём как раз клеток. При утверждение очевидно: при одной отмеченной клетке можно отметить любую клетку в её кресте, а затем и любую клетку вообще.
Для перехода индукции заметим, что можно последовательно отметить клетки После этого в строке, в которой они стоят, окажется клеток, и в ней уже можно будет отметить любую клетку. Значит, можно, вычеркнув эту строку, уменьшить значение на и применить предположение индукции в оставшейся плоскости.
Ошибка.
Попробуйте повторить позже
Многочлен таков, что многочлены и строго монотонны на всей вещественной оси. Докажите, что тоже строго монотонен на всей вещественной оси.
Первое решение. Предположим, что многочлен не является монотонным. Тогда найдутся такие что а значит, и то есть не монотонен.
_________________________________________________________________________________________________________________________________________________________________________________
Второе решение. Так как многочлен монотонен, то он обязан иметь нечётную степень, а тогда он принимает все вещественные значения.
Пусть тогда найдутся такие числа и что Так как старший коэффициент многочлена всегда положителен, то этот многочлен возрастает, поэтому
Если старший коэффициент многочлена положителен, то многочлен возрастает; отсюда получаем, что то есть для любых Если же старший коэффициент отрицателен, то, аналогично, откуда для любых
Ошибка.
Попробуйте повторить позже
Определим последовательность формулой Докажите, что существует такое натуральное число что среди любых подряд идущих членов последовательности есть такой, десятичная запись которого содержит цифру (Как обычно, через обозначается наибольшее целое число, не превосходящее )
Обозначим Напомним, что частный случай неравенства Бернулли (при ) можно переписать в виде (при ).
_________________________________________________________________________________________________________________________________________________________________________________
Лемма 1. Для любого натурального п верны неравенства
Доказательство. Правое неравенство сразу следует из упомянутого неравенства Бернулли. Для доказательства левого, применяя то же неравенство, получаем
откуда
______________________________________________________________________________________________________________________________________________________
Лемма 2. Для любого натурального п верны неравенства
Доказательство. Поскольку достаточно доказать, что или
Применяя лемму получаем
что доказывает левое неравенство. Аналогично, для правого имеем
______________________________________________________________________________________________________________________________________________________
Перейдём к решению задачи. Покажем, что число подходит. Для этого достаточно доказать, что при любом натуральном число с пятёркой в десятичной записи найдётся даже среди чисел Поскольку найдётся натуральное такое, что Покажем, что даже среди -х с конца цифр чисел встретится пятёрка, откуда и будет следовать требуемое.
По лемме при каждом имеем это означает, что -я цифра при переходе от к либо не изменяется, либо увеличивается на (при этом переходит в ). С другой стороны, по той же лемме
это означает, что за таких переходов -я цифра обязана хотя бы раз изменить своё значение (на следующее по циклу). Значит, за переходов она примет все возможных значений, в частности, побывает и пятёркой.
Ошибка.
Попробуйте повторить позже
Даны положительные числа , где . Докажите, что
По неравенству о средних
В условии требуют доказать, что левая часть этого неравенства не меньше 1, поэтому достаточно доказать, что правая часть (оценка снизу) не меньше 1, то есть
В силу положительности чисел неравенство эквивалентно возведённому в квадрат
Здесь последовательная пара скобок слева не меньше соответствующей скобки справа. Например,
поскольку
Аналогично с остальными скобками.
Ошибка.
Попробуйте повторить позже
Исходно на доске написаны многочлены и Если на доске написаны многочлены и разрешается дописать на неё многочлены и где — произвольная (не обязательно целая) константа. Может ли на доске после нескольких операций появиться многочлен вида (при натуральном )?
Подсказка
Понять, какие многочлены получатся очень тяжело, но легче посмотреть на их производные. Поймите, что будет общего у всех производных полученных функций.
Рассмотрим производные изначальных многочленов: Обе производные имеют нули в
Теперь докажем следующую лемму:
_________________________________________________________________________________________________________________________________________________________________________________
Лемма. Имеется множество функций, каждая из которых имеет ноль производной в заданной точке. Тогда, любая новая функция, полученная способом, описанным в задаче, из функций множества, тоже будет иметь корень производной в этой точке.
Доказательство леммы. Пусть новая функция была получена из функций и по одному из способов, упомянутых в условии. По условию леммы имеется такое фиксированное что
1) Значит, — ноль функции
2) Значит, — ноль функции
3) Значит, — ноль функции
4) Значит, — ноль функции
______________________________________________________________________________________________________________________________________________________
Лемма доказана. Вернемся к исходной задаче. По лемме мы получаем, что каждая новая функция на доске будет иметь ноль производной в точке Но рассмотрим функцию, которую мы хотим получить: Заметим, что у ее производной не имеется нуля в точке Значит, по лемме мы не можем получить такую функцию.
Нет, не может
Ошибка.
Попробуйте повторить позже
В окружность вписан остроугольный треугольник в котором Пусть и – середины меньшей и большей дуги окружности соответственно. Пусть – основание перпендикуляра, опущенного из точки на отрезок Докажите, что окружность, описанная около треугольника делит отрезок пополам.
Сделаем симметрию относительно биссектрисы угла и инверсию с таким радиусом, чтобы и где штрихом обозначаем образ точки под действием композиции преобразований. Точка является точкой пересечения внешней биссектрисы угла и описанной окружности значит точка переходит в точку пересечения внешней биссектрисы и прямой Точка переходит в основание биссектрисы угла Точка переходит в точку на биссектрисе, которая находится в два раза дальше от чем Из подобия треугольников и и образ можно определить как точку пересечения перпендикуляра к в точке и
Требовалось доказать, что лежат на одной окружности. После инверсии и симметрии остается доказать, что лежат на одной прямой. Заметим, что Достаточно показать, что Тогда треугольники и подобны, и значит прямые и совпадают. Но ясно что
Внутренняя и внешняя биссектрисы делят противоположную сторону в соотношении равном отношению прилежащих сторон. Значит
Это эквивалентно тому, что мы хотели доказать:
Ошибка.
Попробуйте повторить позже
Для натурального обозначим Докажите, что при некотором у числа есть простой делитель, больший
Для простого и натурального обозначим через степень, в которой входит в разложение на простые множители. Заметим, что если , то
Предположим противное, обозначим Тогда все простые делители чисел вида не превосходят
______________________________________________________________________________________________________________________________________________________
Лемма: Пусть при некотором Тогда при всех
Доказательство: Обозначим тогда Заметим, что если В этой сумме все слагаемые, кроме первого, делятся на а первое делится лишь на но не на Значит и делится на но не на
______________________________________________________________________________________________________________________________________________________
Рассмотрим некоторое простое Ввиду леммы, если при некотором то существует число такое, что при всех натуральных Назовём такое простое число маленьким, все остальные простые числа, меньшие назовём большими. Так как маленьких простых конечное количество, существует натуральное большее любого числа вида где — маленькое.
Пусть теперь — большое простое число, а — такое число, что Тогда из леммы имеем а это означает, что Последний переход верен, так как не кратно
Рассмотрим теперь По доказанному, для любого большого простого Кроме того, поскольку то для любого маленького простого Поскольку все простые делители числа — либо большие, либо маленькие, отсюда следует, что что, очевидно, неверно. Противоречие.
Ошибка.
Попробуйте повторить позже
На стороне параллелограмма () отмечена точка так, что треугольник — остроугольный. Пусть и — центры описанных окружностей треугольников и соответственно. Докажите, что точка пересечения высот треугольника лежит на прямой
Подсказка 1
Иногда, чтобы проверить, что точка лежит на некоторой фиксированной прямой, достаточно показать, что она движется линейно, при линейном движении некоторого другого объекта. Что можно рассмотреть в качестве данного объекта в нашей задаче?
Подсказка 2
Сначала может показаться, что хорошей идеей является движение точки T вдоль прямой BC. К сожалению, при этом центр описанной окружности треугольника ATD не будет двигаться линейно, а значит последующее решение не предоставляется возможным. Что можно двигать линейно, чтобы исправить данную проблему?
Подсказка 3
Давайте будем двигать линейно отрезок BC вдоль прямой, на которой он лежит. Докажите, что каждый из центров окружностей так же будет двигаться линейно. Почему при этом ортоцентр будет двигаться линейно?
Подсказка 4
Высоты из точек O₁ и O₃ параллельны соответственно сторонам TD и AT, следовательно, ортоцентр является точкой пересечения прямых постоянного направления, проходящий через точки, которые движутся линейно. Таким образом, достаточно найти два положения, при которых ортоцентр лежит на прямой AD. Найдите их.
Подсказка 5
Что может быть лучше высот? Много высот! Рассмотрите положение отрезка BC, при котором ABCD является прямоугольником.
Подсказка 6
В качестве одного из возможных вторых положений можно рассмотреть такое, при котором B совпадает с точкой T. Помните, что если на описанной окружности треугольника выбрана точка, то ее образы при отражении относительно сторон треугольника попадают на одну прямую, которая проходит через ортоцентр треугольника.
Зафиксируем точки Пусть точка движется линейно по прямой, проходящей через параллельно Тогда точка так же движется линейно, поскольку Кроме этого, является точкой пересечения серединных перпендикуляров к отрезкам (фиксирован при движении) и (имеет постоянное направление и проходит через середину отрезка которая движется линейно), следовательно движется линейно. Аналогично точка движется линейно.
Рассмотрим треугольник Заметим, что прямая фиксированная, поскольку является серединным перпендикуляром к фиксированному отрезку следовательно высота, проведенная из точки имеет постоянное направление, кроме этого проходит через линейнодвижущуюся точку. То же верно про высоту, проведенную из вершины Наконец, точка пересечения указанных прямых движется линейно. Покажем, что в двух положениях лежит на
Положение 1. Пусть точка такова, что является прямоугольником. Тогда является серединой стороны — Пусть — середина стороны Как известно, является ортоцентром треугольника а значит является ортоцентром треугольника и принадлежит
Положение 2. Пусть совпадает с В этом случае точка определяется как точка пересечения прямой, проходящей через и перпендикулярной и серединного перпендикуляра к точка симметрична относительной прямой
Заметим, что
что влечет принадлежность точек и одной окружности.
Наконец, точки и симметричны точке относительно одной из сторон треугольника , следовательно прямая
является прямой Штейнера точки относительно треугольника и проходит через ее ортоцентр.
Ошибка.
Попробуйте повторить позже
В клетчатой таблице ( поставлены знаков “” в клетках одной диагонали и знаки “” во всех остальных клетках. Разрешается в некоторой строке или в некотором столбце поменять все знаки на противоположные. Докажите, что после любого количества таких операций в таблице останется не менее плюсов.
Подсказка 1
Количество клеток, содержащих "+", было бы удобно оценивать, если бы нам удалось выделить множество клеток, среди которых в любой момент времени будет не меньше одного "+".
Подсказка 2
Покажите, что среди любых четырех клеток, которые образуют прямоугольник, в которых изначально было нечетное количество "+", в любой момент времени найдется клетка, которая содержит "+".
Подсказка 3
Выделите на исходной доске на такие непересекающиеся прямоугольники, каждый из которых содержит ровно одну клетку, выделенной диагонали (той, где изначально стоят "+").
Пронумеруем строки числами сверху вниз, а столбцы — теми же числами слева направо. Клетку будем обозначать парой номеров её строки и столбца; при этом будем считать, что клетки диагонали из плюсов имеют координаты
Заметим, что если четыре клетки лежат в вершинах прямоугольника со сторонами, параллельными осям координат, то любая операция либо не меняет знаков в этих клетках, либо меняет знаки ровно в двух клетках из четырёх. В частности, чётность количества плюсов в этих четырёх клетках не меняется; значит, если среди них вначале был ровно один плюс, то и потом их будет не менее одного.
Теперь выберем в нашей таблице непересекающихся таких четвёрок; по сказанному выше, после любых операций в каждой из них найдётся как минимум один плюс, следовательно, всего плюсов будет не менее При выберем четвёрку клеток выберем четвёрку клеток а также выберем четвёрки и Легко видеть, что они удовлетворяют всем требованиям. На рисунке отмечены такие четвёрки при
Ошибка.
Попробуйте повторить позже
На плоскости отмечены все точки с целыми координатами () такие, что . Двое играют в игру (ходят по очереди). Первым ходом первый игрок ставит фишку в какую-то отмеченную точку и стирает ее. Затем каждым очередным ходом игрок переносит фишку в какую-то другую отмеченную точку и стирает ее. При этом длины ходов должны все время увеличиваться; кроме того, запрещено делать ход из точки в симметричную ей относительно центра. Проигрывает тот, кто не может сделать ход. Кто из играющих может обеспечить себе победу, как бы ни играл его соперник?
Источники:
Пусть игра с теми же правилами происходит на конечном множестве точек которое содержит точку и переходит в себя при повороте на Тогда в этой игре выигрывает первый игрок (ясно, что множество точек из условия удовлетворяет этим условиям).
Доказательство будем вести индукцией по количеству точек в Если то первый выигрывает первым своим ходом. Пусть Теперь под отрезками будем подразумевать отрезки, концы которых лежат в и не симметричны относительно Рассмотрим длины всех отрезков. Пусть — максимальная из них, и пусть — все отрезки длины (некоторые из точек могут совпадать). Заметим, что точка не является концом ни одного из этих отрезков. Действительно, пусть это не так, и среди наших отрезков есть какой-то отрезок Пусть точка получается из поворотом на относительно Тогда то есть длина отрезка не максимальна — противоречие.
Выкинем из все точки Заметим, что полученное множество удовлетворяет всем условиям нашего утверждения (так как множество отрезков переходит в себя при повороте на Значит, по предположению индукции в игре на полученном множестве выигрывает первый. Предъявим теперь выигрышную для него на множестве
Первый будет действовать по стратегии для множества с начала до того момента, когда второй впервые выведет фишку за пределы множества Это случится, ибо согласно стратегии для у первого всегда есть ход, после которого фишка остается в множестве Значит, рано или поздно второй сделает ход из точки лежащей в в точку не лежащую там (пусть тогда Тогда первый может сделать ход в точку (так как а иначе бы не лежала в после чего второму ходить некуда — он должен сделать ход длины, большей а таких ходов нет. Итого, первый выигрывает.
Первый
Ошибка.
Попробуйте повторить позже
По окружности отметили красных, синих и зеленых точек. На каждой дуге между соседними красной и синей точками поставили цифру на каждой дуге между соседними красной и зеленой — цифру а на каждой дуге между соседними синей и зеленой — цифру (На дугах между одноцветными точками поставили ) Найдите максимальную возможную сумму поставленных чисел.
Поставим в каждой красной точке число в каждой синей — а в каждой зеленой — Тогда каждое число на разноцветной дуге равно сумме чисел в ее концах, а каждое число на одноцветной дуге меньше суммы в ее концах. Значит, сумма чисел на дугах не превосходит удвоенной суммы чисел в точках, причем равенство достигается, когда все дуги — разноцветные. Сумма чисел в точках равна поэтому сумма чисел на дугах не больше
Осталось привести пример, когда эта оценка достигается (то есть когда все дуги разноцветны). Расставим сначала по кругу красных точек; затем вставим между соседними красными по точке другого цвета — синих и зеленых. Наконец, вставим оставшиеся зеленых на дуги между красными и синими точками (таких дуг образовалось поэтому их хватит).
Ошибка.
Попробуйте повторить позже
Существует ли ограниченная функция такая, что и удовлетворяет при всех неравенству
Источники:
Подсказка 1
Такой функции не существует.
Подсказка 2
Тут нужно искать противоречие с ограниченностью функции, для этого рассмотрев последовательность, значения функции на которой неограниченны.
Подсказка 3
Чтобы использовать условие f(1)>0, хочется взять y=1/x, чтобы xy было равно 1.
Подсказка 4
Рассмотрите рекурренту x_n=x_{n-1}+y_{n-1}, y_n=1/x_n и примените к ней неравенство из условия многократно, чтобы доказать неограниченность значений f(x_n).
Возьмём произвольно и положим . Тогда
Будем далее выбирать
Тогда
Ясно, что последовательность неограниченна, что противоречит условию.
нет
Ошибка.
Попробуйте повторить позже
В прямоугольной таблице строк и столбца. В её клетках расставлены числа от до каждое – по раз. При этом в каждом столбце числа различаются не более чем на Найдите минимальную возможную сумму чисел в первой строке.
Источники:
Переставив, если нужно, столбцы, будем далее считать, что числа в первой строке стоят в неубывающем порядке. Пусть — ое число первой строки. Рассмотрим сумму
Докажем, что Пусть е слагаемое этой суммы равно Если в этой сумме нет отрицательных членов, все очевидно. Ясно, что то есть Пусть то есть Тогда в первых столбцах содержатся только числа от до следовательно, там содержатся все такие числа. Отсюда следует, что и Таким образом, для любого отрицательного сумма его со следующим членом положительна, поэтому, объединив такие слагаемые в пары, получаем сумму неотрицательных слагаемых. Итак,
Это число достигается для таблицы, в которой первые три клетки первой строки заполнены единицами, а дальше идут числа Далее заполняем столбцы: в первом столбце все единицы, кроме последних двух ячеек, заполненных двойками. Во втором столбце после первой единицы стоят двойки во всех ячейках, кроме последних двух, заполненных тройками. После этого все столбцы, кроме последнего, заполняются по принципу: пусть в первой ячейке этого столбца стоит тогда во всех остальных ячейках, кроме двух последних ставится а в двух последних — В последнем столбце 8 последних ячеек заполняются числом
2005004
Ошибка.
Попробуйте повторить позже
В стране городов, некоторые пары городов соединены дорогами. Для каждых четырёх городов существуют хотя бы две дороги между ними. Известно, что не существует маршрута, проходящего по каждому городу ровно один раз. Докажите, что можно выбрать два города таким образом, чтобы каждый из оставшихся городов был соединен дорогой хотя бы с одним из двух выбранных городов.
Источники:
Подсказка 1
Переведём задачку на язык графов. Города - вершины, дороги - рёбра, а как можно правильнее применить условия про отсутствие пути, проходящего через все города?
Подсказка 2
Верно, из этого следует, что самый длинный путь S соединяет не более 99 вершин. Давайте теперь немного изучим наш рисунок. Например, могут ли крайние вершины пути быть смежными? А что можно сказать о смежности вершин пути S с вершинами вне этого пути?
Подсказка 3
Конечно, получается, с вершинами не из S могут соединяться только те, что не стоят на концах S (и только если путь не замыкается в цикл). Но ведь у нас также есть правило про 2 ребра на 4 вершины. Что, если две из них принадлежат S, а две - не принадлежат?
Подсказка 4
В предыдущем рассмотрении мы не учли, что существуют случаи, когда взять какие-то 2 вершины не из S невозможно. Это происходит, когда в S ровно 99 вершин. Здесь уже нельзя сразу сделать вывод о смежности концов пути, так что лучше будет отдельно разобрать два случая.
Подсказка 5
В случае, когда образуется цикл из вершин S и вершина вне него не соединяется ни с одной вершиной цикла, обратите внимание на то, сколько рёбер могут отсутствовать в подграфе S. Что можно сказать об их чётности? Что из этого следует?
Построим граф, вершины которого соответствуют городам, а ребра — дорогам. Выберем в этом графе самый длинный путь пусть вершины и — концы этого пути. Из условия задачи следует, что в пути не более вершин. Отметим, что концы пути — вершины и не могут быть смежны с вершинами не из (иначе путь можно удлинить). А в случае, когда вершины и смежны и наш путь замыкается в цикл, никакая вершина пути по аналогичным причинам не может быть смежна с вершиной не из
1) Рассмотрим случай, когда в не более вершин. В этом случае рассмотрим любые две вершины и не входящие в путь и концы пути и Среди этих четырех вершин должны быть проведены хотя бы два ребра. Так как ни ни не могут быть смежны с вершинами не из то концы пути и соединены ребром.
Таким образом, путь замыкается в цикл, и тогда ни одна из вершин пути не смежна с вершиной не из Рассмотрим четверку из любых двух вершин и пути и любых двух вершин и не входящих в Так как между этими четырьмя вершинами проведено хотя бы два ребра, то одно из них соединяет и а другое — и Таким образом, в рассматриваемом случае все вершины пути попарно смежны и все вершины не из также попарно смежны. Отсюда очевидно следует утверждение задачи. 2) Рассмотрим случай, когда вне пути лежит ровно одна вершина. Пусть это вершина Если не смежна ни с одной из вершин пути то рассмотрим и любые три вершины пути Поскольку среди этих четырех вершин проведено хотя бы два ребра, то среди любых трех вершин пути проведено хотя бы два ребра. Следовательно, для любой вершины из есть не более одной не смежной с ней вершины пути Поскольку вершин пути нельзя разбить на пары не соединенных ребром, то в должна быть вершина, смежная со всеми остальными вершинами Эта вершина в паре с удовлетворяет утверждению задачи.
Если концы максимального пути и смежны, то, как мы доказали, вершина не смежна ни с одной из вершин пути а этот случай уже разобран.
Остается рассмотреть последний случай, когда концы пути не смежны и вершина смежна хотя бы с одной из вершин пути Рассмотрим вершины и произвольную четвертую вершину (естественно, лежащую на пути ). Так как и попарно не смежны, то смежна хотя бы с двумя вершинами из и Пусть смежна с вершиной пути Одна из соседних с вершин пути не является концом пути. Можно считать, что это первая вершина лежащая на пути из в по ребрам Если смежна с то, пройдя от к по пути далее по ребрам и и затем по пути от к мы обойдем все вершины нашего графа ровно по одному разу, что невозможно по условию. Если же не смежна с то, как мы доказали, эта вершина смежна и с и с Тогда пройдем по ребру далее по пути от к по ребрам и и затем по пути от его конца до вершины, соседней с на пути — получился путь, проходящей по каждой вершине нашего графа ровно один раз, которого по условию не существует. Следовательно, и этот случай не возможен.
Таким образом, мы рассмотрели все случаи и в тех из них, которые возможны, убедились в справедливости утверждения задачи.