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

Поиск
?

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

Всего: 115 … 21–40 | 41–60 | 61–80 | 81–100 | 101–115

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

Тип 21 № 9212 Добавить в вариант

Сто друзей, среди которых есть Петя и Вася, живут в нескольких городах. Петя узнал расстояние от своего города до города каждого из оставшихся 99 друзей и сложил эти 99 чисел. Аналогично поступил Вася. Петя получил 1000 км. Какое наибольшее число мог получить Вася? (Города считайте точками плоскости; если двое живут в одном и том же городе, расстояние между их городами считается равным нулю).

(Борис Френкин)

Критерии проверки:

Критерий	Оценка
Только верный ответ	−.
Доказано лишь, что Вася мог получить 99 000 км, и/или утверждается, что максимальное возможное число, которое Вася мог получить, достигается тогда, когда все, кроме Васи, живут в одном городе	∓

Как ставились оценки:

—  «+» ставится за любое правильное решение;

—  «±» ставится за решение с существенным, но легко восполнимым пробелом;

—  «∓» ставится за неверное решение, однако с существенным продвижением;

—  «–» ставится за неверное решение;

—  «0» ставится, если задача не записана;

—  «+.», «–.» (варианты «+», «–») ставятся в случае менее существенных недостатков (продвижений), чем в случае «+ –» и «–+»;

—  «+/2» ставится в отдельных случаях, когда в тексте присутствует правильная идея, недостаточно развитая, чтобы считать задачу решенной. Эта оценка ставится и в том случае, если задача естественно распадается на две половины, из которых одна решена.

Если жюри хочет обратить внимание на необычное достижение учащегося (краткость, красота, усиление результата и т. п.),  — это отмечается знаком «+!».

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

Решение · Критерии · Помощь

Тип 21 № 9214 Добавить в вариант

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

(Татьяна Казицына)

Критерии проверки:

Критерий	Оценка
Пример, который можно сделать верным, указав вспомогательные прямые, на которых лежат «ключевые» вершины; сами прямые не нарисованы, и без них по рисунку не ясно, всегда ли получатся ровно три части	∓
Пример, в котором нарисованы вспомогательные прямые, на которых лежат «ключевые» вершины, но стороны многоугольника не прямые (например, дуги), пример исправляется, если приблизить дуги ломаными	±
Верный пример, нарисованный по клеточкам	+
Верный пример с нарисованными вспомогательными прямыми, на которых лежат «ключевые» вершины	+

Как ставились оценки:

—  «+» ставится за любое правильное решение;

—  «±» ставится за решение с существенным, но легко восполнимым пробелом;

—  «∓» ставится за неверное решение, однако с существенным продвижением;

—  «–» ставится за неверное решение;

—  «0» ставится, если задача не записана;

Решение · Критерии · Помощь

Тип 21 № 9215 Добавить в вариант

Пусть n > 1  — целое число. В одной из клеток бесконечной белой клетчатой доски стоит ладья. Каждым ходом она сдвигается по доске ровно на n клеток по вертикали или по горизонтали, закрашивая пройденные n клеток в чёрный цвет. Сделав несколько таких ходов, не проходя никакую клетку дважды, ладья вернулась в исходную клетку. Чёрные клетки образуют замкнутый контур. Докажите, что число белых клеток внутри этого контура даёт при делении на n остаток 1.

(Александр Грибалко)

Решение.

Пусть сторона клеток доски равна 1. Отметим центр начальной клетки и центры всех клеток, до которых ладья может добраться за один или несколько ходов. Проведём через них синие прямые параллельно линиям сетки. Образуется вспомогательная синяя сетка, разбитая на клетки со стороной n. Если ладья прыгала из клетки A в клетку B, соединим центры этих клеток отрезком. Эти отрезки образуют замкнутый многоугольник; его вершины лежат в узлах синей сетки, а стороны идут по линиям синей сетки. Поэтому площадь многоугольника кратна n² (пусть она равна an²). Периметр его кратен 2n (ведь шаги ладьи кратны n, причём сдвиги ладьи влево компенсируются сдвигами вправо, а сдвиги вверх  — сдвигами вниз). Далее можно рассуждать по-разному.

