РЕШУ ОЛИМП, математика: задания, ответы, решения

Поиск
?

в условии в решении в тексте к заданию в атрибутах
Скопировать ссылку на результаты поиска
Класс: 10 11 9
Атрибут

Всего: 175 1–20 | 21–40 | 41–60 | 61–80 | 81–100 | 101–120 …

Добавить в вариант

Тип 0 № 1802 Добавить в вариант

На плоскости дан выпуклый многоугольник с вершинами в целых точках, содержащий внутри начало координат O. Пусть V₁  — множество векторов, идущих из O в вершины многоугольника, а V₂  — множество векторов, идущих из O во все целые точки, содержащиеся внутри и на границе многоугольника (таким образом, V₁ содержится в V₂). Два кузнечика прыгают по целым точкам: каждый прыжок первого кузнечика смещает его на вектор из множества V₁, а второго  — из V₂. Докажите, что для некоторого числа c верно следующее утверждение: если оба кузнечика могут допрыгать из O до некоторой точки A, причем второму понадобится для этого n прыжков, то первый сможет сделать это не более чем за n + c прыжков.

(А. Акопян)

Решение.

Пусть $\vecv принадлежит дробь: числитель: V_2 , знаменатель: V_1 конец дроби ,$ тогда $\vecv$ лежит в треугольнике с вершинами $\veca,$ $\vecb,$ $\vecc$ из $V_1,$ и, значит, $\vecv= альфа \veca плюс бета \vecb плюс гамма \vecc,$ где α, β, γ — неотрицательные рациональные числа с суммой 1 (они пропорциональны площадям треугольников vbc, vac, vab соответственно). Если $N=N левая круглая скобка \vecv правая круглая скобка$   — общий знаменатель чисел α, β, γ, то N прыжков на вектор $\vecv$ можно заменить на $альфа N$ прыжков на вектор $\veca,$ $бета N$ прыжков на вектор $\vecb,$ $гамма N$ прыжков на вектор $\vecc.$ Таким образом, можно считать, что второй кузнечик использует прыжок на вектор $\vecv$ менее чем $N левая круглая скобка \vecv правая круглая скобка$ раз.

Предположим, что утверждение задачи неверно, тогда имеется последовательность точек $x_i,$ такая что $f левая круглая скобка x_i правая круглая скобка минус g левая круглая скобка x_i правая круглая скобка arrow бесконечность ,$ где $f левая круглая скобка x правая круглая скобка$ и $g левая круглая скобка x правая круглая скобка$ обозначают количества прыжков, необходимых первому и второму кузнечикам соответственно, чтобы достичь точки x . Переходя к подпоследовательности, можем считать, что набор использованных вторым кузнечиком прыжков из $дробь: числитель: V_2, знаменатель: V_1 конец дроби$ всегда один и тот же  — ведь мы добились того, что количество возможных таких наборов конечно. Еще несколько раз переходя к подпоследовательности, можем считать, что для каждого вектора $\veca принадлежит V_1$ количество $n_i левая круглая скобка \veca правая круглая скобка$ прыжков на вектор $\veca$ у второго кузнечика для достижения точки $x_i$ стабилизируется или же возрастает к бесконечности. Это позволяет считать, что при $i больше j$ точка $x_i$ достигается вторым кузнечиком через промежуточную точку $x_j,$ причем все прыжки из $x_j$ в $x_i$ лежат в $V_1$ и их количество равно $g левая круглая скобка x_i правая круглая скобка минус g левая круглая скобка x_j правая круглая скобка .$ Но тогда первый кузнечик может попасть в $x_i$ за

$f левая круглая скобка x_j правая круглая скобка плюс g левая круглая скобка x_i правая круглая скобка минус g левая круглая скобка x_j правая круглая скобка =g левая круглая скобка x_i правая круглая скобка плюс c$

прыжков. Противоречие.

Решение · Помощь

Тип 0 № 1803 Добавить в вариант

