Олимпиада по математике 11 класс — заключительный этап ВсОШ 2023/2024: задания и ответы

Решения — 1 день

Материалы для проведения заключительного этапа 50-й ВСЕРОССИЙСКОЙ МАТЕМАТИЧЕСКОЙ ОЛИМПИАДЫ ШКОЛЬНИКОВ 2023–2024 учебный год Первый день Нижний Новгород, 19–25 апреля 2024 г.

Москва, 2024

Сборник содержит материалы для проведения заключительного этапа 50-й Всероссийской олимпиады школьников по математике. Задания подготовлены Центральной предметно-методической комиссией по математике Всероссийской олимпиады школьников. Сборник составили: Н. Х. Агаханов, А. В. Антропов, С. Л. Берлов, И. И. Богданов, Н. Ю. Власова, П. А. Кожевников, А. С. Кузнецов, Е. Г. Молчанов, Ф. В. Петров, О. К. Подлипский, К. А. Сухов, Д. А. Терёшин, Д. Г. Храмцов, Г. Р. Челноков. А также: М. А. Дидин, И. А. Ефремов, К. А. Кноп, П. Ю. Козлов, Т. С. Коротченко, А. Д. Терёшин, И. И. Фролов, М. А. Туревский, А. И. Храбров. В скобках после каждой задачи указана фамилия её автора. Компьютерный макет: И. И. Богданов, А. И. Голованов.

© Авторы и составители, 2024 © И. И. Богданов, А. И. Голованов, 2024, макет

Заключительный этап, 2023–2024 учебный год. Первый день

