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

Поиск
?

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

Всего: 42 1–20 | 21–40 | 41–42

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

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

В строку записано 2020 натуральных чисел. Каждое из них, начиная с третьего, делится и на предыдущее, и на сумму двух предыдущих. Какое наименьшее значение может принимать последнее число в строке?

(А. Грибалко)

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

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

На высотах AA₀, BB₀, CC₀ остроугольного неравностороннего треугольника ABC отметили соответственно точки A₁, B₁, C₁ так, что $AA_1 = BB_1 = CC_1 = R,$ где R  — радиус описанной окружности треугольника ABC. Докажите, что центр описанной окружности треугольника $A_1B_1C_1$ совпадает с центром вписанной окружности треугольника ABC.

(Е. Бакаев)

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

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

На клетчатой плоскости отметили 40 клеток. Всегда ли найдётся клетчатый прямоугольник, содержащий ровно 20 отмеченных клеток?

(М. Евдокимов)

Решение.

I способ. Рассмотрим клетчатый квадрат размером $11 \times 11$ и удалим из него внутренний центральный квадрат $9 \times 9,$ оставив только рамку толщиной 1. В рамке будет как раз 40 клеток. Докажем, что на плоскости нет клетчатого прямоугольника, содержащего ровно 20 из этих 40 клеток.

Допустим, такой прямоугольник есть. Пусть в нём есть клетки из обеих вертикальных сторон рамки. Тогда каждая горизонтальная сторона рамки либо полностью включена в прямоугольник, либо вовсе не включена. Если включена ровно одна горизонтальная сторона, число клеток в прямоугольнике нечётно, если обе  — клеток 40 (слишком много), а если ни одной  — клеток максимум $9 плюс 9=18$ (слишком мало).

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

Ответ: Нет.

II способ. Рассмотрим клетчатый прямоугольник $левая квадратная скобка 1,14 правая квадратная скобка \times левая квадратная скобка 1,3 правая квадратная скобка ,$ и удалим из него клетки $левая круглая скобка 7, 1 правая круглая скобка$ и $левая круглая скобка 7, 3 правая круглая скобка .$ Останется ровно 40 клеток. Предположим, что нашёлся клетчатый прямоугольник, в котором ровно 20 отмеченных клеток. Он может затрагивать одну, две или три горизонтали с номерами 1, 2, 3. Если он затрагивает одну горизонталь, то в нём не более 14 отмеченных клеток. Если он задевает 2 горизонтали (одна из них  — вторая), то он задевает вертикаль с номером 7 (иначе в нём не более 14 клеток). Тогда эта вертикаль вносит в прямоугольник нечётное число отмеченных клеток, а остальные чётное. Поэтому общее число отмеченных клеток в прямоугольнике нечётно.

Если он задевает все три горизонтали, то число отмеченных клеток в нём либо кратно 3 (если он не задевает 7-й вертикали), либо имеет остаток 1 при делении на 3 (иначе). В каждом из случаев получаем противоречие.

Замечание. Возможны другие решения. Например, подходит квадрат $7 \times 7$ с вырезанным центральным квадратом $3 \times 3,$ но доказательство более длинное.

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

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