Способ 1. Площадь многоугольника состоит из белой клетчатой части и из чёрной каёмки, окружающей белую часть. Разобьём контур многоугольника на отрезки между узлами синей сетки. К каждому из них изнутри прилегает чёрная прямоугольная полоска ширины $дробь: числитель: 1, знаменатель: 2 конец дроби .$ Её площадь равна $дробь: числитель: n, знаменатель: 2 конец дроби .$ Так как число таких полосок чётно, их общая площадь  — целое число, кратное n (пусть bn). Но эта «общая площадь» не совпадает с чёрной площадью внутри многоугольника. Несовпадения возникают из-за чёрных клеток в углах многоугольника: если угол равен 90°, то полоски перекрываются по четверти чёрной клетки; а при угле в 270° внутри остаётся четверть клетки, не покрытая полосками. Внешние углы многоугольника равны $\pm 90 в степени левая круглая скобка \circ правая круглая скобка ,$ а поскольку сумма внешних углов (с учётом знаков) равна 360°, то внешних углов в 90° на 4 больше, чем внешних углов в −90°, то есть внутренних углов в 90° на 4 больше, чем углов в 270°. Поэтому площадь чёрной каёмки внутри контура меньше суммарной площади полосок на 1. Значит, чёрная площадь внутри многоугольника равна bn − 1, а белая площадь внутри равна тогда

$a n в квадрате минус левая круглая скобка b n минус 1 правая круглая скобка =n умножить на левая круглая скобка a n минус b правая круглая скобка плюс 1.$

Но эта площадь равна числу белых клеток!

Способ 2. Проведём через центры всех клеток исходной доски красные прямые параллельно линиям сетки, образуется красная сетка с единичными клетками. Многоугольник, рассмотренный выше,  — клетчатый многоугольник на этой сетке, поэтому количество Γ красных узлов на его границе равно его периметру, а значит, кратно 2n. Центром всякой клетки исходной доски является красный узел, поэтому такая клетка целиком лежит внутри этого многоугольника тогда и только тогда, когда внутри этого многоугольника лежит её центр. Поэтому количество B белых клеток внутри многоугольника равно количеству красных узлов внутри него. По формуле Пика для этого многоугольника и красной сетки, $B плюс дробь: числитель: \Gamma, знаменатель: 2 конец дроби минус 1=a n в квадрате ,$ откуда $B\equiv 1 левая круглая скобка \bmod n правая круглая скобка .$

Приведем другое решение.

Назовём клетки, в которых может останавливаться ладья, узлами. Клетка является узлом, если до какого-то другого узла расстояние как по вертикали, так и по горизонтали кратно n. Чёрный контур вместе с белыми клетками внутри него образуют клетчатый многоугольник M.

Индукция по периметру M. База. Наименьший периметр равен $4 левая круглая скобка n плюс 1 правая круглая скобка$ у квадрата, внутри него находится $левая круглая скобка n минус 1 правая круглая скобка в квадрате$ белых клеток. Шаг индукции. Пусть периметр больше $4 левая круглая скобка n плюс 1 правая круглая скобка .$

Способ 1. Тогда найдётся клетчатая вертикаль или горизонталь, содержащая узлы, по обе стороны от которой есть чёрные клетки. Она содержит несколько интервалов внутренних белых клеток с концами в чёрных узлах. Выберем любой из этих интервалов, он разбивает чёрный контур на два контура меньшей длины. По предположению индукции внутри каждого из них число белых клеток сравнимо с 1, а на «разбивающем» интервале сравнимо с −1 по модулю n. Поэтому число белых клеток внутри исходного контура сравнимо с $1 плюс 1 минус 1=1 левая круглая скобка \bmod n правая круглая скобка .$

Рис. 1

Способ 2. Многоугольник M имеет выпуклые (90°) и невыпуклые (270°) углы. Назовём сторону многоугольника крайней, если она соединяет два равных угла этого многоугольника. Крайние стороны, очевидно, есть, пусть BC  — участок пути, соответствующий кратчайшей из них. Без ограничения общности можно считать, что он горизонтален, а ладья пришла в B снизу из ближайшего узла A и ушла из C вниз в ближайший узел D (см. рис. 1, где n  =  3).