Миша приехал в страну, в которой n городов и каждые два напрямую соединены дорогой. Он собирается, начав с некоторого города, объехать несколько городов, не заезжая ни в один город дважды. Каждый раз, пока Миша едет по дороге, президент разрушает k дорог, ведущих из города, в который ведет эта дорога. (А если там нет такого количества уцелевших дорог  — разрушает все оставшиеся, кроме той, по которой едет Миша.) Какое наибольшее количество городов сможет объехать Миша, независимо от действия президента?

Решение.

В случае $k больше или равно n минус 2,$ пока Миша едет из первого города во второй, Президент разрушит все остальные $n минус 2$ дороги, ведущие из второго города, и Миша сможет посетить лишь эти два города.

Пусть $k меньше или равно n минус 3.$ Пусть Миша приехал в город X, и в этот момент есть $k плюс 1$ городов, в которых он еще не был. Тогда Миша сможет продолжить свой путь, поехав в один из них. В самом деле, дороги, ведущие из X в эти города, могли быть разрушены только во время последней Мишиной поездки (пока он ехал в X), но президент не мог сразу разрушить все эти дороги, ибо их больше чем k.

Таким образом, Миша может попасть в тупик лишь если осталось не более k не посещенных им городов, т. е. если он проехал не менее $n минус k$ городов.

С другой стороны, президент может изначально выбрать некоторые k «особо ценных» городов своей страны, и во время каждого Мишиного перемещения стирать дороги из города, в который Миша едет, в эти k городов. Этим он не даст Мише попасть в эти города, т. е. Миша посетит заведомо не более $n минус k$ городов.

Ответ: Миша сможет объехать $n минус k$ городов, если $k меньше или равно n минус 3,$ и 2 города в противном случае (при $k=n минус 2$ эти ответы совпадают).

Решение · Помощь

Тип 0 № 1804 Добавить в вариант

Раскрасим вершины 2018-угольника в два цвета так, чтобы любые две соседние вершины были разного цвета. Если сумма углов при вершинах одного цвета равна сумме углов при вершинах другого цвета, будем называть такой 2018-угольник интересным. В выпуклом 2019-угольнике отметили одну вершину. Оказалось, что при удалении любой неотмеченной вершины остается интересный 2018-угольник. Докажите, что при удалении отмеченной вершины также остается интересный 2018-угольник.

Решение.

Обозначим соседние вершины 2019-угольника буквами A, B, C и D (по часовой стрелке). Пусть вершины B и C не являются отмеченными. Рассмотрим углы 2019-угольника, идущие через один против часовой стрелки, начиная с A и заканчивая D. Обозначим их сумму через u. Рассмотрим оставшиеся углы, обозначим их сумму v. Поскольку при удалении вершины B получается интересный 2018-угольник, имеем равенство сумм углов

$u минус \angle C A B=v минус \angle A C B минус \angle A B C \qquad левая круглая скобка * правая круглая скобка$

(угол $\angle B$ не входит в этот многоугольник, а углы $\angle A$ и $\angle C$ надо уменьшить на $\angle C A B$ и $\angle A C B$ соответственно). Аналогично, поскольку при удалении вершины C получается интересный 2018-угольник, имеем равенство сумм углов

$u минус \angle C D B=v минус \angle C B D минус \angle B C D . \qquad левая круглая скобка ** правая круглая скобка$

Вычтем из равенства (**) равенство (*), получим

$\angle C A B минус \angle C D B=\angle A C B плюс \angle A B C минус \angle C B D минус \angle B C D=\angle A B D минус \angle A C D.$

Прибавив к нему верное равенство

$\angle C A B плюс \angle A B D=\angle C D B плюс \angle A C D,$

получим, что $\angle C A B=\angle C D B.$ Следовательно, четырехугольник $A B C D$ вписанный. Отметим также, что верно и обратное. А именно, если выполняется равенство (*) (т. е. 2018-угольник без вершины B  — интересный) и четырехугольник ABCD вписанный, то верно и равенство (**), а значит, 2018-угольник без вершины C  — интересный.