11 класс 11.1. В пространстве расположен бесконечный цилиндр (т.е. геометрическое место точек, удалённых от данной прямой ` на данное расстояние R > 0). Могут ли шесть прямых, содержащих рёбра некоторого тетраэдра, иметь ровно по одной общей точке с этим цилиндром? (А. Кузнецов) Ответ. Не могут. Решение. Предположим, что такая конструкция существует. Спроецируем тетраэдр на плоскость α, перпендикулярную прямой `. Проекцией цилиндра будет некоторая окружность ω. Обозначим проекции вершин тетраэдра через A, B, C, D, они все будут различны (в противном случае одна из прямых, содержащих стороны тетраэдра, будет параллельна `, такая прямая не может иметь с цилиндром ровно одну общую точку). Каждая из прямых, соединяющих точки A, B, C, D должна иметь с окружностью ω одну общую точку, то есть касаться этой окружности. При этом точки A, B, C, D не могут лежать на одной прямой (поскольку вершины тетраэдра не лежат в одной плоскости). Значит, либо на одной прямой лежат какие-то три из них, не умаляя общности B, C, D, либо никакие три из этих точек на одной прямой не лежат. В любом случае прямые AB, AC, AD попарно различны, однако они все касаются окружности ω и проходят через точку A, противоречие. 11.2. Тройку положительных чисел (a, b, c) назовём загадочной, если r r 1 1 2 a + 2 2 + 2ab + b2 + 2 2 + 2bc + a c b a r 1 + c2 + 2 2 + 2ca = 2(a + b + c). c b Докажите, что если тройка (a, b, c) — загадочная, то тройка (c, b, a) — тоже загадочная. (А. Кузнецов, К. Сухов) Решение. Покажем, что тройка (a, b, c) — загадочная в том и только в том случае, когда abc = 1, из этого немедленно последует Предположим, что abc < 1. Тоr требуемое в задаче. √ a2 + 21 2 + 2ab > a2 + b2 + 2ab = a + b, аналогично гда a c

13

50-я Всероссийская математическая олимпиада школьников

r r 1 2 b + 2 2 + 2bc > b + c и c2 + 21 2 + 2ca > c + a. Итого, b a

c b

в этом случае левая часть равенства из условия больше правой. Рассуждая аналогично, в случае abc > 1 имеем, что правая часть больше левой, а в случае abc = 1 достигается равенство, что и требовалось. 11.3. Юрий подошёл к великой таблице майя. В таблице 200 столбцов и 2200 строк. Юрий знает, что в каждой клетке таблицы изображено солнце или луна, и любые две строки отличаются (хотя бы в одном столбце). Каждая клетка таблицы закрыта листом. Поднялся ветер и сдул некоторые листы: по два листа с каждой строки. Могло ли так случиться, что теперь Юрий хотя бы про 10 000 строк может узнать, что в них изображено в каждом из столбцов? (И. Богданов, К. Кноп) Ответ. Могло. Решение. Разобьём все позиции на две половины по 100 столбцов — «левую» и «правую». Предположим, что в каждой строке, в которой есть два солнца в одной половине (назовём их солнечными), ветер сдул листья с одной из таких пар солнц, а в каждой несолнечной строке — таких строк ровно 1012 — ветер обнаружил положения всех солнц (в несолнечной строке не более двух солнц, так что ветер мог так поступить). Тогда Юрий* сообразит, что те строки, где открыты два солнца в одной половине — точно солнечные, а значит, несолнечные строки — это в точности те 1012 строк, в которых ветер не открывал два солнца в одной половине. У каждой из них открыты все солнца, так что закрытые листьями изображения в этих строках — луна. 11.4. Четырёхугольник ABCD, в котором нет параллельных сторон, вписан в окружность ω. Через вершину A проведена прямая `a k BC, через вершину B — прямая `b k CD, через вершину C — прямая `c k DA, через вершину D — прямая `d k AB. Четырёхугольник, последовательные стороны которого лежат на этих четырёх прямых (именно в этом порядке), вписан в окружность γ. Окружности ω и γ пересекаются в точках E и F . Дока* Юрий Валентинович Кнорозов (1922–1999) — советский и российский учёный, дешифровавший письменность майя.

14

Заключительный этап, 2023–2024 учебный год. Первый день

жите, что прямые AC, BD и EF пересекаются в одной точке. (А. Кузнецов)

Первое решение. Без ограничения общности можно считать, что лучи AB и DC; CB и DA пересекаются. Пусть отрезки AC и BD пересекаются в точке G, а также A0 B 0 C 0 D0 — четырёхугольник, образованный прямыми `a , `b , `c , `d (см. рис. 4). Также обозначим через X пересечение AB и CD0 , через Y — пересечение CD и AB 0 . D0 X

A0

B E G

γ2

γ1 γ YY

C00000 C

F F B0000 B D

γ0

Рис. 4 Пусть ∠B 0 AB = α. Из вписанности четырёхугольника

A0 B 0 C 0 D0 и условий AX k `d , CY k `b имеем: α = ∠B 0 AX = = 180◦ − ∠A0 B 0 C 0 = ∠C 0 D0 X = ∠Y CA0 . Значит, во-первых,

точки A, D0 , X, C 0 лежат на одной окружности, обозначим её γ1 ; во-вторых, точки C, Y , A0 , B 0 лежат на одной окружности, обозначим её γ2 ; в-третьих, точки A, X, C, Y лежат на одной окружности, обозначим её γ0 . Заметим, что точка B — радикальный центр окружностей γ, γ0 , γ1 (поскольку она лежит на прямых AX и C 0 D0 ); точка D — радикальный центр окружностей γ, γ0 , γ2 (так как она лежит на прямых CY и A0 B 0 ). Таким образом, BD — радикальная ось окружностей γ0 и γ; AC — радикальная ось окружностей γ0 и ω; EF — радикальная ось окруж15

50-я Всероссийская математическая олимпиада школьников

ностей ω и γ, поэтому эти три прямые пересекаются в одной точке, что и требовалось доказать. Второе решение. Введём обозначения как в первом решении. Для точки плоскости P обозначим через f (P ) разность степеней точки P относительно окружностей ω и γ. Поскольку EF — радикальная ось окружностей ω и γ, то достаточно доказать, что f (G) = 0. Кроме того, легко видеть, что f (A) = = AC 0 · AB 0 и f (C) = −CD0 · CA0 (см. рис. 5). D0

A0

B E G γ

F F B00000 B

C00000 C

D ω

Рис. 5 Заметим, что функция f — линейная, то есть для точки P на отрезке QR выполнено равенство f (P ) = =

P R · f (Q) + P Q · f (R) (?). Мы докажем это утверждение QR

позднее. Пока, применив его для точек A, G, C, мы получим, что f (G) =

AG · f (C) + CG · f (A) . AC

f (A) = − f (C) AG (??). Заметим, что AG = d(A, BD) = SABD = AB · AD = CG GC d(C, BD) SBCD CB · CD

Таким образом, достаточно доказать, что

(последнее равенство следует из того, что ∠BAD + ∠BCD = = 180◦ ; через d(P, `) мы обозначаем расстояние от точки D до

16

Заключительный этап, 2023–2024 учебный год. Первый день

прямой `). Следовательно, равенство (??) переписывается в ви0 0 AB · AD . де: AC 0 · AB 0 = CB · CD CD · CA

Из вписанности четырёхугольника ABCD и данных в условии параллельностей прямых следуют равенства углов: ∠CA0 D = 180◦ − ∠ADB 0 = ∠BAD = 180◦ − ∠BCD = ∠CBC 0 = = ∠AC 0 B; ∠ABC 0 = ∠CDA0 и ∠BCD0 = ∠B 0 AD. Таким образом, 4ABC 0 и 4CDA0 , а также 4DAB 0 и 4BCD0 подобны по двум углам. Из подобия получаем равенства отношений AC 0 = AB и AB 0 = AD , остаётся лишь перемножить эти раCD BC CA0 CD0 венства. Вернёмся к доказательству линейности функции f . Введём декартовы координаты таким образом, чтобы центры окружностей ω и γ лежали на оси абсцисс, пусть их координаты будут (x1 , 0) и (x2 , 0), а радиусы окружностей — R1 и R2 . Тогда для произвольной точки P с координатами (x, y) по определению степени точки мы получаем, что f (P ) = (x − x1 )2 + y 2 − R12 − − (x − x2 )2 − y 2 + R22 = ax + b, где a и b — две константы. Если точка P лежит на отрезке QR и xq , xr — координаты точек Q и R по оси абсцисс, то x =

P R · xq + P Q · xr , откуда немедленно QR

следует (?). Замечание 1. Линейная функция в произвольным образом введённых декартовых координатах имеет вид f (x, y) = ax+ +by +c. Если она отлична от константы, то решением уравнения f (x, y) = 0 будет прямая. Например, таким образом (рассуждая как в приведённом решении) доказывается, что радикальная ось двух окружностей — это прямая, перпендикулярная линии центров. Замечание 2. Приведём план решения задачи с помощью комплексных чисел. Пусть окружность ω — стандартная единичная, координаты точек A, B, C, D обозначаются соответственно a, b, c, d. Рассмотрим прямые (точнее, уравнения прямых) `ac (z) = acz̄ + z − a − c, `bd (z) = bdz̄ + z − b − d — это соответствующие диагонали AC, BD. Прямая `a через точку A параллельно BC имеет уравнение `a (z) = bcz̄ + z − bc/a − a, аналогично три другие прямые из условия. Окружность γ, про17

50-я Всероссийская математическая олимпиада школьников

ходящая через точки их пересечения, имеет уравнение F (z) := = `a (z)`c (z) − `b (z)`d (z): с одной стороны, точки пересечения удовлетворяют условию F = 0, с другой стороны, коэффициенты при z 2 и z̄ 2 сокращаются, так что это именно окружность. Радикальная ось окружностей γ и ω имеет уравнение `ef (z) := = F (z) − T (z z̄ − 1), где T — подходящий коэффициент, чтобы получилась прямая (он нам не будет важен в дальнейшем). Докажем, что для некоторых коэффициентов τ , θ имеет место тождество `ef (z)+τ `ac (z)+θ`bd (z) = 0 (A), из этого будет следовать требуемое. Тождество (A) достаточно проверять, когда z — одна из вершин четырёхугольника ABCD, потому что на одной прямой они не лежат. Подставляя, например, z = a, получаем тождество 0 = F (a) + θ`bd (a) = −`b (a)`d (a) + θ`bd (a). Это даёт значение θ, и оно должно быть согласовано со значением, которое получается для z = c, то есть должно выполняться тождество `b (a)`d (a)/`bd (a) = `b (c)`d (c)/`bd (c), и второе аналогичное. Все эти значения считаются непосредственно (и раскладываются на множители, например, `bd (a) = bd/a+a−b−d = (a−b)(a−d)/d), после чего не составляет труда доказать нужное тождество.