Если из D контур поворачивает в сторону A (или из A в сторону D), то CD  — крайняя сторона. Значит, BC  =  CD, то есть ABCD  — минимальный квадрат, что противоречит рассматриваемому случаю.

В противном случае внутри «отрезка» AD нет других участков пути ладьи: такой участок обязан быть крайним (путь вверх из его концов невозможен), но это противоречит выбору BC. Таким образом, все клетки между A и D белые либо все они лежат вне многоугольника. Заменим часть пути ABCD «отрезком» AB. При этом многоугольник M потеряет (рис. 2), либо приобретет (рис. 3) белый прямоугольник высоты n, то есть, количество белых клеток по модулю n не изменится. (На рисунках красные клетки заведомо лежат вне многоугольника, а где лежат жёлтые клетки зависит от того, куда продолжается чёрный контур из точек A и D).

Рис. 2

Рис. 3

Критерии проверки:

Критерий	Оценка
Только идея, что ладья ходит по сетке из клеток $n \times n$	–.

Как ставились оценки:

—  «+» ставится за любое правильное решение;

—  «±» ставится за решение с существенным, но легко восполнимым пробелом;

—  «∓» ставится за неверное решение, однако с существенным продвижением;

—  «–» ставится за неверное решение;

—  «0» ставится, если задача не записана;

Решение · Критерии · Помощь

Тип 21 № 9217 Добавить в вариант

Петя прибавил к натуральному числу N натуральное число M и заметил, что сумма цифр у результата та же, что и у N. Тогда он снова прибавил M к результату, потом  — ещё раз, и т. д. Обязательно ли он когда-нибудь снова получит число с той же суммой цифр, что и у N?

(Александр Шаповалов)

Критерии проверки:

Критерий	Оценка
Только утверждается, и, возможно, доказано, что если М взаимно просто с 10, то когда-нибудь Петя снова получит число с такой же суммой цифр, как у N	−.
Ответ к пункту а)	3 б
Ответ к пункту б)	8 б.

Как ставились оценки:

—  «+» ставится за любое правильное решение;

—  «±» ставится за решение с существенным, но легко восполнимым пробелом;

—  «∓» ставится за неверное решение, однако с существенным продвижением;

—  «–» ставится за неверное решение;

—  «0» ставится, если задача не записана;

Решение · Критерии · Помощь

Тип 21 № 9218 Добавить в вариант

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

а)  N  =  2;

б)  N  =  3.

(Сергей Токарев)

Решение.

Можно считать, что детектор выдаёт сумму номиналов фальшивых купюр в проверяемом наборе. Первая проверка  — весь набор  — даст сумму S номиналов всех фальшивых.

а)  Вторая проверка  — все купюры, меньшие $дробь: числитель: S, знаменатель: 2 конец дроби ,$   — даст число X. В этом наборе ровно одна фальшивая, поэтому купюры с номиналами X и S − X фальшивые.

Замечание.

Во вторую проверку можно было взять по купюре из каждой пары с суммой S.

б)  Назовём купюры и числа, меньшие $дробь: числитель: S, знаменатель: 3 конец дроби ,$ мелкими, а остальные  — крупными. Вторая проверка  — все мелкие купюры  — даст число М. Теперь известна и сумма номиналов K  =  S − M крупных фальшивых купюр. Заметим, что фальшивые есть и среди мелких, и среди крупных купюр. Поэтому возможны два вида троек фальшивых купюр: (M₁, M₂, K), где числа M₁ и M₂  — мелкие с суммой M, и (M, K₁, K₂), где K₁ и K₂  — крупные с суммой K, а М  — мелкое.

Третья проверка  — все купюры, меньшие $дробь: числитель: M, знаменатель: 2 конец дроби ,$ и все крупные, меньшие $дробь: числитель: K, знаменатель: 2 конец дроби ,$   — даст число X. Видно, что в этом наборе ровно одна фальшивая купюра. Поэтому, если число X мелкое, то тройка фальшивых  — это (X, M − X, K), а если крупное, то  — (M, X, K − X).

Замечание.

Во вторую проверку можно взять наименьшую купюру от каждой тройки с суммой S. В третью проверку можно взять по одной купюре из каждой пары мелких с суммой M и из каждой пары крупных с суммой K.