Последовательно действуя таким образом, мы докажем, что исходный 2019-угольник является вписанным. Следовательно, если рассмотреть отмеченную вершину P и соседнюю с ней вершину Q, то из интересности 2018-угольника без вершины Q и вписанности 2019-угольника мы получим, что 2018-угольник без вершины P  — интересный.

Решение · Помощь

Тип 0 № 1805 Добавить в вариант

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

Решение.

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

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

$\mathrmOP левая квадратная скобка \mathrmOO правая квадратная скобка \mathrmO arrow \mathrmOPPPO. \qquad левая круглая скобка * правая круглая скобка$

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

Покажем, что все остальные конфигурации нельзя получить друг из друга. Действительно, наша операция не меняет разность количества орлов на чётных местах и количества орлов на нечётных местах. Когда большая группа состоит из одного орла, т. е. когда все орлы стоят на нечётных местах, а решки на чётных, эта разность равна $дробь: числитель: n, знаменатель: 2 конец дроби .$ Увеличение количества орлов в большой группе уменьшает эту разность на 1, поэтому все разности от 0 до $дробь: числитель: n, знаменатель: 2 конец дроби .$ возможны. Аналогично, когда большая группа состоит из решек получатся разности от −1 до $минус дробь: числитель: n, знаменатель: 2 конец дроби .$ Итого получаем $n плюс 1$ различную конфигурацию.

Ответ: 2 варианта для нечётных n и $n плюс 1$ вариант для чётных n.

Решение · Помощь

Тип 0 № 1806 Добавить в вариант

Коэффициенты многочлена f(x)  — целые числа, по модулю не превосходящие 5 000 000. При этом каждое из уравнений $f левая круглая скобка x правая круглая скобка =x, f левая круглая скобка x правая круглая скобка =2x, \dots, f левая круглая скобка x правая круглая скобка =20x$   имеет целый корень. Докажите, что f(0) = 0.

Решение · Помощь

Тип 0 № 1807 Добавить в вариант

Дан вписанный четырехугольник ABCD. Прямая, перпендикулярная BD, пересекает отрезки AB, BC и лучи DA, DC в точках P, Q, R, S соответственно. Известно, что PR = QS. Докажите, что середина отрезка PQ равноудалена от точек A и C.

Решение · Помощь

Тип 0 № 1808 Добавить в вариант

Пусть a, b, c, d > 0. Докажите неравенство

$a в степени 4 плюс b в степени 4 плюс c в степени 4 плюс d в степени 4 минус 4abcd больше или равно 4 левая круглая скобка a минус b правая круглая скобка в квадрате корень из: начало аргумента: abcd конец аргумента .$

Решение · Помощь

Тип 0 № 1809 Добавить в вариант

Шашка передвигается из левого нижнего угла доски 100 × 100 в правый верхний угол, на каждом шагу перемещаясь на одну клетку вправо или на одну клетку вверх. Пусть a  — число путей, в которых ровно 70 шагов шашка совершает под диагональю, идущей из левого нижнего угла в правый верхний, а b  — число путей, в которых таких шагов ровно 110. Что больше: a или b?

Решение.

Для каждого k, $0 меньше или равно k меньше или равно n$ обозначим через $M_k$ множество маршрутов шашки, ведущих из левого нижнего в правый верхний угол доски $n \times n,$ и делающих ровно $2 k$ шагов ниже главной диагонали. Имеет место потрясающий факт: при фиксированном n все множества $M_k$ содержат поровну элементов!

Это утверждение называется теоремой Чанга-Феллера, оно впервые доказано МакМагоном в 1909 г. Приводимое ниже комбинаторное доказательство появилось в 1955 г.

Предъявим взаимно однозначное соответствие между множествами $M_k$ и $M_k плюс 1,$ $0 меньше или равно k меньше или равно n .$ Маршрут шашки можно интерпретировать как последовательность из $2 n$ букв «в» или «п», причем букв каждого вида в ней поровну. Рассмотрим произвольный маршрут a из множества $M_k .$ Запишем его в виде