18

Критерии проверки работ 11 класса. индекс критерия критерий

балл

Задача 1 В целом верные решения с недочетами оцениваются не менее чем в 5 баллов. Ниже перечислены основные недочеты, за которые снимается по 1 баллу M

Упущен случай, когда вершина тетраэдра лежит на цилиндре

М1

Упущен случай, в котором проекции двух вершин совпадают

M2

Не объяснено, почему проекции вершин тетраэдра не лежат на одной прямой Если нарушена логика рассмотрения случаев, задача считается не решенной. Продвижения (при отсутствии решения) оцениваются по схемам А или B, не суммируются продвижения из разных схем. Суммируются продвижения в рамках одной схемы под разными пунктами (I, II, III) Работа оценивается не более чем в 4 балла.

Решение с проецированием вдоль оси цилиндра

AI

Доказано, что при проекции вершин тетраэдра на плоскость, перп оси цилиндра, получаются 4 разные* точки и прямые, их соединяющие, касаются окружности (проекции цилиндра) 2 балла *Если не объяснено, почему не могут совпадать проекции начисляется лишь 1 балл

AII

Доказано, что 4 проекции вершин не лежат на одной прямой

1 балл

AIIIa

Разобран случай, когда проекция некоторой грани — треугольник

1 балл

AIIIb