Для бесконечной последовательности $a_1, a_2, ...$ её первая производная  — это последовательность $a′n=a_n плюс 1 минус a_n,$ (где $n=1, 2, ... правая круглая скобка ,$ а её k-я производная  — это первая производная её (k−1)-й производной $левая круглая скобка k = 2, 3, ... правая круглая скобка .$ Назовём последовательность хорошей, если она и все её производные состоят из положительных чисел. Докажите, что если $a_1, a_2, ...$ и $b_1, b_2, ...$   — хорошие последовательности, то и $a_1 умножить на b_1, a_2 умножить на b_2,...$   — хорошая последовательность.

(Р. Салимов)

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

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

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

(А. Заславский)

Решение.

I способ. Пусть O  — центр сферы, а ABC  — данный сферический треугольник. По формуле площади сферического треугольника

$Пи =S_A B C=\angle A плюс \angle B плюс \angle C минус Пи ,$

то есть $\angle A плюс \angle B плюс \angle C=2 Пи .$ (Доказательство формулы площади заключается в применении формулы включений-исключений к трем полусферам, пересечением которых является данный треугольник.)

Построим на сфере точку D, лежащую с C в разных полуплоскостях относительно OAB, и такую, что $\angle D A B=\angle C B A$ и $\angle D B A=\angle C A B$ (имеются в виду сферические углы; иначе говоря, точка D получена из C композицией симметрии относительно $O A B$ и симметрии относительно серединного перпендикуляра к AB). Тогда треугольники ABC и BAD равны. Значит, $B D=A C$ и $A D=B C .$ Но из условия имеем

$\angle D A C=\angle D B C=\angle A C B,$

следовательно, сферические треугольники $C D A$ и $D C B$ также равны треугольнику $A B C.$ Четыре полученных треугольника покрывают сферу.

II способ. Пусть A, B, C  — вершины данного треугольника. Покажем, что треугольник ABC остроугольный. Действительно, пусть $\angle A C B больше или равно дробь: числитель: Пи , знаменатель: 2 конец дроби .$ Если плоскость $альфа =A B C$ содержит центр O сферы, то сферический треугольник ABC вырожден, и его площадь не такая, как надо. Иначе $альфа$ отрезает от сферы «шапочку» площади меньше полусферы. Далее, прямая AB (нестрого) разделяет C и проекцию O на $A B C;$ значит, часть шапочки, отсекаемая плоскостью OAB и содержащая C, не больше её половины. Наконец, сферический треугольник $A B C$ лежит в этой области, площадь которой меньше четверти площади сферы  — противоречие.

Итак, треугольник ABC остроугольный; тогда существует равногранный тетраэдр ABCD (точки D и O лежат в одной полуплоскости относительно ABC). Пусть $O в степени левая круглая скобка \prime правая круглая скобка$   — центр этого равногранного тетраэдра. Тогда телесные углы $O в степени левая круглая скобка \prime правая круглая скобка A B C,$ $O в степени левая круглая скобка \prime правая круглая скобка B C D,$ $O в степени левая круглая скобка \prime правая круглая скобка C D A,$ $O в степени левая круглая скобка \prime правая круглая скобка D A B$ разбивают пространство, то есть каждый из них равен четверти площади единичной сферы. Однако, если $O в степени левая круглая скобка \prime правая круглая скобка$ ближе в ABC, чем O, то этот телесный угол больше, чем OABC, а если $O в степени левая круглая скобка \prime правая круглая скобка$ дальше  — то меньше. Оба случая невозможны; значит, $O=O в степени левая круглая скобка \prime правая круглая скобка ,$ и упомянутые телесные углы дают требуемое разбиение сферы на 4 части.

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

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

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

(И. Богданов)

Решение.

I способ. Присвоим цветам остатки $0,1,2$ от деления на 3 произвольным образом. Все операции с ними также будем производить по модулю 3. Тогда операция, производимая роботом, такова: если уничтожаются кубики цветов a и b, то появляется кубик цвета $минус a минус b.$

Если $N=2 в степени левая круглая скобка k правая круглая скобка ,$ то после каждого прохода полного круга количество кубиков уменьшается вдвое, а их сумма меняет знак. Значит, в конце получится кубик цвета $левая круглая скобка минус 1 правая круглая скобка в степени левая круглая скобка k правая круглая скобка левая круглая скобка a_1 плюс \ldots плюс a_N правая круглая скобка ,$ вне зависимости от места старта. Мы доказали, что степени двойки удачны.

Если $N=2 в степени левая круглая скобка k правая круглая скобка плюс d,$ где $1 меньше или равно d меньше или равно 2 в степени левая круглая скобка k правая круглая скобка минус 1,$ то рассмотрим расстановку из одного красного кубика и $N минус 1$ белого. Если робот стартует перед красным кубиком, то после d ходов останутся один синий кубик и $2 в степени левая круглая скобка k правая круглая скобка минус 1$ белых. Если робот стартует непосредственно после красного кубика, то через d ходов останутся один красный кубик и $2 в степени левая круглая скобка k правая круглая скобка минус 1$ белых. Вышеприведенные аргументы для степени двойки показывают, что в этих двух ситуациях итоговые цвета будут разными, то есть N неудачно.

Ответ: Степени двойки.

II способ. Заметим сразу, что, если чётное число N удачно, то и $дробь: числитель: N, знаменатель: 2 конец дроби$ тоже. Действительно, если в расстановке N кубиков робот будет начинать только с чётных позиций, то после $дробь: числитель: N, знаменатель: 2 конец дроби$ ходов он будет получать одну и ту же расстановку, в которой он стоит на всевозможных позициях. Поскольку каждая расстановка $дробь: числитель: N, знаменатель: 2 конец дроби$ кубиков может быть получена таким образом, получаем требуемое.

Рассмотрим две расстановки, отличающиеся ровно в одном месте. Запустим в них по роботу параллельно; тогда получающиеся расстановки всегда будут отличаться ровно в одном месте. В частности, итоговые цвета будут различны.

Отсюда уже следует, что все нечётные $N=2 k плюс 1 больше 1$ (а значит, по замечанию, и все N, кроме степеней двойки) неудачны. Действительно, начнём с расстановки с одним красным и $2 k$ белыми кубиками. Если робот стоял перед красным кубиком, через $k плюс 1$ ход останутся один красный и $k минус 1$ белый кубик, робот стоит после красного. Если же робот стартует непосредственно после красного, через $k плюс 1$ ход останутся один синий и $k минус 1$ белых кубиков, робот стоит непосредственно после синего. Как показано выше, итоговые цвета в этих двух ситуациях будут разными.

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

$В arrow К arrow С arrow Б,$

то после одного использования цвет сдвинется в противоположную сторону. Значит, если $N=2 в степени левая круглая скобка k правая круглая скобка ,$ любая такая замена исходного кубика приведёт к сдвигу цвета итогового кубика в одну и ту же сторону. Осталось заметить, что две расстановки, отличающиеся поворотом, получаются из расстановки всех белых кубиков за одинаковое количество замен «вперёд по циклу».

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

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

В первый день 2ⁿ школьников играли в пинг-понг «навылет»: сначала сыграли двое, затем победитель сыграл с третьим, победитель этой пары  — с четвёртым и т. д., пока не сыграл последний школьник (ничьих в пинг-понге не бывает). Во второй день те же школьники разыграли кубок: сначала произвольно разбились на пары и сыграли в парах, проигравшие выбыли, а победители снова произвольно разбились на пары и сыграли в парах, и т. д. Оказалось, что наборы игравших пар в первый и во второй день были одни и те же (возможно, победители были другие). Найдите наибольшее возможное значение n.

(Б. Френкин)

Решение.

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

Теперь рассмотрим тот же граф как граф кубкового турнира. Если из него выбросить висячие вершины, останется граф турнира на $2 в степени левая круглая скобка n минус 1 правая круглая скобка$ победителях первого этапа. Он, очевидно, является путём лишь при $n меньше или равно 3,$ в противном случае победитель турнира будет иметь степень не меньше 3. Значит, $n меньше или равно 3 .$

Осталось привести пример при $n=3 .$ Пусть участники пронумерованы от 1 до 8 и пары в кубке таковы (первым указан проигравший, вторым победитель): 1−2, 3−4, 5−6, 7−8, 2−4, 6−8, 4−8. тогда при игре навылет пары могли быть такими (победитель снова указан вторым): 1−2, 2−4, 3−4, 4−8, 7−8, 8−6, 6−5 .

Ответ: 3.

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

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

Сфера касается 99 рёбер некоторой выпуклой 50-угольной пирамиды. Обязательно ли тогда она касается и 100-го ребра этой пирамиды?

(М. Евдокимов)

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

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

Для положительных чисел $x_1, ..., x_n$ докажите неравенство:

$левая круглая скобка дробь: числитель: x_1, знаменатель: x_2 конец дроби правая круглая скобка в степени 4 плюс левая круглая скобка дробь: числитель: x_2, знаменатель: x_3 конец дроби правая круглая скобка в степени 4 плюс ... плюс левая круглая скобка дробь: числитель: x_n, знаменатель: x_1 конец дроби правая круглая скобка в степени 4 больше или равно дробь: числитель: x_1, знаменатель: x_5 конец дроби плюс дробь: числитель: x_2, знаменатель: x_6 конец дроби плюс ... плюс дробь: числитель: x_n минус 3, знаменатель: x_1 конец дроби плюс дробь: числитель: x_n минус 2, знаменатель: x_2 конец дроби плюс дробь: числитель: x_n минус 1, знаменатель: x_3 конец дроби плюс дробь: числитель: x_n, знаменатель: x_4 конец дроби .$ $левая круглая скобка дробь: числитель: x_1, знаменатель: x_2 конец дроби правая круглая скобка в степени 4 плюс левая круглая скобка дробь: числитель: x_2, знаменатель: x_3 конец дроби правая круглая скобка в степени 4 плюс ... плюс левая круглая скобка дробь: числитель: x_n, знаменатель: x_1 конец дроби правая круглая скобка в степени 4 больше или равно дробь: числитель: x_1, знаменатель: x_5 конец дроби плюс$
$плюс дробь: числитель: x_2, знаменатель: x_6 конец дроби плюс ... плюс дробь: числитель: x_n минус 3, знаменатель: x_1 конец дроби плюс дробь: числитель: x_n минус 2, знаменатель: x_2 конец дроби плюс дробь: числитель: x_n минус 1, знаменатель: x_3 конец дроби плюс дробь: числитель: x_n, знаменатель: x_4 конец дроби .$

(М. Фадин)

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

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

Клетки доски 100 × 100 раскрашены в чёрный и белый цвета в шахматном порядке. Можно ли перекрасить ровно 2018 различных клеток этой доски в противоположный цвет так, чтобы в каждой строке и в каждом столбце оказалось одно и то же количество чёрных клеток?

(Ю. Чеканов)

Решение.

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

Пусть после перекраски в каждой строке и каждом столбце оказалось по $50 плюс k$ чёрных клеток; тогда в каждом столбце и в каждой строке перекрашено на k белых клеток больше, чем чёрных. Пусть в одном из чёрных квадратов перекрашено а клеток. По замечанию выше, в каждом из белых квадратов перекрашено по $a плюс 50 k$ клеток, а тогда в другом чёрном квадрате также перекрашено $левая круглая скобка a плюс 50 k правая круглая скобка минус 50 k=a$ клеток. Значит, общее число перекрашенных клеток равно

$2 a плюс 2 левая круглая скобка a плюс 50 k правая круглая скобка =4 левая круглая скобка a плюс 25 k правая круглая скобка ,$

то есть оно делится на 4 и потому не может равняться 2018.

Решение 2. Пронумеруем строки снизу вверх, а столбы справа налево, числами от 1 до 100 (пусть левая нижняя клетка чёрная). Тогда у каждой чёрной клетки чётная сумма координат, a у каждой белой  — нечётная.

Рассмотрим сумму координат всех чёрных клеток (до или после перекраски). Поскольку в каждой строке их поровну, сумма их ординат делится на $1 плюс 2 плюс \ldots плюс 100=5050,$ аналогично сумма абсцисс также делится на 5050. В частности, эта сумма до и после перекраски была чётной, то есть изменилась на чётное число.

С другой стороны, при перекраске исходно чёрной клетки в белый цвет наша сумма чётности не меняла, а при перекраске исходно белой в чёрный  — меняла. Это значит, что было перекрашено чётное количество белых клеток.

Пусть w и b  — количества перекрашенных исходно белых и исходно чёрных клеток, соответственно. Тогда $w плюс b=2018,$ а $w минус b$ делится на 4, поскольку как исходное, так и полученное количество чёрных клеток делится на 4. Значит,

$w= дробь: числитель: левая круглая скобка левая круглая скобка w плюс b правая круглая скобка плюс левая круглая скобка w минус b правая круглая скобка правая круглая скобка , знаменатель: 2 конец дроби$

нечётное число. Противоречие.

Ответ: нет.

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

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

Дан треугольник XBC. Различные точки $A_H,$ $A_I,$ A_m таковы, что X является ортоцентром треугольника $A_HBC,$ центром вписанной окружности треугольника A_IBC и точкой пересечения медиан треугольника $A_MBC.$ Докажите, что если $A_HA_M$ и BC параллельны, то A_I  — середина $A_HA_M.$

(Е. Бакаев)

Решение.

Пусть M  — середина BC, а Y и Z  — точки, симметричные X относительно прямой BC и точки M, соответственно. Тогда

$\angle B Z C=\angle B Y C=\angle B X C=180 в степени левая круглая скобка \circ правая круглая скобка минус \angle B A_H C,$

откуда точки $A_H,$ B, C, Y и Z лежат на одной окружности $\Omega$ c центром O и радиусом R. При этом, поскольку $A_H A_M \| B C$ и $A_M X: X M=2,$ получаем

$A_H X: X Y=A_M X: 2 X M=1,$

то есть X  — середина $A_H Y.$

Пусть T  — середина YZ. Тогда OTYX  — прямоугольник, поэтому $T X=O Y=R .$ Из симметрии относительно BC получаем, что

$O B=O C=T B=T C=R.$

Значит, T  — центр окружности, описанной около треугольника BXC, то есть, по лемме о трезубце, середина дуги BC окружности $левая круглая скобка A_I B C правая круглая скобка .$

Пусть $K=A_H Y \cap B C,$ $Y Y в степени левая круглая скобка \prime правая круглая скобка$   — диаметр окружности $\Omega,$ а P и S  — середины KM и $A_H A_M,$ соответственно. Заметим, что

$Y Z=2 K M=A_H A_M=A_H Y в степени левая круглая скобка \prime правая круглая скобка .$

Значит, TX пересекает отрезки $K M$ и $A_H A_M$ в их серединах P и S, а также $P=Y Y в степени левая круглая скобка \prime правая круглая скобка \cap B C .$ Тогда

$B P умножить на P C=Y P умножить на P Y в степени левая круглая скобка \prime правая круглая скобка =T P умножить на P S$

(последнее равенство выполнено в силу симметрии отрезков $Y Y в степени левая круглая скобка \prime правая круглая скобка$ и TS относительно перпендикуляра к BC в точке P). Значит, TBSC  — вписанный четырёхугольник, как и $T B A_I C.$ Поскольку $A_I$ и S лежат на $T X,$ отсюда следует $A_I=S.$

Замечание. На последнем шаге можно действовать и по-другому. Пусть $K=A_H Y \cap B C,$ а S  — середина $A_H A_M .$ Пусть $K_M$ и $K_X$   — точки, симметричные K относительно M и X соответственно. Тогда в треугольнике $A_I B C$ точка $K_M$   — точка касания вневписанной окружности с $B C,$ а $K_X$   — точка вписанной окружности, диаметрально противоположная K. При гомотетии с центром $A_I,$ переводящей вневписанную во вписанную, эти точки переходят друг в друга  — значит, $A_I$ лежит на $K_M K_X .$ Осталось заметить, что $K_M K_X$ проходит через S, поскольку

$K_X K: K_X A_H=K K_M: A_H S=2 ,$

так что $A_I=K_M K_X \cap T X=S .$

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

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

Для каких натуральных n верно следующее утверждение: для произвольного многочлена P степени n с целыми коэффициентами найдутся такие различные натуральные a и b, для которых $P левая круглая скобка a правая круглая скобка плюс P левая круглая скобка b правая круглая скобка$ делится на a + b?

(Г. Жуков)

Решение.

Нечётные n не подходят. В самом деле, рассмотрим многочлен $P левая круглая скобка x правая круглая скобка =x в степени левая круглая скобка n правая круглая скобка плюс 1$ и различные натуральные $a, b .$ Так как n нечётно, $a в степени левая круглая скобка n правая круглая скобка плюс b в степени левая круглая скобка n правая круглая скобка$ делится на $a плюс b,$ а тогда

$P левая круглая скобка a правая круглая скобка плюс P левая круглая скобка b правая круглая скобка = левая круглая скобка a в степени левая круглая скобка n правая круглая скобка плюс b в степени левая круглая скобка n правая круглая скобка правая круглая скобка плюс 2$

не делится, поскольку $a плюс b больше 2$

Осталось доказать, что все чётные n подходят. Рассмотрим произвольный многочлен $P левая круглая скобка x правая круглая скобка$ степени n. Представим его в виде суммы $P левая круглая скобка x правая круглая скобка =P_0 левая круглая скобка x правая круглая скобка плюс P_1 левая круглая скобка x правая круглая скобка ,$ где в $P_0 левая круглая скобка x правая круглая скобка$ все мономы чётной степени, в в $P_1 левая круглая скобка x правая круглая скобка$   — нечётной. Заметим, что при всех натуральных a, b сумма $P_1 левая круглая скобка a правая круглая скобка плюс P_1 левая круглая скобка b правая круглая скобка$ делится на $a плюс b.$ Докажем, что найдутся такие a, b, что и $P_0 левая круглая скобка a правая круглая скобка плюс P_0 левая круглая скобка b правая круглая скобка$ делится на $a плюс b.$ Заметим, что степень $P_0$ равна n.

Рассмотрим случай, когда старший коэффициент $P_0 левая круглая скобка x правая круглая скобка$ положителен (в случае отрицательного старшего коэффициента проведём дальнейшее доказательство для многочлена $минус P_0 левая круглая скобка x правая круглая скобка правая круглая скобка .$ Так как $n больше 1,$ то найдётся такое натуральное m, что $P_0 левая круглая скобка m правая круглая скобка больше 2 m .$ Докажем, что $a=m,$ $b=P_0 левая круглая скобка m правая круглая скобка минус m$ подходят. В силу выбора m, они обе натуральные, причём $b больше a.$ Далее, по модулю $a плюс b=P_0 левая круглая скобка m правая круглая скобка$ выполняются сравнения $P_0 левая круглая скобка a правая круглая скобка =P_0 левая круглая скобка m правая круглая скобка \equiv 0$ (очевидно) и

$P_0 левая круглая скобка b правая круглая скобка =P_0 левая круглая скобка левая круглая скобка b плюс a правая круглая скобка минус a правая круглая скобка \equiv P_0 левая круглая скобка минус a правая круглая скобка =P_0 левая круглая скобка m правая круглая скобка \equiv 0$

(в силу чётности многочлена $P_0 правая круглая скобка .$ Значит, $P_0 левая круглая скобка a правая круглая скобка плюс P_0 левая круглая скобка b правая круглая скобка \equiv 0$ $левая круглая скобка \bmod a плюс b правая круглая скобка ,$ что и требовалось.

Замечание. В случае чётного п можно проделать подобное рассуждение и без разбиения на чётную и нечётную компоненты. Поскольку степень многочлена $P левая круглая скобка x правая круглая скобка плюс P левая круглая скобка минус x правая круглая скобка$ равна $n больше 1,$ существует такое натуральное m, что $P левая круглая скобка m правая круглая скобка плюс P левая круглая скобка минус m правая круглая скобка больше 2 m .$ Тогда подойдут числа $a=m,$ $b=P левая круглая скобка m правая круглая скобка плюс P левая круглая скобка минус m правая круглая скобка минус m .$ Действительно, тогда $b больше a больше 0,$ и по модулю $a плюс b=P левая круглая скобка m правая круглая скобка плюс P левая круглая скобка минус m правая круглая скобка$ верно сравнение

$P левая круглая скобка a правая круглая скобка плюс P левая круглая скобка b правая круглая скобка \equiv P левая круглая скобка a правая круглая скобка плюс P левая круглая скобка минус a правая круглая скобка =P левая круглая скобка m правая круглая скобка плюс P левая круглая скобка минус m правая круглая скобка \equiv 0 .$

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

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

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

Хозяйка испекла квадратный торт и отрезала от него несколько кусков. Первый разрез проведён параллельно стороне исходного квадрата от края до края. Следующий разрез проведён в оставшейся части от края до края перпендикулярно предыдущему разрезу, далее аналогично (сколько-то раз). Все отрезанные куски имеют равную площадь. Может ли оставшаяся часть торта быть квадратом?

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

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

Пусть X  — некоторая фиксированная точка на стороне AC треугольника ABC (X отлична от A и C). Произвольная окружность, проходящая через X и B, пересекает отрезок AC и описанную окружность треугольника ABC в точках P и Q, отличных от X и B. Докажите, что все возможные прямые PQ проходят через одну точку.

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

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

16 карточек с целыми числами от 1 до 16 разложены лицевой стороной вниз в виде таблицы 4 × 4 так, что карточки, на которых записаны соседние числа, лежат рядом (соприкасаются по стороне). Какое наименьшее число карточек нужно одновременно перевернуть, чтобы наверняка определить местоположение всех чисел (как бы ни были разложены карточки)?

Решение.

Оценка. Занумеруем клетки, как показано на рисунке 1. Заметим, что одна из клеток с номером 1 должна быть открыта, иначе красный и синий способы заполнения таблицы на рисунке 2 были бы неразличимы. Одна из клеток с номером 2 также должна быть открыта, иначе красный и синий способы заполнения таблицы на рисунке 3 были бы неразличимы.

Аналогично, должны быть открыты хотя бы по одной из клеток с номерами 3, 4, 5, 6, 7, 8, то есть должно быть открыто не менее 8 карточек.

Рис. 1.

Рис. 2.

Рис. 3.

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

Заметим, что если в угол ведёт ребро, то мы восстановим число в нём. Если же в угловую клетку не ведёт ребро, то в ней стоит крайнее число, то есть 1 или 16, а так как мы знаем чётность числа в каждой клетке, то в этом случае мы тоже восстановим число в углу. Итак, числа в углах заведомо восстановлены.

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

Таким образом, мы восстановили числа во всех клетках.

Ответ: восемь карточек.

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

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

Имеется натуральное 1001-значное число A. Где 1001-значное число Z  — то же число A, записанное от конца к началу (например, для четырёхзначных чисел это могли быть 7432 и 2347). Известно, что A > Z. При каком A частное $дробь: числитель: A, знаменатель: Z конец дроби$ будет наименьшим (но строго больше 1)?

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

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

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

Решение.

Возьмём в горизонтальной плоскости $альфа$ правильный треугольник с высотой 2. Пусть J  — центр одной из его вневписанных окружностей, а A, B, C  — середины его сторон.

Выберем такие сферы: три с центрами в A, B, C радиуса 1; две радиуса 2 с центрами в точках $J в степени левая круглая скобка \prime правая круглая скобка$ и $J в степени левая круглая скобка \prime \prime правая круглая скобка ,$ получающихся из J поднятием и опусканием относительно $альфа$ на 1.

Теперь осталось провести требуемые плоскости. Плоскость через $J',$ параллельная $альфа ,$ касается четырёх остальных сфер; для $J в степени левая круглая скобка \prime \prime правая круглая скобка$ аналогично. Осталось провести плоскость, скажем, через A; она перпендикулярна $альфа$ и содержит сторону треугольника, на которой лежит A. Все проверки достаточно просты.

Ответ: да, можно.

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

Центр сферы $S_0$ поместим в точке $A_0$ с координатами (0, 0, 0), радиус r этой сферы выберем позже. Остальные сферы $S_i,$ $i=1, 2, 3, 4$ возьмем радиуса 1, а центры этих сфер поместим в точки $A_1 левая круглая скобка a, 0, 1 правая круглая скобка ,$ $A_2 левая круглая скобка минус a, 0, 1 правая круглая скобка ,$ $A_3 левая круглая скобка 0, a, минус 1 правая круглая скобка ,$ $A_4 левая круглая скобка 0, минус a, минус 1 правая круглая скобка$ (a выберем позже).

Плоскость Оху проходит через $A_0$ и касается сфер $S_i,$ $i=1, 2, 3, 4.$ Можно подобрать a так, чтобы плоскость $A_2 A_3 A_4$ находилась на расстоянии $\varrho_1=1$ от точки $A_1,$ тогда плоскость $\sigma_1,$ проходящая через $A_1$ и параллельная плоскости $A_2 A_3 A_4,$ будет касаться сфер $S_i,$ $i=2, 3, 4.$ Действительно, уравнение плоскости

$A_2 A_3 A_4: 2 x плюс a z плюс a=0 .$

Тогда $\varrho_1= дробь: числитель: 4 a, знаменатель: корень из: начало аргумента: 4 плюс a в степени левая круглая скобка 2 конец аргумента правая круглая скобка конец дроби$ и достаточно положить $a= корень из: начало аргумента: дробь: числитель: 4, знаменатель: 15 конец дроби конец аргумента .$ $S_0.$

Положим r равным расстоянию от A₀ до плоскости $дельта _1,$ так, чтобы плоскость $дельта _1,$ касалась также и сферы S₀.

Конструкция переводится в себя при симметрии относительно плоскостей Oxz, Oyz, а также при композиции поворота на $90 в степени левая круглая скобка \circ правая круглая скобка$ вокруг оси Oz и симметрии относительно плоскости Оху. Поэтому условие задачи выполняется также для центров сфер $S_i,$ $i=2, 3, 4.$

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

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

Дано натуральное число $n больше 1.$ Что больше: количество способов разрезать клетчатый квадрат $3n \times 3n$ на клетчатые прямоугольники $1\times 3$ или количество способов разрезать клетчатый квадрат $2n \times 2n$ на клетчатые прямоугольники $1\times 2?$

Решение.

Дадим конструкцию отображения, каждому разбиению доски $2 n \times 2 n$ на доминошки сопоставляющего разбиение доски $3 n \times 3 n$ на триминошки.

Предположим, что задано некоторое разбиение доски $2 n \times 2 n$ на доминошки. Пронумеруем все вертикали числами от 1 до $2 n$ и все горизонтали числами от 1 до $2 n.$ Сделает n горизонтальных разрезов через горизонтали с четным номером и n вертикальных разрезов через вертикали с четным номером. Получится доска $3 n \times 3 n$ (правда, разбитая на неравные клетки, но ничего страшного), далее её будем называть новой доской. Каждая отдельная клетка старой доски стала либо одной, либо двумя, либо четырьмя клетками новой (если соответственно нуль, одна или обе координаты старой клетки были четными числами). Доминошки после этой операции становятся либо триминошками, либо прямоугольниками $2 \times 3 .$ Так вот, разрежем каждый из этих прямоугольников $2 \times 3$ на две триминошки. Получим, наконец, некоторое разбиение доски $3 n \times 3 n$ на триминошки.

Докажем, что при этом из разных разбиений на доминошки получаются разные разбиения на триминошки. Предположим противное: пусть два различных разрезания на доминошки доски $2 n \times 2 n$ при построенном отображении становятся одним разрезанием на триминошки доски $3 n \times 3 n.$ Поскольку разрезания на доминошки различны, существует клетка A доски $2 n \times 2 n,$ накрытая в этих разрезаниях доминошками по-разному. Но тогда после нашей операции то, во что превратится клетка A, т. е. 1, 2, или 4 клеточки, будет накрыто триминошками по-разному. Значит, и разрезания на триминошки разные, что противоречит предположению.

Тем самым, мы доказали, что разрезаний на триминошки не меньше, чем разрезаний на доминошки. Осталось предъявить хотя бы одно разрезание $3 n \times 3 n$ на триминошки, которое не получается из разрезания $2 n \times 2 n$ на доминошки. Проверьте, что подойдет любое разбиение на триминошки, в котором к правому нижнему углу, (т. е. образованному последними строкой и столбцом), примыкает горизонтальная триминошка, а на ней стоят три вертикальные (пример см. на рисунке справа).

Ответ: больше число разбиений на триминошки.

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

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

В таблице n × n стоят все целые числа от 1 до n², по одному в клетке. В каждой строке числа возрастают слева направо, в каждом столбце  — снизу вверх. Докажите, что наименьшая возможная сумма чисел на главной диагонали, идущей сверху слева вниз направо, равна $1 в квадрате плюс 2 в квадрате плюс ... плюс n в квадрате .$

(Б. Френкин)

Решение.

Будем называть лесенкой следующую часть таблицы из $n плюс левая круглая скобка n минус 1 правая круглая скобка плюс \ldots плюс 1$ клеток: самый левый столбец, следующий столбец без верхнего числа, следующий столбец без двух верхних чисел, ..., самый правый столбец без верхних $n минус 1$ чисел.

Пример. Двигаясь от самого левого столбца лесенки к самому правому, заполняем их снизу вверх числами 1, $2, \ldots$ по возрастанию: в первом столбце лесенки будут стоять числа от 1 до n, во втором  — от $n плюс 1$ до $2 n минус 1$ и т. д. Заполнив лесенку, заполняем оставшиеся клетки таблицы по тому же принципу: двигаясь от самого левого столбца таблицы к самому правому, заполняем их снизу вверх оставшимися числами по возрастанию. Тогда таблица будет удовлетворять условию, а сумма чисел на главной диагонали будет равна

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

что и требуется.

Оценка. I способ. Пусть $a_1 меньше a_2 меньше умножить на s меньше a_n$   — числа на главной диагонали (порядок, в котором они там стоят, нам неизвестен). Для каждого $a_k$ покрасим само $a_k$ и все числа, стоящие либо под $a_k$ в том же столбце, либо слева от $a_k$ в той же строке, в цвет номер k. Тогда чисел каждого цвета будет ровно n, и каждое число лесенки, кроме чисел главной диагонали, будет покрашено ровно в два цвета  — «цвет строки» и «цвет столбца» (а каждое число на главной диагонали  — только в один свой цвет).

Заметим, что $a_k$ больше всех остальных чисел цвета k и больше всех чисел, цвет которых имеет номер меньше k (так как $a_k больше a_k минус 1 больше \ldots больше a_1 правая круглая скобка .$ Тем самым $a_k$ не меньше, чем количество чисел с цветами от 1 до k. Но таких чисел ровно

$n плюс левая круглая скобка n минус 1 правая круглая скобка плюс \ldots плюс левая круглая скобка n минус левая круглая скобка k минус 1 правая круглая скобка правая круглая скобка ,$

поскольку чисел цвета $1 минус$ ровно n, чисел цвета 2, но не цвета $1, минус$ ровно $n минус 1, \ldots,$ чисел цвета k, но ни одного из цветов $1, 2, \ldots, k минус 1,$   — ровно $n минус левая круглая скобка k минус 1 правая круглая скобка .$ Отсюда

$a_1 плюс \ldots плюс a_n больше или равно n плюс левая квадратная скобка n плюс левая круглая скобка n минус 1 правая круглая скобка правая квадратная скобка плюс \ldots плюс левая квадратная скобка n плюс$
$плюс левая круглая скобка n минус 1 правая круглая скобка плюс \ldots плюс 2 плюс 1 правая квадратная скобка =n в квадрате плюс левая круглая скобка n минус 1 правая круглая скобка в квадрате плюс \ldots плюс 1 в квадрате .$ $a_1 плюс \ldots плюс a_n больше или равно n плюс левая квадратная скобка n плюс левая круглая скобка n минус 1 правая круглая скобка правая квадратная скобка плюс$
$плюс \ldots плюс левая квадратная скобка n плюс левая круглая скобка n минус 1 правая круглая скобка плюс \ldots плюс 2 плюс$
$плюс 1 правая квадратная скобка =n в квадрате плюс левая круглая скобка n минус 1 правая круглая скобка в квадрате плюс \ldots плюс 1 в квадрате .$

II способ. Пусть $a_1 меньше a_2 меньше умножить на s меньше a_n$   — числа на главной диагонали. Рассмотрим некоторое $a_k.$ Если число из лесенки находится в одной строке или в одном столбце с одним из диагональных чисел $a_1, a_2, \ldots, a_k,$ то оно не превосходит его, и, значит, не превосходит $a_k,$ числа $x больше a_k$ могут находиться только в строках и столбцах с числами $a_k плюс 1, \ldots, a_n$   — таких чисел всего $1 плюс 2 плюс \ldots плюс левая круглая скобка n минус k правая круглая скобка .$ Все остальные $левая круглая скобка n плюс k плюс 1 правая круглая скобка плюс \ldots плюс n$ чисел лесенки не больше $a_k,$ то есть $a_k больше или равно левая круглая скобка n плюс k плюс 1 правая круглая скобка плюс \ldots плюс n .$ Складывая, получаем точную оценку на $a_1 плюс a_2 плюс \ldots плюс a_n .$

III способ. Пронумеруем все диагонали, параллельные главной и лежащие не выше её, числами от 1 до n снизу вверх. Пусть $a_1 меньше a_2 меньше умножить на s меньше a_n$   — числа на главной диагонали. Проведём из чисел $a_1, a_2, \ldots, a_n минус 1$ единичные стрелки влево или вниз в попарно различные клетки $левая круглая скобка n минус 1 правая круглая скобка$ -й диагонали (это, очевидно, возможно). Из $a_n$ же проведём одну из двух стрелок на $левая круглая скобка n минус 1 правая круглая скобка$ -ю диагональ.

Далее действуем аналогично. Именно, пусть мы уже провели стрелки в клетки k-й диагонали так, что пути по стрелкам из $a_1, \ldots, a_k$ не имеют общих клеток. Берём клетки k-й диагонали, в которые приходят пути из $a_1, \ldots, a_k минус 1,$ и проводим из них стрелки в попарно различные клетки $левая круглая скобка k минус 1 правая круглая скобка$ -й диагонали. Из оставшейся клетки проводим любую стрелку на $левая круглая скобка k минус 1 правая круглая скобка$ -ю диагональ.

Теперь нетрудно доказать оценку. Из клеток $a_1, \ldots, a_k$ ведут k путей, причём их начала длины $n, n минус 1, \ldots, n минус k плюс 1$ соответственно не имеют общих клеток. Число $a_k$ не меньше всех чисел, встречающихся на этих путях; поэтому

$a_k больше или равно n плюс левая круглая скобка n минус 1 правая круглая скобка плюс \ldots плюс левая круглая скобка n минус k плюс 1 правая круглая скобка .$

Суммируя, получаем

$a_1 плюс \ldots плюс a_n больше или равно n плюс левая круглая скобка n плюс левая круглая скобка n минус 1 правая круглая скобка правая круглая скобка плюс \ldots плюс$
$плюс левая круглая скобка n плюс левая круглая скобка n минус 1 правая круглая скобка плюс \ldots плюс 1 правая круглая скобка =n умножить на n плюс левая круглая скобка n минус 1 правая круглая скобка умножить на левая круглая скобка n минус 1 правая круглая скобка плюс \ldots плюс 1 умножить на 1 .$ $a_1 плюс \ldots плюс a_n больше или равно n плюс левая круглая скобка n плюс левая круглая скобка n минус 1 правая круглая скобка правая круглая скобка плюс$
$плюс \ldots плюс левая круглая скобка n плюс левая круглая скобка n минус 1 правая круглая скобка плюс \ldots плюс 1 правая круглая скобка =n умножить на n плюс$
$плюс левая круглая скобка n минус 1 правая круглая скобка умножить на левая круглая скобка n минус 1 правая круглая скобка плюс \ldots плюс 1 умножить на 1 .$

Замечание. Это же решение можно оформить по-другому. Рассмотрим только расстановку различных натуральных чисел в диагоналях $1, 2, \ldots, n .$ Докажем, что если в каждой диагонали поставить числа сверху вниз по возрастанию, то расстановка чисел в этом треугольнике по-прежнему будет удовлетворять условиям. Для этого, если $b_1 меньше умножить на s меньше b_k$ и $c_1 меньше умножить на s меньше c_k минус 1$   — числа в k-й и $левая круглая скобка k минус 1 правая круглая скобка$ -й диагоналях, надо доказать, что $b_i больше или равно c_i$ при всех $i=1, 2, \ldots, k минус 1 .$ Это доказывается, например, тем же проведением стрелок; есть и другие способы. После этого в новой расстановке число $a_k$ не меньше, чем все числа в первых k столбцах треугольника, то есть

$a_k больше или равно n плюс левая круглая скобка n минус 1 правая круглая скобка плюс \ldots плюс левая круглая скобка n минус k плюс 1 правая круглая скобка ,$

откуда и следует оценка.

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

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

Луноход ездит по поверхности планеты, имеющей форму шара с длиной экватора 400 км. Планета считается полностью исследованной, если луноход побывал на расстоянии по поверхности не более 50 км от каждой точки поверхности и вернулся на базу (в исходную точку). Может ли луноход полностью исследовать планету, преодолев не более 600 км?

(М. Евдокимов)

Решение.

Отметим на планете полюсы N и S, и пусть точки A, B, C и D делят соответствующий экватор на четыре равных дуги, как на рисунке 1.

Рис. 1.

Рис. 2.

Рассмотрим замкнутый путь

$A arrow B arrow S arrow D arrow C arrow N arrow A$

по поверхности, состоящий из дуг больших окружностей с центрами в центре планеты. Этот путь состоит из 6 одинаковых дуг длиной в $дробь: числитель: 1, знаменатель: 4 конец дроби$ экватора, поэтому длина пути составляет 600 км.

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

Замечание. Докажем более сильное утверждение: луноход может полностью исследовать планету, преодолев не более 570 км.

Снова разобьём поверхность планеты на 8 равных треугольников. Средней параллелью треугольника назовём часть линии, параллельной стороне треугольника и соединяющей середины двух других сторон. На рисунке 2 средняя параллель треугольника лежит на границе красной и зелёной областей. Пусть луноход прошёл по средним параллелям всех треугольников, как на рисунке 3. Вся поверхность планеты будет исследована, потому что любая точка треугольника находится на расстоянии не более 50 км от некоторой точки средней параллели, что видно из рисунка $2 .$

Рис. 3.

Рис. 4.

Наконец, докажем, что длина окружности, на которой лежит средняя параллель, в $корень из: начало аргумента: 2 конец аргумента$ раз меньше длины экватора. Из этого будет следовать, что длина пути равна $дробь: числитель: 800, знаменатель: корень из: начало аргумента: 2 конец аргумента конец дроби ,$ что примерно равно 566.

Пусть N и E  — вершины треугольника, O  — центр планеты. Радиус окружности, на которой лежит средняя параллель, равен расстоянию r от середины M дуги NE до прямой ON. Из рисунка 4 видно, что $r= дробь: числитель: O E, знаменатель: корень из: начало аргумента: 2 конец аргумента конец дроби .$ Значит, радиус меньшей окружности в $корень из: начало аргумента: 2 конец аргумента$ меньше радиуса планеты, что и требовалось.

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

Ответ: да.

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

Всего: 42 1–20 | 21–40 | 41–42