$a=uвvпw ,$

где «в» обозначает первый ход, который шашка сделала вверх, находясь на диагонали; «п»  — это ход, которым она впервые после этого вернулась на диагональ; $u минус 9$ то, возможно, пустая последовательность ходов, которые шашка совершила до выполнения хода в (эти ходы были сделаны ниже диагонали); $v минус$ это, возможно, пустая последовательность ходов, которые шашка совершила после выполнения хода в, но до выполнения хода «п» (эти ходы были сделаны выше диагонали); наконец, w  — это все остальные ходы шашки. Поставим в соответствие маршруту следующий маршрут b из множества $M_k плюс 1$ :

$b=vпuвw.$

Это соответствие биективно.

Ответ: $a=b.$

Решение · Помощь

Тип 0 № 1812 Добавить в вариант

Докажите, что для каждого натурального числа N найдется такое целое k > 0, что N удастся записать в виде суммы чисел 2⁰, 2¹, $2 в квадрате , \dots, 2 в степени k ,$ каждое из которых участвует в этой сумме 1 или 2 раза. Например, $12=2 в степени 0 плюс 2 в степени 0 плюс 2 в степени 1 плюс 2 в квадрате плюс 2 в квадрате .$

(М. Антипов)

Решение · Помощь

Тип 0 № 1813 Добавить в вариант

Дано нечётное натуральное число n > 1. На доске записаны числа n, n+1, n+2, . . . , 2n−1. Докажите, что можно стереть одно из них так, чтобы сумма оставшихся чисел не делилась ни на одно из оставшихся чисел.

Решение · Помощь

Тип 0 № 1814 Добавить в вариант

Дан остроугольный треугольник ABC. На отрезке AC и на продолжении стороны BC за точку C выбираются такие переменные точки X и Y соответственно, что $∠\angle ABX плюс \angle CXY = 90°.$ Точка T  — проекция точки B на прямую XY. Докажите, что все такие точки T лежат на одной прямой.

(С. Берлов)

Решение · Помощь

Тип 0 № 1815 Добавить в вариант

На круглом ожерелье висят n > 3 бусинок, каждая покрашена в красный или синий цвет. Если у какой-то бусинки соседние с ней бусинки покрашены одинаково, ее можно перекрасить (из красного в синий или из синего в красный). При каких n из любой исходной раскраски бусинок можно сделать ожерелье, в котором все бусинки покрашены одинаково?

(С. Берлов)

Решение.

Докажем, что при нечетной длине ожерелья все бусинки можно сделать одноцветными. Любое ожерелье разбивается на блоки подряд идущих бусинок одинакового цвета. Среди них обязан присутствовать блок нечетной длины (допустим, красный). Перекрасим в нём сначала все бусинки с четным номером, а потом все остальные его бусинки. В результате этот блок станет синим и сольётся с соседними синими блоками количество блоков уменьшится. Рано или поздно останется один блок, чего мы и хотели. Приведем два объяснения, почему четные n не подходят.

I способ. (инвариант). Легко убедиться, что при любом перекрашивании количество пар соседних бусинок вида к-к либо не меняется, либо меняется ровно на 2, т. е. в любом случае не меняется четность этого числа. То же самое верно и про число пар вида с−с. В одноцветном ожерелье (четной длины) оба эти количества четны. Поэтому из ожерелья, в котором оба эти количества нечетны, нельзя получить ни одно из двух одноцветных ожерелий. При четном n таково, например, ожерелье

II способ. (критические ожерелья). Для n, кратного четырём, рассмотрим ожерелье вида ...−к−к−с−ск−к−с−с−..., в котором чередуются пары красных и пары синих бусинок. С этим ожерельем нельзя сделать ни одного перекрашивания. В частности, из него нельзя получить и одноцветное.