Доказано, что проекции трех вершин лежат на одной прямой

1 балл

AIIIc

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

1 балл

IIIa, IIIb, IIIc не суммируются друг с другом B

Решение без перехода к проекциям

BI

Описание прямых, проходящих через точку вне цилиндра и имеющих с ним 1 общую точку: они лежат в двух плоскостях, касающихся цилиндра

1 балл

BII

Сформулировано и доказано, что через каждую вершину тетраэдра проходит грань, параллельная прямой $\ell$

2 балла

BIII

Доказано, что ребро тетраэдра не может быть параллельно $\ell$

1 балл

(Z)

Алгебраические преобразования без дальнейших продвижений

0 баллов

(A)

Перепутаны знаки в случаях неравенства abc<>1

не более 6 баллов

(B)

Доказано, что если abc=1, то тройка загадочная

1 балл

Задача 2

Задача 3 доказано, что встречаются все двоичные коды ровно по одному разу 0 баллов показано, как восстановить меньшее количество строк (обычно 400)

0 баллов

продвижения в оценке сверху количества восстанвливаемых строк

0 баллов

исследован аналогичный вопрос в ситуации, когда ветер сдувает один лист из каждой строки

0 баллов

предъявлен верный способ действий ветра и Юрия, но не доказано, что восстановление однозначно

4 балла

Задача 4 Критерии по 11.4:

(Z1)

Доказана вписанность вспомогательного четырёхугольника, полученного при помощи "антипараллельности" из исходного. Например для четырёхугольника A, D0, X, C или для A, X, C, Y из первого решения.

0 баллов

(Z2)

Сделана "инверсия + симметрия" или аналогичное преобразование, после чего задача переформулирована в новых терминах.

0 баллов

(Z3)

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

0 баллов

Только оценка

2 балла

Только пример

3 балла

Оценка и алгоритм без обоснования

5 баллов

Задача 5

Задача 6 Z

Перечисленные в этом пункте продвижения не оцениваются Изогональность лучей $AO$ и $AH$ в угле $BAC$, иной подсчет углов без дальнейших выводов Отмечена точка $D$ (второе пересечение окружности $(ABC)$ и AH$) Доказано, что отрезок $XY$ — серединный перпендикуляр к $AD$, равенства $AX = XD$ и $AY = YD$ Вписанность $XYZT$, $BZTC$, параллельность $XY$ и $AB$ Переформулировка задачи после инверсии (например, с центром A).

Отмечена точка $D$, сформулирована гипотеза о касании окружностей в точке $D$ и доказана вписанность $XYZT$.

1 балл

Доказано, что окружности $(DXY)$ и $(ABC)$ касаются

1 балл

Доказано, что окружности $(DZT)$ и $(ABC)$ касаются

1 балл

D1

Доказано, что $BZHD$ — вписанный

1 балл

D2

Доказано, что $AZ = ZY$

2 балла

При наличии лишь продвижений, указанных выше, работа оценивается не более чем в 3 балла. С учетом этого, суммируются продвижения из разных групп (A, B, C, D). Продвижения из одной группы не суммируются. S

Наличие продвижений B или C автоматически засчитывается за наличие гипотезы из продвижения А.

Доказано, что точки $D, X, Y, Z, T$ лежат на одной окружности

4 балла

Задача 7 доказано, что компоненты связности -- деревья (или: задача сведена к вычислению математического ожидания числа дорог) 0 баллов доказано, что количество компонент равно количеству взаимных дорог