Приведём другое решение пункта б).

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

Вторая проверка  — все купюры, номиналы которых попали в первый столбец таблицы. После этой проверки мы будем знать сумму номиналов некоторых купюр в «фальшивой» тройке. Пусть эта сумма равна S₂. В неё точно входит число из первого столбца, так как соответствующая купюра участвовала в проверке. Также в неё может входить число из второго столбца. А вот числа из третьего столбца в ней точно нет, поскольку все числа первого столбца меньше $дробь: числитель: S_1, знаменатель: 3 конец дроби ,$ а третьего  — больше $дробь: числитель: S_1, знаменатель: 3 конец дроби ,$ поэтому ни одно из чисел третьего столбца не может присутствовать в первом. Удалим из таблицы все строки, в которых ни первое число, ни сумма первого и второго не равны S₂.

Третья проверка  — все купюры, номиналы которых находятся во втором столбце оставшейся таблицы. Заметим, что в каждой строке либо первое число равно S₂ и тогда второе число больше S₂, либо сумма первого и второго числа равна S₂ и тогда первое число меньше $дробь: числитель: S_2, знаменатель: 2 конец дроби ,$ а второе  — больше $дробь: числитель: S_2, знаменатель: 2 конец дроби ,$ но меньше S₂. Значит, никакое число из первого столбца не может стоять во втором столбце. Кроме того, из этого следует, что все числа во втором столбце различны, иначе соответствующие тройки полностью совпадали бы.

Докажем, что и числа из третьего столбца не могли попасть во второй столбец. Предположим, что это не так, и в тройках (a₁, a₂, a₃) и (b₁, b₂, b₃) совпадают числа a₃ и b₂. Тогда $a_1 меньше a_2 меньше a_3=b_2 меньше b_3,$ а так как

$a_1 плюс a_2 плюс a_3=b_1 плюс b_2 плюс b_3=S_1,$

то $b_1 меньше a_1 меньше b_1 плюс b_2$ и $a_1 плюс a_2 больше b_1 плюс b_2 больше b_1.$ Это противоречит тому, что в обеих тройках есть числа с суммой S₂. Таким образом, результатом третьей проверки является номинал второй купюры в «фальшивой» тройке. А так как мы уже доказали, что во втором столбце нет равных чисел, то мы однозначно определим эту тройку.

Критерии проверки:

№	Критерий	Оценка
7а	Оценка не снижается за отсутствие обоснования и неявное использование того, что пары купюр с одинаковыми суммами номиналов не пересекаются
7б	Первой проверкой определяется S  — сумма номиналов всех фальшивых купюр. На вторую проверку берутся все купюры, являющиеся наименьшими во всевозможных тройках купюр с суммой номиналов S, или берутся все купюры с номиналами, меньшими $дробь: числитель: S, знаменатель: 3 конец дроби ,$ или аналогичное. Далее нет продвижений
	Факт: набор купюр может быть таким, что из него невозможно выбрать поднабор купюр со свойством «для всякой тройки купюр с суммой номиналов, равной сумме номиналов всех фальшивых купюр, ровно одна купюра из этой тройки имеется в поднаборе»	−.
	Ответ к пункту а)	3 б.
	Ответ к пункту б)	8 б.

Как ставились оценки:

—  «+» ставится за любое правильное решение;

—  «±» ставится за решение с существенным, но легко восполнимым пробелом;

—  «∓» ставится за неверное решение, однако с существенным продвижением;

—  «–» ставится за неверное решение;

—  «0» ставится, если задача не записана;

Решение · Критерии · Помощь

Тип 21 № 9222 Добавить в вариант

В клетчатом квадрате между каждыми двумя соседними по стороне клетками есть закрытая дверь. Жук начинает с какой-то клетки и ходит по клеткам, проходя через двери. Закрытую дверь он открывает в ту сторону, в которую идёт, и оставляет дверь открытой. Через открытую дверь жук может пройти только в ту сторону, в которую дверь была открыта. Докажите, что если жук в какой-либо момент захочет вернуться в исходную клетку, то он сможет это сделать.

(Александр Перепечко)

Критерии проверки:

Критерий	Оценка
Доказано только, что жук всегда может сделать ход, и/или что из прямоугольной клетчатой области (отличной от всего квадрата) можно выйти наружу из некоторой её клетки	−
Рассматривается некоторая «достаточно произвольная» подобласть клеток квадрата (например, произвольный цикл из клеток, по которому жук может пройти, или произвольная компонента сильной связности), и доказано, что из неё можно выйти наружу из некоторой её клетки	не менее ∓
Оценка не снижается за отсутствие доказательства того, что в графе смежности клеток нет мостов
Оценка не снижается за отсутствие доказательства того, что если все клетки разбиты на два непустых подмножества, то найдутся две различные пары соседних клеток, в которых одна клетка лежит в одном подмножестве, а другая  — в другом

Как ставились оценки:

—  «+» ставится за любое правильное решение;

—  «±» ставится за решение с существенным, но легко восполнимым пробелом;

—  «∓» ставится за неверное решение, однако с существенным продвижением;

—  «–» ставится за неверное решение;

—  «0» ставится, если задача не записана;

Решение · Критерии · Помощь

Тип 21 № 9225 Добавить в вариант

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

а)  N  =  201;

б)  N  =  400?

(Андрей Аржанцев)

Решение.

а)  Пусть площадь пиццы равна 201. Тогда площадь вписанного в неё квадрата равна $дробь: числитель: 402, знаменатель: Пи конец дроби больше 121.$ Нарисуем внутри пиццы квадрат со стороной 11 так, чтобы центры квадрата и пиццы совпали. Проведя по 12 разрезов, параллельных сторонам квадрата, получим 121 кусок $1 \times 1.$ Мысленно склеим куски пиццы вне квадрата и разобьём эту фигуру 40 разрезами через центр на 80 равновеликих кусков (в силу непрерывности это можно сделать, вращая диаметр). Всего хватило 64 разреза.

б)  Пусть площадь пиццы равна 400. Тогда площадь вписанного правильного шестиугольника равна $дробь: числитель: 600 корень из: начало аргумента: 3 конец аргумента , знаменатель: Пи конец дроби больше$ 294. Нарисуем внутри пиццы правильный шестиугольник площади 294 так, чтобы его центр и центр пиццы совпали. Отметим вершины и точки на сторонах шестиугольника так, чтобы каждая сторона разбилась на 7 равных частей. Если провести разрезы, параллельные сторонам шестиугольника через все отмеченные точки (всего таких разрезов 3 · 15  =  45), разобьём шестиугольник на 6 · 72  =  294 равных правильных треугольника площади 1. Мысленно склеим куски пиццы вне шестиугольника и разобьём эту фигуру 53 разрезами через центр на 106 равновеликих кусков. Всего хватило 98 разрезов.

Ответ: найдутся.

Замечание.

Количество разрезов можно сильно уменьшить, если воспользоваться следующей общей идеей. Положим пиццу нужной площади на единичную сетку, совместив центр пиццы с центром одной из клеток. Проведём все разрезы по линиям сетки, пересекающим пиццу. В результате она разрежется на единичные порции и кусочки по краям, составляющие каёмку. С каемкой поступим, как в вышеизложенном решении. Но по сравнению с ним площадь каемки сильно уменьшится и разрезов потребуется меньше. Например, в пункте а), положив пиццу на квадрат $15 \times 15$ и проведя 32 разреза по линиям сетки, мы обнаружим, что кроме квадрата $11 \times 11,$ она содержит ещё 56 клеток. Площадь каёмки будет равна 24, поэтому всего потребуется 32 + 12  =  44 разреза.

Критерии проверки:

№	Критерий	Оценка
7а	Только верный ответ	−
7б	Только верный ответ	−
	Ответ к пункту а)	5 б.
	Ответ к пункту б)	5 б.

Как ставились оценки:

—  «+» ставится за любое правильное решение;

—  «±» ставится за решение с существенным, но легко восполнимым пробелом;

—  «∓» ставится за неверное решение, однако с существенным продвижением;

—  «–» ставится за неверное решение;

—  «0» ставится, если задача не записана;

Решение · Критерии · Помощь

Тип 21 № 9827 Добавить в вариант

Существует ли целое $n больше 1,$ удовлетворяющее неравенству