Если n четно, но имеет вид $n=4 k плюс 2,$ немного изменим вид критического ожерелья: ...−к−к−к−к−с−с−кк−с−с−... (один из красных блоков теперь имеет длину 4). С ним можно сделать лишь одно перекрашивание, точнее, два аналогичных  — перекрасить вторую или третью красную бусинку в длинном блоке. С полученным ожерельем можно сделать лишь две операции: обратную к только что проделанной или операцию, перекрашивающую бусинку, соседнюю с только что перекрашенной.

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

Ответ: при всех нечетных n.

Решение · Помощь

Тип 0 № 1816 Добавить в вариант

Можно ли нарисовать на плоскости треугольник ABC и отметить на той же плоскости две точки X и Y , так что

$AX = BY = AB,$

$BX = CY = BC,$

$CX = AY = CA ?$

(М. Иванов)

Решение · Помощь

Тип 0 № 1817 Добавить в вариант

Даны два нечетных натуральных числа a и b. Докажите, что существует такое натуральное k, что хотя бы одно из чисел $b в степени k минус a в квадрате$ и $a в степени k минус b в квадрате$ делится на $2 в степени левая круглая скобка 2018 правая круглая скобка .$

(А. Голованов)

Решение.

Будем решать обобщенную задачу. Дано натуральное число n и два нечетных натуральных числа a и b. Докажите, что существует такое натуральное k, что хотя бы одно из чисел $b в степени левая круглая скобка 2 k правая круглая скобка минус a в квадрате$ и $a в степени левая круглая скобка 2 k правая круглая скобка минус b в квадрате$ делится на $2 в степени левая круглая скобка n правая круглая скобка .$

Воспользуемся следующим известным утверждением: пусть число $c минус 1$ дает остаток $2 в степени левая круглая скобка k правая круглая скобка$ при делении на $2 в степени левая круглая скобка k плюс 1 правая круглая скобка ,$ где $k больше или равно 2 .$ Тогда $c в квадрате минус 1$ дает остаток $2 в степени левая круглая скобка k плюс 1 правая круглая скобка$ при делении на $2 в степени левая круглая скобка k плюс 2 правая круглая скобка .$

Пусть $a в квадрате минус 1$ делится на $2 в степени левая круглая скобка альфа правая круглая скобка$ и не делится на $2 в степени левая круглая скобка альфа плюс 1 правая круглая скобка ,$ а $b в квадрате минус 1$ делится на $2 в степени левая круглая скобка бета правая круглая скобка$ и не делится на $2 в степени левая круглая скобка бета плюс 1 правая круглая скобка .$ Очевидно, что при этом $альфа , бета больше или равно 2.$ Тогда $a в квадрате минус 1$ дает остаток $2 в степени левая круглая скобка альфа правая круглая скобка$ при делении на $2 в степени левая круглая скобка альфа плюс 1 правая круглая скобка ,$ а $b в квадрате минус 1$ дает остаток $2 в степени левая круглая скобка бета правая круглая скобка$ при делении на $2 в степени левая круглая скобка бета плюс 1 правая круглая скобка .$ Пусть $альфа меньше или равно бета ,$ положим для краткости $2 в степени левая круглая скобка бета минус альфа правая круглая скобка =m .$ По лемме число

$a в степени левая круглая скобка 2 m правая круглая скобка минус 1= левая круглая скобка левая круглая скобка левая круглая скобка a в квадрате правая круглая скобка \overbrace в квадрате правая круглая скобка \ldots правая круглая скобка в квадрате в степени левая круглая скобка бета минус альфа двоек правая круглая скобка минус 1 \qquad левая круглая скобка * правая круглая скобка$

дает остаток $2 в степени левая круглая скобка бета правая круглая скобка$ при делении на $2 в степени левая круглая скобка бета плюс 1 правая круглая скобка .$