1 балл

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

4 балла

мелкие ошибки вычислительного или комбинаторного характера снятие от 1 до 2 баллов Задача 8 (A)

Доказана оценка $c\sqrt[100]{p}$

1 балл

Решения — 2 день

Материалы для проведения заключительного этапа 50-й ВСЕРОССИЙСКОЙ МАТЕМАТИЧЕСКОЙ ОЛИМПИАДЫ ШКОЛЬНИКОВ 2023–2024 учебный год Второй день Нижний Новгород, 19–25 апреля 2024 г.

Москва, 2024

Сборник содержит материалы для проведения заключительного этапа 50-й Всероссийской олимпиады школьников по математике. Задания подготовлены Центральной предметно-методической комиссией по математике Всероссийской олимпиады школьников. Сборник составили: Н. Х. Агаханов, А. В. Антропов, С. Л. Берлов, И. И. Богданов, Н. Ю. Власова, П. А. Кожевников, А. С. Кузнецов, Е. Г. Молчанов, Ф. В. Петров, О. К. Подлипский, К. А. Сухов, Д. А. Терёшин, Д. Г. Храмцов, Г. Р. Челноков. А также: М. А. Дидин, И. А. Ефремов, К. А. Кноп, П. Ю. Козлов, Т. С. Коротченко, А. Д. Терёшин, И. И. Фролов, М. А. Туревский, А. И. Храбров. В скобках после каждой задачи указана фамилия её автора. Компьютерный макет: И. И. Богданов, А. И. Голованов.

© Авторы и составители, 2024 © И. И. Богданов, А. И. Голованов, 2024, макет

50-я Всероссийская математическая олимпиада школьников

11 класс 11.5. Квартал представляет собой клетчатый квадрат 10 × 10. В новогоднюю ночь внезапно впервые пошёл снег, и с тех пор каждую ночь на каждую клетку выпадало ровно по 10 см снега; снег падал только по ночам. Каждое утро дворник выбирает один ряд (строку или столбец) и сгребает весь снег оттуда на один из соседних рядов (с каждой клетки — на соседнюю по стороне). Например, он может выбрать седьмой столбец и из каждой его клетки сгрести весь снег в клетку слева от неё. Сгребать снег за пределы квартала нельзя. Вечером сотого дня года в город приедет инспектор и найдёт клетку, на которой лежит сугроб наибольшей высоты. Цель дворника — добиться, чтобы эта высота была минимальна. Сугроб какой высоты найдёт инспектор? (А. Солынин)

Ответ. 1120 см. Решение. Будем измерять высоту сугроба в дециметрах. Также будем считать, что сторона одной клетки равна 1 дм, то есть за каждую ночь на клетку выпадает 1 дм3 снега. Докажем, что после сотого утра найдется сугроб высотой не менее 112 дм. Предположим, что такого сугроба нет. Так как дворник в сотое утро полностью сгрёб снег с какого-то ряда, в десяти клетках квадрата снега нет. В каждой из оставшихся 90 клеток, по нашему предположению, не более 111 дм3 снега, то есть всего снега не больше, чем 9990 дм3 . Однако за 100 ночей суммарно выпало 10 000 дм3 снега. Противоречие. Покажем, как может действовать дворник, чтобы после сотого утра каждый сугроб имел высоту не более 112 дм (то есть в каждой клетке было не более 112 дм3 снега). Способ 1. Первые 11 дней дворник сгребает снег из второго столбца в первый, следующие 11 дней дворник сгребает снег из третьего столбца во второй, затем 11 дней из четвёртого в третий, и т. д. Через 99 дней в десятом столбце не будет снега. Посчитаем, сколько снега стало в столбце i ⩽ 9 через 99 дней. Вечером 11(i − 1)-го дня в столбце номер i не было снега, а в столбце i + 1 в каждой клетке было по 11(i − 1) дм3 снега. На следующий вечер в столбце i станет по 11(i − 1) + 2 дм3 сне16

Заключительный этап, 2023–2024 учебный год. Второй день