$левая квадратная скобка корень из: начало аргумента: n минус 2 конец аргумента плюс 2 корень из: начало аргумента: n плюс 2 конец аргумента правая квадратная скобка меньше левая квадратная скобка корень из: начало аргумента: 9n плюс 6 конец аргумента правая квадратная скобка ?$

(Здесь [x] обозначает целую часть числа x, по есть наибольшее целое число, не превосходящее x.)

(М. Малкин)

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

Тип 21 № 9828 Добавить в вариант

В таблице $44 \times 44$ часть клеток синие, а остальные красные. Никакие синие клетки не граничат друг с другом по стороне. Множество красных клеток, наоборот, связно по сторонам (от любой красной клетки можно добраться до любой другой красной, переходя из клетки 6 клетку через общую сторону и не заходя с синие клетки). Докажите, что синих клеток 6 таблице меньше трети.

(Б. Френкин)

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

Тип 21 № 9830 Добавить в вариант

Назовём рассадку N кузнечиков на прямой в различные её точки k-удачной, если кузнечики, сделав необходимое число ходов по правилам чехарды, могут добиться того, что сумма попарных расстояний между ними уменьшится хотя бы в k раз. При каких $N больше или равно 2$ существует рассадка, являющаяся k-удачной сразу для всех натуральных k? (B чехарде за ход один из кузнечиков прыгает в точку, симметричную ему относительно другого кузнечика.)

(М. Святловский)

Решение.

При N  =  2 как бы кузнечики ни прыгали, расстояние между ними не меняется.

Пусть $N больше или равно 3.$ Рассадим 1-го, 2-го и 3-го кузнечиков на прямой в точках с координатами 0, 1, $корень из: начало аргумента: 2 конец аргумента ,$ назовём этих кузнечиков V, Q, R. Остальные произвольно рассаживаются в другие попарно различные точки. Покажем, что для всякого k кузнечики далее смогут прыгать так, чтобы сумма попарных расстояний уменьшилась хотя бы в k раз (исходную сумму обозначим через P).

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

Доказательство леммы. Покажем, что эти условия сохраняются при прыжке. Предположим, для некоторого кузнечика отношение расстояний до двух других рационально, тогда эти расстояния имеют вид a и aq, где q рационально. Тогда расстояние между другими двумя кузнечиками ненулевое и имеет вид $|a \pm a q|,$ тогда отношение любых двух расстояний между кузнечиками рационально, противоречие. Пусть какой-то кузнечик перепрыгнул через кузнечика A, тогда расстояния от A до обоих кузнечиков не изменились, а значит отношение этих расстояний осталось иррациональным, в частности расстояния различны, и потому кузнечики по-прежнему находятся в попарно-различных точках.

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

Пусть, не умаляя общности, в текущий момент минимально расстояние между кузнечиками V, Q с координатами a и b, а R имеет координату c. Отметим на прямой все точки с координатами, отличающимися от a на число, кратное (a – b). Понятно, что прыгая друг через друга кузнечики V, Q смогут занять любые две соседние отмеченные точки, тогда R не находится в отмеченной точке (по лемме прыгая только через друг друга V, Q, R остаются в попарно различных точках), тогда V, Q могут занять две соседние отмеченные точки между которыми лежит c, и расстояние от R до одного из кузнечиков будет не более $дробь: числитель: |a минус b|, знаменатель: 2 конец дроби ,$ то есть наименьшее расстояние уменьшилось хотя бы в 2 раза.

Тогда за несколько ходов кузнечики V, Q, R могут уменьшить наименьшее расстояние между ними хотя бы в 2 раза, потом за несколько ходов ещё хотя бы в 2 раза, потом ещё, и т. д, могут за несколько ходов добиться того, чтобы расстояние между какими-то двумя из них было равно некоторому числу t, меньшему $дробь: числитель: P, знаменатель: 2 N левая круглая скобка N минус 1 правая круглая скобка умножить на k конец дроби$   — пусть они так и сделают. Назовём каких-нибудь двух кузнечиков, между которыми расстояние t, хорошими, и одного из них назовём D, далее эти кузнечики уже не прыгают.