Будем решать задачу индукцией по n. Если $n меньше или равно бета плюс 1,$ то нам подойдет $k=m,$ поскольку $a в степени левая круглая скобка 2 m правая круглая скобка$ и $b в квадрате$ дают равные остатки при делении на $2 в степени левая круглая скобка бета правая круглая скобка .$ Сделаем переход от n к $n плюс 1.$ По индукционному предположению при некотором k число $a в степени левая круглая скобка 2 k правая круглая скобка минус b в квадрате$ делится на $2 в степени левая круглая скобка n правая круглая скобка .$ Если оно делится и на $2 в степени левая круглая скобка n плюс 1 правая круглая скобка ,$ то переход сделан. Иначе оно дает остаток $2 в степени левая круглая скобка n правая круглая скобка$ при делении на $2 в степени левая круглая скобка n плюс 1 правая круглая скобка .$ Пусть $r=2 в степени левая круглая скобка n минус бета правая круглая скобка плюс 1.$ Тогда по лемме $b в степени левая круглая скобка 2 левая круглая скобка r минус 1 правая круглая скобка правая круглая скобка минус 1$ дает остаток $2 в степени левая круглая скобка n правая круглая скобка$ при делении на $2 в степени левая круглая скобка n плюс 1 правая круглая скобка .$ Следовательно, $b в степени левая круглая скобка 2 r правая круглая скобка минус b в квадрате$ дает остаток $2 в степени левая круглая скобка n правая круглая скобка$ при делении на $2 в степени левая круглая скобка n плюс 1 правая круглая скобка .$ Воспользуемся формулой разности степеней:

$a в степени левая круглая скобка 2 k r правая круглая скобка минус b в степени левая круглая скобка 2 r правая круглая скобка = левая круглая скобка a в степени левая круглая скобка 2 k правая круглая скобка минус b в квадрате правая круглая скобка левая круглая скобка a в степени левая круглая скобка 2 k левая круглая скобка r минус 1 правая круглая скобка правая круглая скобка плюс a в степени левая круглая скобка 2 k левая круглая скобка r минус 2 правая круглая скобка правая круглая скобка b в квадрате плюс a в степени левая круглая скобка 2 k левая круглая скобка r минус 3 правая круглая скобка правая круглая скобка b в степени левая круглая скобка 4 правая круглая скобка плюс \ldots плюс b в степени левая круглая скобка 2 левая круглая скобка r минус 1 правая круглая скобка правая круглая скобка правая круглая скобка .$

Первая скобка дает остаток $2 в степени левая круглая скобка n правая круглая скобка$ при делении на $2 в степени левая круглая скобка n плюс 1 правая круглая скобка ,$ вторая состоит из r нечетных слагаемых и, значит, нечётна. Стало быть, разность $a в степени левая круглая скобка 2 k r правая круглая скобка минус b в степени левая круглая скобка 2 r правая круглая скобка$ дает остаток $2 в степени левая круглая скобка n правая круглая скобка$ при делении на $2 в степени левая круглая скобка n плюс 1 правая круглая скобка .$ Но тогда

$a в степени левая круглая скобка 2 k r правая круглая скобка минус b в квадрате = левая круглая скобка a в степени левая круглая скобка 2 k r правая круглая скобка минус b в степени левая круглая скобка 2 r правая круглая скобка правая круглая скобка минус левая круглая скобка b в степени левая круглая скобка 2 r правая круглая скобка минус b в квадрате правая круглая скобка$

делится на $2 в степени левая круглая скобка n плюс 1 правая круглая скобка ,$ поскольку выражения в скобках дают одинаковые остатки при делении на $2 в степени левая круглая скобка n плюс 1 правая круглая скобка .$

Решение · Помощь

Тип 0 № 1818 Добавить в вариант

В клетчатом квадрате 10×10 (стороны клеток имеют единичную длину) выбрали n клеток, в каждой из них нарисовали одну из диагоналей и поставили на этой диагонали стрелочку в одном из двух направлений. Оказалось, что для любых двух стрелочек либо конец одной из них совпадает с началом другой, либо расстояние между их концами не меньше 2. При каком наибольшем n это возможно?

(М. Антипов)

Решение · Помощь

Тип 0 № 1819 Добавить в вариант