га в каждой клетке. Затем ещё десять дней количество снега в каждой клетке i-го столбца будет увеличиваться на 2, а затем 11(9 − i) дней — на 1. Итого, через 99 дней в каждой клетке столбца i будет по 11(i − 1) + 22 + 11(9 − i) = 110 дм3 снега. В сотую ночь выпадет ещё по 1 дм3 в каждую клетку. А сотым утром дворник сгребет снег из десятого столбца в девятый. Таким образом, в каждой клетке будет не более 112 дм3 снега. Способ 2. Пусть дворник сгребёт снег из 2-го столбца в 1-ый, из 3-го во 2-й, . . . , из 10-го в 9-ый. Тогда вечером девятого дня в первых девяти столбцах будет по 10 дм3 снега в каждой клетке, а в десятом столбце снега не будем. Затем дворник проделывает аналогичный процесс в обратном порядке: из 9-го в 10-ый, из 8-го в 9-ый, . . . , из 2-го в первой. Тогда вечером 18-го дня в клетках последних девяти столбцов будет по 20 дм3 снега, а в первом столбце не будет снега. Аналогично повторим такие сдвиги (каждый длится 9 дней) ещё 9 раз, и через 99 дней получим в клетках девяти столбцов по 110 дм3 снега и один крайний столбец пустой. Сотым утром сгребаем снег из этого крайнего в соседний и получаем не более 112 дм3 снега в каждой клетке. 11.6. Остроугольный неравнобедренный треугольник ABC вписан в окружность ω с центром в точке O, его высоты пересекаются в точке H. Через точку O проведена прямая, перпендикулярная AH, а через точку H — прямая, перпендикулярная AO. Докажите, что точки пересечения этих прямых со сторонами AB и AC лежат на одной окружности, которая касается окружности ω. (А. Кузнецов) Решение. Пусть прямая AH повторно пересекает окружность ω в точке D (см. рис. 5). Тогда прямая, проведённая по условию через O — серединный перпендикуляр к хорде AD, пусть она пересекает стороны AB и AC в точках X и Y , а прямая через H из условия задачи пересекает их в точках Z и T . Поскольку XY k AC, то окружность (AXY ) касается окружности ω в точке A. При симметрии относительно XY окружность ω переходит в себя, а окружность (AXY ) переходит в окружность (DXY ), тогда она тоже касается окружности ω. Поскольку ZH ⊥ AO, то ∠AZH = 90◦ − ∠OAB = ∠ACB = 17

50-я Всероссийская математическая олимпиада школьников

X H H

Y T

Z B

D Рис. 5 = ∠ADB. Следовательно, четырёхугольник BZHD — вписанный. Тогда ∠BZD = ∠BHD = 90◦ − ∠HCB = ∠ACB. Значит, в силу сказанного выше, ∠XY D = ∠AY X = ∠ACB = ∠BZD, поэтому точка Z лежит на окружности (DXY ). Аналогично, на этой окружности лежит и точка T , откуда и следует требуемое. Замечание. Можно рассуждать несколько иначе: установить (похожими равенствами углов), что точки X, Y , Z, T лежат на одной окружности, а также что окружности (DXY ) и (DZT ) касаются окружности ω в точке D. Однако эти три окружности не могут быть различными, поскольку в таком случае их радикальные оси не пересекаются в одной точке, в чём нетрудно убедиться. Значит, все эти окружности совпадают, что нам и требовалось. 11.7. В стране n > 100 городов и пока нет дорог. Правительство наугад определяет стоимость строительства дороги (с двусторонним движением) между каждыми двумя городами, используя по разу все суммы от 1 до n(n − 1)/2 талеров (все варианты равновероятны). Мэр каждого города выбирает самую дешёвую из n − 1 возможных дорог, идущих из этого города, и она строится

18

Заключительный этап, 2023–2024 учебный год. Второй день

(это может быть взаимным желанием мэров обоих соединяемых городов или только одного из двух). После строительства этих дорог города оказываются разбиты на M компонент связности (между городами одной компоненты связности можно добраться по построенным дорогам, возможно, с пересадками, а между городами разных компонент — нельзя). Найдите математическое ожидание случайной величины M . (Ф. Петров) n(n − 1)