Далее, любой кузнечик не из пары хороших может прыгая через пару хороших (в подходящем порядке) смещаться на 2t в любую сторону на прямой, и тогда может за несколько прыжков через них оказаться на расстоянии меньшем $2 t$ от D, пусть все кузнечики кроме хороших сделают прыжки таким образом. Тогда расстояние от любого кузнечика до D будет меньше 2t, а значит, все попарные расстояния меньше 4t, а значит, их сумма меньше $4 t умножить на дробь: числитель: N левая круглая скобка N минус 1 правая круглая скобка , знаменатель: 2 конец дроби меньше дробь: числитель: P, знаменатель: k конец дроби .$

Ответ: при $N больше или равно 3.$

Приведем решение по идее Евгения Эндеки (11 класс, г. Барнаул).

Для любого $N больше 2$ предъявим явно начальную рассадку, которая является k-удачной для любого натурального числа k.

Сначала для данного $N больше 2$ построим конечную геометрическую прогрессию $1, q, \ldots, q в степени левая круглая скобка N минус 1 правая круглая скобка ,$ со знаменателем $q принадлежит левая круглая скобка 0, 1 правая круглая скобка ,$ для которой выполнено условие

$1 = q плюс q в квадрате плюс \ldots плюс q в степени левая круглая скобка N минус 1 правая круглая скобка .$

Требуемый набор существует при любом целом $N больше 2,$ поскольку уравнение

$q плюс q в квадрате плюс \ldots плюс q в степени левая круглая скобка N минус 1 правая круглая скобка минус 1 = 0$

имеет решение на интервале (0, 1), так как левая часть меняет знак на его концах.

Расположим теперь N кузнечиков в следующих начальных точках:

$0, 1, левая круглая скобка 1 плюс q правая круглая скобка , левая круглая скобка 1 плюс q плюс q в квадрате правая круглая скобка , \ldots, левая круглая скобка 1 плюс q плюс \ldots плюс q в степени левая круглая скобка N минус 3 правая круглая скобка правая круглая скобка , левая круглая скобка 1 плюс q плюс \ldots плюс q в степени левая круглая скобка N минус 2 правая круглая скобка правая круглая скобка .$

Рассмотрим прыжок первого кузнечика через второго; тогда его новая координата будет равна

$2 = 1 плюс 1 = 1 плюс q плюс q в квадрате плюс \ldots плюс q в степени левая круглая скобка N минус 1 правая круглая скобка .$

Получилось, что прыгнувший кузнечик стал самым правым, а все кузнечики теперь расположены в точках

$1, левая круглая скобка 1 плюс q правая круглая скобка , левая круглая скобка 1 плюс q плюс q в квадрате правая круглая скобка , \ldots, левая круглая скобка 1 плюс q плюс \ldots плюс q в степени левая круглая скобка N минус 2 правая круглая скобка правая круглая скобка , левая круглая скобка 1 плюс q плюс \ldots плюс q в степени левая круглая скобка N минус 1 правая круглая скобка правая круглая скобка .$

Сдвинув начало координат на 1 вправо, получим координаты кузнечиков

$0, q, левая круглая скобка q плюс q в квадрате правая круглая скобка , \ldots, левая круглая скобка q плюс \ldots плюс q в степени левая круглая скобка N минус 2 правая круглая скобка правая круглая скобка , левая круглая скобка q плюс \ldots плюс q в степени левая круглая скобка N минус 1 правая круглая скобка правая круглая скобка .$

Таким образом, кузнечики уменьшили свои координаты ровно в q раз. Если указанный шаг (прыжок самого левого кузнечика через ближайшего соседа) повторять r раз, то попарные расстояния изменятся в q^r раз, что позволит достичь любого нужного уменьшения $дробь: числитель: 1, знаменатель: K конец дроби .$

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

Тип 21 № 9831 Добавить в вариант

В ряд слева направо стоят N коробок, занумерованных подряд числами $1, 2, \ldots, N.$ В некоторые коробки, стоящие подряд, положат по шарику, оставив остальные пустыми. Инструкция состоит из последовательно выполняемых команд вида «поменять местами содержимое коробок №і и №j», где і и j  — числа. Для каждого ли N существует инструкция, в которой не больше 100N команд, со свойствам: для лобой начальной раскладки указанного вида можно будет, вычеркнув из инструкции некоторые команды, получить инструкцию, после выполнения которой все коробки с шариками будут левее коробок без шариков?