Для непостоянной арифметической прогрессии (a_n) существует такое натуральное n > 1, что $a_n плюс a_n плюс 1=a_1 плюс \dots плюс a_3n минус 1.$   Докажите, что в этой прогрессии нет нулевых членов.

Решение · Помощь

Тип 0 № 1820 Добавить в вариант

Каждые два из n городов Руритании соединены прямым авиарейсом одной из двух авиакомпаний  — Альфа или Бета. Промонопольный комитет хочет, чтобы не менее k рейсов выполнялись компанией Альфа. Для этого он может хоть каждый день выбирать любые три города и изменять принадлежность трёх рейсов, связывающих эти города друг с другом (то есть отбирать каждый из этих рейсов у компании, которая его выполняет, и передавать другой). При каком наибольшем k комитет заведомо сможет за какое-то время достичь своей цели, как бы ни распределялись рейсы сейчас?

Решение · Помощь

Тип 0 № 1821 Добавить в вариант

Даны натуральные числа $a, b$ и $c больше или равно b.$   Докажите, что $a в степени b левая круглая скобка a плюс b правая круглая скобка в степени c больше c в степени b a в степени c .$

Решение · Помощь

Тип 0 № 1822 Добавить в вариант

В классе 25 учеников. Учитель хочет запасти N конфет, провести олимпиаду и раздать за успехи в ней все N конфет (решившие поровну задач должны получить поровну, решившие меньше  — меньше, в том числе, возможно, и ноль конфет). При каком наименьшем N это будет возможно независимо от количества задач на олимпиаде и успехов учеников?

Решение.

Покажем, что меньшего числа конфет может не хватить. На тот случай, если все участники решили поровну задач, число конфет необходимо сделать кратным 25. Пусть $N=25 k .$ Представим себе, что 24 человека решили поровну, а 25-й решил меньше. Если каждому из первых 24 участников дать по k конфет или еще меньше, то останутся лишние конфеты. Значит, каждому из них необходимо дать как минимум по $k плюс 1$ конфете, откуда $25 k больше или равно 24 левая круглая скобка k плюс 1 правая круглая скобка ,$ то есть $k больше или равно 24 .$

Теперь докажем по индукции, что можно раздать m участникам $m левая круглая скобка m минус 1 правая круглая скобка$ конфет так, чтобы каждый получил меньше $2 s$ конфет. База при $m=1$ очевидна: дадим единственному участнику 0 конфет.

Переход от $m минус 1$ к m. Пусть есть $s больше или равно 1$ участников с самым большим результатом, и кроме них еще t участников, $s плюс t=m.$ Менее успешным участникам по предположению индукции раздадим $t левая круглая скобка t минус 1 правая круглая скобка$ конфет (причем всем меньше чем по $2t правая круглая скобка .$ После этого останется

$левая круглая скобка s плюс t правая круглая скобка левая круглая скобка s плюс t минус 1 правая круглая скобка минус t левая круглая скобка t минус 1 правая круглая скобка =s левая круглая скобка s плюс 2 t минус 1 правая круглая скобка$

конфет, и мы раздадим их поровну s «верхним» участникам. Каждый из них получит по $s плюс 2 t минус 1$ конфет. Это число не меньше, чем $2t,$ поэтому больше того, что мы раздали каждому из остальных. Кроме того,

$s плюс 2 t минус 1 меньше 2 s плюс 2 t=2 m,$

что и завершает переход.

Ответ: $600=25 умножить на 24$ конфет.

Решение · Помощь

Тип 0 № 1823 Добавить в вариант

Дан многочлен f(x) степени 2000. При этом у многочлена $f левая круглая скобка x минус 1 правая круглая скобка$   ровно 3400 корней, а у многочлена $f левая круглая скобка 1 минус x в квадрате правая круглая скобка$   ровно 2700 корней. Докажите, что расстояние между какими-то двумя корнями f(x) меньше 0,002.

Решение · Помощь

Всего: 175 1–20 | 21–40 | 41–60 | 61–80 | 81–100 | 101–120 …