Ответ. 2(2n − 3) . Решение. Дорогу, которую хотят строить сразу два мэра, назовём надёжной. Рассмотрим в каждой компоненте самую дешёвую дорогу AB. Тогда она является надёжной. Предположим, что в этой компоненте есть ещё одна надёжная дорога CD (ясно, что города C, D отличны от A, B) и рассмотрим путь по дорогам от одного из городов A, B до одного из городов C, D — не умаляя общности, он имеет вид AX1 X2 . . . Xk C (города X1 , . . . , Xk отличны от A, B, C, D, возможно, k = 0). Тогда дорогу AX1 хочет строить мэр города X1 (мэр города A хочет строить AB), дорогу X1 X2 — мэр города X2 (мэр города X1 хочет строить X1 A) и так далее, мэр города C хочет строить дорогу CXk , а не CD — противоречие. Итак, в каждой компоненте есть ровно одна надёжная дорога. Для каждой из n(n − 1)/2 пар городов A, B рассмотрим случайную величину ξAB , которая равна 1, если AB — надёжная дорога, и 0 в противном случае. Из доказанного следует, что M есть сумма ξAB по всем n(n − 1)/2 парам {A, B}. Для данных A, B событие ξAB = 1 означает, что дорога AB — самая дешёвая из 2n − 3 дорог, выходящих из A или B, так что вероятность такого события равна 1/(2n − 3) (из симметричности распределения цен эти дороги равноправны, так что каждая из них является самой дешёвой с вероятностью 1/(2n − 3)). Значит, математическое ожидание ξAB равно 1/(2n − 3), а математическое ожидание случайной величины M равно сумме этих математических n(n − 1)

ожиданий по всем парам, то есть 2(2n − 3) . 11.8. Докажите, что существует такое c > 0, что для любого нечётного простого p = 2k + 1 числа 10 , 21 , 32 , . . ., k k−1 да19

50-я Всероссийская математическая олимпиада школьников

√ ют хотя бы c p различных остатков при делении на p. (М. Туревский, И. Богданов)