(И. Митрофанов)

Решение.

Давайте считать, что все шарики синие. В пустые коробки положим по красному шарику. Теперь пустых коробок нет. Покажем даже более сильное утверждение: что для любого N есть инструкция не длиннее чем 3N со следующим свойством.

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

Понятно, что для N  =  1 такая инструкция есть. Покажем, как из инструкции для $k больше или равно 1$ сделать инструкцию для 2k и для 2k – 1, этого будет достаточно. Обозначим N  =  2k или 2k – 1.

Инструкция для N будет выглядеть следующим образом.

I группа: сначала все пары вида $левая круглая скобка i, k плюс i правая круглая скобка$ в любом порядке. Если N нечетно, сюда приходится добавить все пары вида $левая круглая скобка i плюс 1, i плюс k правая круглая скобка$ при $i больше или равно 1$ (назовём эти команды дополнительными).

II группа: инструкция для k первых коробочек из индукционного предположения

III группа: все пары различных чисел вида $левая круглая скобка i, N плюс 1 минус i правая круглая скобка$ в любом порядке.

При N  =  2k длина этой инструкции не превышает

$k плюс 3 k плюс k=5 k меньше или равно 3 N.$

При $N=2 k минус 1$ длина этой инструкции не превышает

$2 левая круглая скобка k минус 1 правая круглая скобка плюс 3 k плюс левая круглая скобка k минус 1 правая круглая скобка =6 k минус 3=3 N.$

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

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

1.  Они идут подряд, и все они среди левых k коробок  — ничего делать не надо.

2.  Они идут подряд, и все они среди правых коробок  — используем все пары вида $левая круглая скобка i, k плюс i правая круглая скобка .$

3.  Они есть и среди левых k коробок, и среди остальных правых, при этом они идут подряд. Заметим, что ни в какой паре вида $левая круглая скобка i, i плюс k правая круглая скобка$ нет двух камней основного цвета. Все основные камни тогда перенесем справа налево (тогда камни не основного цвета будут среди первых k камней лежать подряд.

4.  Камни основного цвета  — самые первые и самые последние. Перенеся последние влево (при нечётном N используя дополнительные операции), получаем требуемое. (Про это всё проще думать, если мыслить расположение коробочек не в ряд, а по окружности.)

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

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

Ответ: да.

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

Тип 21 № 9844 Добавить в вариант

Авантюрист прибыл на остров, где живёт племя аборигенов, и пытается понять их язык. На данный момент ему известно следующее.

1.  В языке всего две буквы A и B, каждая последовательность букв образует слово, у которого есть некоторое значение;

2.  Несмотря на то, что слов бесконечно много, значений у слов конечное количество;

Авантюрист придумал обозначение для слов, имеющих одинаковое значение: он стал писать между ними знак равенства «=».

3.  Если ω₁  =  ω₂, то для любых слов s и t выполнены равенства

$s \omega_1 t = s \omega_2 t,$ $s \omega_1 = s \omega_2,$ $\omega_1t = \omega_2t$

(для слов x и y под xy понимается слово, полученное приписыванием к слову x справа слова y); другими словами, если в некотором слове заменить его подслово на слово с тем же значением, то значение слова от этого не изменится. Докажите, что если ABB  =  B, то BAB  =  B.

Решение · Критерии · Помощь

Тип 21 № 10206 Добавить в вариант

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

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

Тип 21 № 10213 Добавить в вариант

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

Решение · Критерии · Помощь

Тип 21 № 10325 Добавить в вариант

В турнире по футболу играли несколько команд. Каждые две команды сыграли один матч. За победу давали два очка, за ничью  — одно очко, за проигрыш  — ничего. После турнира выяснилось чем больше очков у команды, тем меньше голов она забила (суммарно за весь турнир) и тем больше голов пропустила. Какое наименьшее количество команд могло быть?

Решение · Критерии · Помощь

Всего: 115 … 21–40 | 41–60 | 61–80 | 81–100 | 101–115

Случай чётного n	3 балла
Случай нечётного n	4 балла
Приведена только идея разбиения участников на пары	1 балл