Решение. Все сравнения в этом решении производятся по модулю p. Если a и b — целые числа, причём b не делится на p, то через a/b мы обозначаем тот единственный остаток c по модулю p, для которого a ≡ bc. Пусть числа 10 , 21 , 32 , . . ., k k−1 дают ровно d различных остатков при делении на p. Обозначим t = [p/4]. Тогда выражения вида f (a) = (2a)2a−1 /(aa−1 )2 = 22a−1 a при 1 ⩽ a ⩽ t дают максимум d2 различных остатков. Назовём пару натуральных чисел (a, b) таких, что 1 ⩽ a < < b ⩽ t, исключительной, если f (a) ≡ f (b). Покажем, что для каждого δ = 1, 2, . . . , t − 1 существует не более одной исключительной пары (a, b), в которой b − a = δ. Действительно, если (a, b) — такая пара, то из 22a−1 a = 22b−1 b вытекает, что a/b ≡ 22δ , откуда b = a + δ ≡ 22δ b + δ, или b(1 − 22δ ) ≡ δ. Такой остаток b не более чем единственен (поскольку δ 6= 0), а по нему восстанавливается a. Итого, существует не более чем t − 1 исключительная пара; обозначим их количество через S. Пусть числа f (1), f (2), . . . , f (t) дают ровно ` различных остатков по модулю p, встречаюP` щихся a1 , a2 , . . ., a` раз соответственно. Тогда i=1 ai = t и P S = `i=1 Ca2i . Верна следующая цепочка неравенств:   ` ` X X 1 t2 /` − t t−1⩾S =  a2i − ai  ⩾ , 2 2

i=1 i=1 2 откуда ` ⩾ t /(3t − 2) > t/3. Вспоминая, что ` ⩽ d2 , получаем

p p оценку d > t/3 ⩾ [ p/12]. Таким образом, в качестве искомой константы c можно взять, например, число 1/24: для простых p < 12 неравен√ p

ство d > 24 тривиально, а для p > 12 следует из неравенства [x] ⩾ x/2 при x > 1.

20

Критерии проверки работ 11 класса. индекс критерия критерий

балл

Задача 1 В целом верные решения с недочетами оцениваются не менее чем в 5 баллов. Ниже перечислены основные недочеты, за которые снимается по 1 баллу M

Упущен случай, когда вершина тетраэдра лежит на цилиндре

М1

Упущен случай, в котором проекции двух вершин совпадают

M2

Не объяснено, почему проекции вершин тетраэдра не лежат на одной прямой Если нарушена логика рассмотрения случаев, задача считается не решенной. Продвижения (при отсутствии решения) оцениваются по схемам А или B, не суммируются продвижения из разных схем. Суммируются продвижения в рамках одной схемы под разными пунктами (I, II, III) Работа оценивается не более чем в 4 балла.

Решение с проецированием вдоль оси цилиндра

AI

Доказано, что при проекции вершин тетраэдра на плоскость, перп оси цилиндра, получаются 4 разные* точки и прямые, их соединяющие, касаются окружности (проекции цилиндра) 2 балла *Если не объяснено, почему не могут совпадать проекции начисляется лишь 1 балл

AII

Доказано, что 4 проекции вершин не лежат на одной прямой

1 балл

AIIIa

Разобран случай, когда проекция некоторой грани — треугольник

1 балл

AIIIb

Доказано, что проекции трех вершин лежат на одной прямой

1 балл

AIIIc

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

1 балл

IIIa, IIIb, IIIc не суммируются друг с другом B

Решение без перехода к проекциям

BI

Описание прямых, проходящих через точку вне цилиндра и имеющих с ним 1 общую точку: они лежат в двух плоскостях, касающихся цилиндра

1 балл

BII

Сформулировано и доказано, что через каждую вершину тетраэдра проходит грань, параллельная прямой $\ell$

2 балла

BIII

Доказано, что ребро тетраэдра не может быть параллельно $\ell$

1 балл

(Z)

Алгебраические преобразования без дальнейших продвижений

0 баллов

(A)

Перепутаны знаки в случаях неравенства abc<>1

не более 6 баллов

(B)

Доказано, что если abc=1, то тройка загадочная

1 балл

Задача 2

Задача 3 доказано, что встречаются все двоичные коды ровно по одному разу 0 баллов показано, как восстановить меньшее количество строк (обычно 400)

0 баллов

продвижения в оценке сверху количества восстанвливаемых строк

0 баллов

исследован аналогичный вопрос в ситуации, когда ветер сдувает один лист из каждой строки

0 баллов

предъявлен верный способ действий ветра и Юрия, но не доказано, что восстановление однозначно

4 балла

Задача 4 Критерии по 11.4:

(Z1)

Доказана вписанность вспомогательного четырёхугольника, полученного при помощи "антипараллельности" из исходного. Например для четырёхугольника A, D0, X, C или для A, X, C, Y из первого решения.

0 баллов

(Z2)

Сделана "инверсия + симметрия" или аналогичное преобразование, после чего задача переформулирована в новых терминах.

0 баллов

(Z3)

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

0 баллов

Только оценка

2 балла

Только пример

3 балла

Оценка и алгоритм без обоснования

5 баллов

Задача 5

Задача 6 Z

Перечисленные в этом пункте продвижения не оцениваются Изогональность лучей $AO$ и $AH$ в угле $BAC$, иной подсчет углов без дальнейших выводов Отмечена точка $D$ (второе пересечение окружности $(ABC)$ и AH$) Доказано, что отрезок $XY$ — серединный перпендикуляр к $AD$, равенства $AX = XD$ и $AY = YD$ Вписанность $XYZT$, $BZTC$, параллельность $XY$ и $AB$ Переформулировка задачи после инверсии (например, с центром A).

Отмечена точка $D$, сформулирована гипотеза о касании окружностей в точке $D$ и доказана вписанность $XYZT$.

1 балл

Доказано, что окружности $(DXY)$ и $(ABC)$ касаются

1 балл

Доказано, что окружности $(DZT)$ и $(ABC)$ касаются

1 балл

D1

Доказано, что $BZHD$ — вписанный

1 балл

D2

Доказано, что $AZ = ZY$

2 балла

При наличии лишь продвижений, указанных выше, работа оценивается не более чем в 3 балла. С учетом этого, суммируются продвижения из разных групп (A, B, C, D). Продвижения из одной группы не суммируются. S

Наличие продвижений B или C автоматически засчитывается за наличие гипотезы из продвижения А.

Доказано, что точки $D, X, Y, Z, T$ лежат на одной окружности

4 балла

Задача 7 доказано, что компоненты связности -- деревья (или: задача сведена к вычислению математического ожидания числа дорог) 0 баллов доказано, что количество компонент равно количеству взаимных дорог

1 балл

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

4 балла

мелкие ошибки вычислительного или комбинаторного характера снятие от 1 до 2 баллов Задача 8 (A)

Доказана оценка $c\sqrt[100]{p}$

1 балл