Тема Заключительный этап ВсОШ

Закл (финал) 11 класс → .10 Закл 2023

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела заключительный этап всош

Разделы подтемы Закл (финал) 11 класс

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#90097Максимум баллов за задание: 7

У $100$ школьников есть стопка из $101$ карточки, которые пронумерованы числами от $0$ до $100.$ Первый школьник перемешивает стопку, затем берет сверху из получившейся стопки по одной карточке, и при каждом взятии карточки (в том числе при первом) записывает на доску среднее арифметическое чисел на всех взятых им на данный момент карточках. Так он записывает $100$ чисел, а когда в стопке остается одна карточка, он возвращает карточки в стопку, и далее все то же самое, начиная с перемешивания стопки, проделывает второй школьник, потом третий, и т.д. Докажите, что среди выписанных на доске $10000$ чисел найдутся два одинаковых.

Источники: ВСОШ, ЗЭ, 2023, 10.2 и 11.2 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1

Попробуйте посмотреть, какие множества чисел могут получаться у школьников на 1 шаге, на 2 шаге, на 100 шаге?

Подсказка 2

Попробуйте в явном виде найти все возможные значения, находящиеся в этих множествах. Как найти одинаковые среди них?

Подсказка 3

Рассмотрите первое, второе и сотое множества, а именно их объединение. Сколько в нëм чисел?

Показать доказательство

На $1$ -м шаге у каждого из $100$ человек было выписано одно из чисел множества

A1 = {0,1,2,...,100}

На $2$ -м шаге — одно из чисел множества

{ 1 2 3 199} A2 = 2,2,2,..., 2

На $100$ -м шаге выписано одно из чисел множества

{ S S− 1 S− 2 S− 100 } A100 = 100,-100-,-100-,...,-100--

где $S = 100-⋅101- 2$ — сумма всех чисел (а вычитается — число на оставшейся в конце карточке).

Видим, что ${ 1 2 3 199 200} A1 ∪A2 =A2 = 0,2,2,2,..., 2 , 2 ,$ так что $|A1∪ A2|= 201.$ Далее, $|A100|=101,$ но числа $1 1 50− 2,50,50+ 2$ принадлежат $A2∩A100,$ значит, $|A1 ∪A2∪ A100|≤ 201 +101− 3= 299.$

Итак, мы показали, что $300$ чисел, выписанных на $1$ -м, $2$ -м и $100$ -м шагах, могут принимать не более $299$ различных значений. Следовательно, какие-то два из них равны.

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#131944Максимум баллов за задание: 7

Число $x$ таково, что $sin x+tgx$ и $cosx+ ctgx$ — рациональные числа. Докажите, что $sin2x$ является корнем квадратного уравнения с целыми коэффициентами.

Источники: ВСОШ, ЗЭ, 2023, 11.1 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

Ясно, что sin(2x) выражается через sin(x)cos(x). Если найти уравнение с таким корнем, то будет несложно получить корень sin(2x).

Подсказка 2:

Давайте заметим, что выражения a + b и ab будут целыми и инвариантными относительно перестановки синуса и косинуса. Почему бы в дополнение к выражению v = sin(x)cos(x) не взять выражение u = sin(x) + cos(x) и попробовать выразить ab и a + b через u и v?

Подсказка 3:

Вы должны были получить такие равенства: a + b = u + 1/v, ab = v + u + 1. Как из них получить нужное уравнение?

Показать доказательство

Положим $a= sinx+ tgx$ и $b= cosx+ ctgx.$ Введём обозначения:

u= sinx+ cosx

v = sinxcosx

По условию рациональными являются числа

c =a+ b= u+ v−1

d =a⋅b= v+ u+ 1

Отсюда

k= d− c= v+1 − v−1

Значит,

t= sin2x= 2v

является решением квадратного уравнения

2 t + 2t− (4+ 2kt)= 0

с рациональными коэффициентами, откуда следует требуемое.

Ошибка.
Попробуйте повторить позже

Задача 3#131945Максимум баллов за задание: 7

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

Источники: ВСОШ, ЗЭ, 2023, 11.3 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

По условию нельзя одну строку перевести в другую. Что это означает в общем виде?

Подсказка 2:

Каждой строке присущ индивидуальный признак, над которым описанная операция невластна либо власть очень ограничена, то есть с помощью этой операции можно совсем немного изменить этот признак. Разумеется, нам будет проще, если признак будет абсолютно неприступным, ведь тогда гораздо проще делать оценку в силу "фиксированности". Попробуем сначала доказать именно это. Что это за особенность такая?

Подсказка 3:

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

Подсказка 4:

Спустя время можно осознать, что арифметика не особо-то и вяжется сюда. Значит, думаем дальше. Мы меняем два элемента с разницей в 1. Хмм, попробуем просто поисследовать, что происходит при операции. Например, можно начать с анализа соседних чисел с теми, которые мы меняем...

Подсказка 5:

Пусть последовательность выглядела так: ...abc...def.... Меняем b и e. Знаем, что |b − e| = 1. Интересно, может ли случиться так, что b > c, а e < c?

Подсказка 6:

Конечно, нет. Иначе b ≥ c + 1, e ≤ c − 1, то есть b − e ≥ 2, ошибочка однако... Хм, на какую более общую идею это наталкивает?

Подсказка 7:

Отношения (в плане больше или меньше) сохраняются при перестановке b и e. Кажется, мы на верном пути! Итак, какая же у нас идея?

Подсказка 8:

Если рассмотреть в какой-то строке отношения между всеми соседними, то оно всегда будет оставаться таким же! Хммм, как бы изящно записать эти отношения?

Подсказка 9:

Наверное, с помощью знаков < и >. То есть каждой строке сопоставляем такую последовательность из 99 знаков, назовём её признаком. Получается, если у двух строк разные признаки, то одну из другой не получить. А если совпадают, всегда ли можно?

Подсказка 10:

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

Подсказка 11:

n ≤ 2⁹⁹ (осознайте почему). Попробуем же теперь построить пример.

Подсказка 12:

В явном виде строить его довольно трудно. Нужно действовать хитрее! Зафиксируем признак и докажем, что для него можно подобрать нужный набор чисел (доказать это необходимо в общем виде). Это будет ещё одна подзадача для самостоятельного решения) Дело за Вами! Мы в Вас верим!

Показать ответ и решение

Сопоставим строке $x , 1$ $x, 2$ …, $x 100$ чисел от 1 до 100 последовательность из 99 знаков < и > в соответствии с тем, как упорядочены соседние числа. То есть если $xk <xk+1,$ то $k$ -й знак в этой последовательности равен <, в противном случае он равен >.

Заметим, что разрешённые операции над строкой не меняют соответствующую ей последовательность знаков. Действительно, из пары чисел $xk$ и $xk+1$ меняется не более одного и не более чем на 1. Поэтому знак неравенства между ними не может измениться на противоположный.

Сопоставим каждой перестановке знаков расстановку чисел по следующему правилу (далее такие расстановки будем называть выделенными). При $k= 1,$ $2,$ …, $99$ если $xk > xk+1$ (т.е. $k$ -й знак <) поставим на место $xk$ наибольшее из не выбранных ранее чисел, если же $xk < xk+1$ — наименьшее из не выбранных ранее чисел.

Заметим, что при такой последовательности операций числа, не выбранные за первые $k$ шагов, будут образовывать отрезок натурального ряда (а выбранными окажутся несколько наибольших и несколько наименьших чисел от 1 до 100). В частности, $x1 = 1$ или $x1 = 100.$ Число $x100$ заменим на единственное оставшееся число.

Нетрудно видеть, что полученная расстановка чисел соответствует выбранной последовательности знаков. Всего выделенных расстановок будет столько же, сколько и различных последовательностей знаков, то есть $299.$ В силу сказанного выше, разрешёнными операциями никакие две из выделенных строк нельзя сделать одинаковыми. Таким образом, заполнив таблицу $100× 299$ выделенными строками, мы получаем пример для $n= 299.$

Теперь докажем, что из любой строки $A$ длины 100 можно получить выделенную строку $B$ с той же расстановкой знаков. Из этого последует, что $n ≤ 299.$

Предположим, что первые $t− 1$ знаков данной строки

A =(x1,...,x100)

и выделенной строки

B =(y1,...,y100)

совпадают. Если $t= 100,$ то и сами строки совпадают. Пусть $t<100.$ Без ограничения общности будем считать, что $xt < xt+1.$

В силу сказанного выше наборы чисел $yt,$ …, $y100$ и $xt,$ …, $x100$ совпадают и образуют отрезок натурального ряда с наименьшим числом $xt.$ Поскольку $yt < yt+1,$ можно менять в строке $A$ на месте $t$ с числом на единицу меньшим, пока на месте $t$ не окажется число $xt.$

Таким образом, мы добились совпадения первых $t$ символов у нашей строки с выделенной строкой $B.$ Значит, такими операциями можно из любой строки получить выделенную строку, что завершает доказательство оценки.

Ответ:

$299$

Ошибка.
Попробуйте повторить позже

Задача 4#131946Максимум баллов за задание: 7

Окружность $ω$ описана около треугольника $ABC,$ в котором $AB < AC.$ Биссектрисы треугольника $ABC$ пересекаются в точке $I.$ Из середины $M$ стороны $BC$ на прямую $AI$ опущен перпендикуляр $MH.$ Прямые $MH, BI$ и $AB$ ограничивают треугольник $Tb,$ а прямые $MH, CI$ и $AC$ ограничивают треугольник $Tc.$ Описанные окружности треугольников $Tb$ и $Tc$ повторно пересекают окружность $ω$ в точках $′ B$ и $′ C$ соответственно. Докажите, что точка $H$ лежит на прямой $′′ B C .$

Источники: ВСОШ, ЗЭ, 2023, 11.4 (см. olympiads.mccme.ru)

Показать доказательство

Обозначим точки пересечения прямой $MN$ с прямыми $AB,$ $AC,$ $BI$ и $CI$ через $P,$ $Q,$ $X$ и $Y$ соответственно (см. рисунок). Пусть прямые $AI,$ $BI$ и $CI$ повторно пересекают $ω$ в точках $A1,$ $B1$ и $C1$ соответственно. Обозначим

∠BAI = ∠CAI =α,∠ABI = ∠CBI =β,∠ACI = ∠BCI =γ,

тогда $α+ β+ γ = 90∘$ из суммы углов треугольника $ABC.$ Поскольку $MH ⊥AI,$ имеем $∠AQM = 90∘− α.$ Так как четырехугольник $ABA1C$ — вписанный,

∘ ∘ ∠MA1C = 90 − ∠BCA1 = 90 − α

Таким образом,

∠MA1C + ∠MQC =180∘,

поэтому четырёхугольник $A1CQM$ — вписанный. Следовательно, $∠AQA1 = 90∘,$ откуда следует, что точки $A,$ $A1,$ $P,$ $Q$ лежат на окружности $γ,$ построенной на отрезке $AA1$ как на диаметре.

Теперь заметим, что

∠QC′C = ∠QY C = 90∘− ∠CIA1 = 90∘− α − γ =β

Однако из вписанности четырехугольника $BC′CB1$ мы получаем, что

∠CC ′B1 =∠B1BC =β =∠CC ′Q

Следовательно, точки $C ′,$ $Q$ и $B1$ лежат на одной прямой. Аналогично, точки $P,$ $B′$ и $C1$ лежат на одной прямой.

$PIC$

В силу сказанного выше и вписанности четырёхугольника $C1B1CB$ имеем, что

∠CC1B1 =β = ∠CYQ,

поэтому $C1B1 ∥ PQ.$ Поскольку четырёхугольник $B ′C1B1C′$ вписанный,

∠PB ′C′ = ∠C1B1C′ = ∠PQC ′.

Значит, четырёхугольник $′ ′ B QC P$ вписанный. Тогда радикальные оси его описанной окружности, окружности $γ$ и окружности $ω$ пересекаются в одной точке, а это прямые $′ ′ B C ,$ $PQ$ и $AA1.$ Следовательно, точка $H$ лежит на прямой $′ ′ B C ,$ что и требовалось доказать.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Приведём другой способ закончить решение. После того, как установлено, что точки $′ C ,$ $Q$ и $B1$ лежат на одной прямой, и точки $P,$ $B′$ и $C1$ лежат на одной прямой. Обозначим через $N$ середину дуги $BAC.$ Пусть прямая $AX$ повторно пересекает окружность $ω$ в точке $T.$ Заметим, что

′ ∘ 1 ′ ∠CC Y =∠AQY =90 − α= 2∠CC B.

Следовательно, $′ CY$ — биссектриса угла $′ CC B,$ поэтому на прямой $′ C Y$ лежит точка $N.$ Аналогично, она лежит на прямой $′ XB .$ Применяя теорему Паскаля для точек $′ AT C B1BC$ мы получаем, что точка $X,$ точка $Q$ и точка пересечения $′ C T$ и $BC$ лежат на одной прямой. Следовательно, прямые $BC,$ $XQ$ и $′ C T$ Т пересекаются в одной точке, то есть точка $M$ лежит на $′ C T.$ Теперь применяем теорему Паскаля для точек $′ ′ ATC BNA1$ и получаем, что точки $X$ и $M$ вместе с точкой пересечения $AA1$ и $′ ′ B C$ лежат на одной прямой. Значит, точка $H$ лежит на $′ ′ B C ,$ что и требовалось.

Ошибка.
Попробуйте повторить позже

Задача 5#131962Максимум баллов за задание: 7

Изначально на доске написано 10 единиц. Гриша и Глеб играют в игру, делая ходы по очереди. Своим ходом Гриша возводит некоторые 5 чисел на доске в квадрат. Глеб своим ходом выбирает несколько (возможно, ни одного) чисел на доске и увеличивает каждое из них на 1. Если в течение 10 000 ходов на доске появится число, делящееся на 2023, то побеждает Глеб, иначе побеждает Гриша. Кто из игроков имеет выигрышную стратегию, если первым ходит Гриша?

Источники: ВСОШ, ЗЭ, 2023, 11.5 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

Для начала будет полезно изучить само число 2023, 2023 = 7*17². Теперь нужно попытаться угадать ответ, кто же победит?

Подсказка 2:

Пусть Глеб имеет выигрышную стратегию. Тогда он всегда за 10000 ходов успевает добиться делимости. Не кажется ли Вам, что 10000 просто для красоты?

Подсказка 3:

Действительно, это просто красивое число. Значит, побеждает Глеб, и он должен добиваться делимости за не более чем какое-то количество ходов, причём предварительно количество нужно будет угадать и только потом доказывать, что он это сможет сделать. Либо побеждает Гриша, и тогда нужно доказать, что он всегда может поддерживать НЕделимость чисел на 2023. Кажется, проще сначала попробовать доказать второй вариант, ибо достаточно просто придумать алгоритм.

Подсказка 4:

Итак, хотим доказать, что Гриша может всегда "сломать" делимость на 2023, но рассуждать именно про делимость 2023 сложновато, не зря же мы вначале разложили его на множители) Будем пробовать доказать, что Гриша может всегда "сломать" делимость на 7 (7 < 17 и они оба простые, поэтому логичнее начать с 7).

Подсказка 5:

Информации о конкретном числе в ключе "делится или не делится на 7" нам недостаточно. Что же может нам помочь, когда речь идёт о делимости?

Подсказка 6:

Конечно же, модульная арифметика! Рассмотрите, как операция Гриши влияет на остатки.

Подсказка 7:

Если число не делилось на 7 до хода Гриши, то после оно будет давать остаток 1 либо 2, либо 4 по модулю 7. В то же время Глеб может прибавить 1 к остатку своим ходом. На какие мысли об алгоритме Гриши это наталкивает?

Подсказка 8:

Подумаем вот о чём... Гриша возвёл в квадрат некоторое число а, получил a². На какое максимальное количество ходов он может забыть про него? То есть сколько раз подряд он может позволить Глебу изменить число a²?

Подсказка 9:

Если на ≥ 3 хода. То есть a² сравнимо с 4, то за 3 хода Глеб может победить. Значит, забывать про число Гриша может максимум на два хода Глеба. Что это значит?

Подсказка 10:

Если зафиксировать какое-то число, то минимум каждые два хода Гриша должен с ним взаимодействовать (осознайте, что этого достаточно). Осталось придумать такую стратегию... Вам может помочь идея разбиения на группы. Успехов!

Показать ответ и решение

Заметим, что $2023= 7⋅172.$ Гриша разобьёт числа на доске на две группы по 5 и будет возводить в квадрат числа из первой группы и из второй группы по очереди. Легко видеть, что квадраты целых чисел, не кратных 7, при делении на 7 могут давать лишь остатки 1, 2 и 4. Следовательно, после увеличения максимум на 2 числа на доске будут давать при делении на 7 лишь остатки 1, 2, 3, 4, 5 и 6. Значит, ни одно из чисел не будет делиться на 7, а потому не будет делиться и на 2023.

Ответ:

побеждает Гриша

Ошибка.
Попробуйте повторить позже

Задача 6#131963Максимум баллов за задание: 7

Плоскость $α$ пересекает рёбра $AB,BC,CD$ и $DA$ тетраэдра $ABCD$ в точках $X,Y,Z$ и $T$ соответственно. Оказалось, что точки $Y$ и $T$ лежат на окружности $ω,$ построенной на отрезке $XZ$ как на диаметре. Точка $P$ отмечена в плоскости $α$ так, что прямые $P Y$ и $P T$ касаются окружности $ω.$ Докажите, что середины рёбер $AB,$ $BC,$ $CD,DA$ и точка $P$ лежат в одной плоскости.

Источники: ВСОШ, ЗЭ, 2023, 11.6 (см. olympiads.mccme.ru)

Показать доказательство

Из условия задачи мы сразу получаем, что

∘ ∠XY Z =90 = ∠XT Z

Обозначим через $Q$ точку пересечения прямых $XY$ и $ZT,$ через $R$ — точку пересечения прямых $ZY$ и $XT$ (см. первый рисунок). Без ограничения общности можно считать, что точка $Z$ лежит на отрезках $RY$ и $QT.$ Поскольку точка $R$ лежит и в плоскости $ABD,$ и в плоскости $BCD,$ то она лежит на прямой $BD.$ Аналогично, точка $Q$ лежит на прямой $AC.$

$PIC$

Замечим, что $RY$ и $QT$ — высоты треугольника $XQR.$ Тогда $Z$ — точка пересечения высот этого треугольника, и поэтому $XZ ⊥ QR.$ Пусть $M$ — середина отрезка $QR.$ Поскольку $∠QY R= 90∘,$ то $YM = MR = RQ$ по свойству медианы прямоугольного треугольника. Значит,

∠MY R =∠Y RQ =90∘− ∠XQR = ∠ZXQ

Следовательно, прямая $YM$ касается окружности $ω.$ Аналогично, прямая $T M$ тоже касается окружности $ω,$ поэтому точки $M$ и $P$ совпадают.

$PIC$

Рассмотрим две параллельные плоскости $β$ и $γ,$ одна из которых содержит отрезок $AC,$ а другая — отрезок $BD.$ Заметим, что середины всех отрезков, соединяющих точку из плоскости $β$ и точку из плоскости $γ,$ лежат в одной плоскости, параллельной $β$ и $γ.$ Действительно, если ввести декартовы координаты так, что одна из плоскостей задаётся уравнением $z =0,$ а другая — уравнением $z = h$ (где $h$ есть расстояние между плоскостями $β$ и $γ$ ), то середины всех рассматриваемых отрезков лежат в плоскости $z = h∕2.$ Применяя это наблюдение для отрезков $AB,$ $BC,$ $CD,$ $DA,$ $QR,$ мы получаем, что их середины лежат в одной плоскости, что и требовалось.

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#131964Максимум баллов за задание: 7

Назовём многочлен $P (x)$ бицелозначим, если числа $P(k)$ и $P′(k)$ целые при любом целом $k.$ Пусть $P(x)$ — бицелозначный многочлен степени $d,$ и пусть $Nd$ — произведение всех составных чисел, не превосходящих $d$ (произведение пустого множества сомножителей считаем равным 1). Докажите, что старший коэффициент многочлена $Nd⋅P(x)$ — целый.

Источники: ВСОШ, ЗЭ, 2023, 11.7 (см. olympiads.mccme.ru)

Показать доказательство

Многочлен $P(x)$ называется целозначным, если $P(k)$ — целое число при любом целом $k.$ Нам надо доказать, что, если многочлены $P(x)$ и $′ P(x)$ целозначны, причём степень $P(x)$ равна $d,$ то старший коэффициент многочлена $Nd ⋅P (x)$ — целый.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Пусть $P(x)$ — целозначный многочлен степени $d.$ Тогда все коэффициенты многочлена $d!⋅P(x)$ целые.

Доказательство. Рассмотрим многочлен

d Q (x)= ∑ P(i)⋅ (x−-0)(x−-1)⋅⋅⋅(x−-(i−-1))(x−-(i+-1))⋅⋅⋅(x−-d) i=0 (i− 0)(i− 1)⋅⋅⋅(i− (i− 1))(i− (i+1))⋅⋅⋅(i− d)

Его степень не больше $d,$ и его значения совпадают с соответствующими значениями $P(x)$ в точках $x =0,1,2,...,d.$ Это означает, что многочлен $P(x)− Q(x)$ имеет степень не выше $d,$ а также обнуляется в $d+ 1$ точке. Поэтому он нулевой, то есть $P(x)= Q(x).$ (Формула выше — это частный случай интерполяционной формулы Лагранжа.)

Осталось заметить, что в формуле выше в $i$ -м слагаемом знаменатель равен $d−i (−1) i!(d− i)!;$ это число делит $d!,$ поскольку

d! i!(d−-i)! = Cid.

Значит, при умножении каждого слагаемого на $d!$ получается многочлен с целыми коэффициентами.

_________________________________________________________________________________________________________________________________________________________________________________

Перейдём к решению задачи. Индукция по $d.$ База при $d= 0$ тривиальна. Для перехода индукции рассмотрим бицелозначный многочлен $P(x)$ степени $d;$ пусть его старший коэффициент равен $a.$

Если $d$ не является простым числом, то

Nd = dNd−1.

Заметим, что многочлен $ΔP (x)= P(x+ 1)− P (x)$ также бицелозначный, имеет степень $d− 1$ и старший коэффициент $ad.$ По предположению индукции, число

Nd−1⋅ad =Nda

является целым, что и требовалось доказать.

Пусть теперь $d$ — простое число; тогда

Nd =Nd− 1,

и то же рассуждение даёт, что число $dNda$ является целым. Предположим, что $Nda$ — нецелое число; тогда знаменатель числа $a$ (в несократимой записи) делится на простое число $d.$

Заметим, что сумма всех коэффициентов многочлена $P(x)$ — это целое число $P (1).$ Поскольку знаменатель числа $a$ делится на $d,$ среди коэффициентов многочлена $P(x)$ найдётся ещё один, у которого знаменатель делится на $d;$ пусть это коэффициент $b$ при $xi,i< d.$ Заметим, что $i> 0,$ так как число $P(0)$ целое.

Но тогда у целозначного многочлена $P′(x)$ коэффициент при $xi−1$ равен $ib$ и также имеет знаменатель, кратный $d.$ Поскольку $d$ — простое число, отсюда вытекает, что коэффициент при $xi−1$ у многочлена $(d− 1)!P ′(x)$ нецелый, что противоречит лемме.

Ошибка.
Попробуйте повторить позже

Задача 8#131966Максимум баллов за задание: 7

В стране $N$ городов. В ней действует $N (N − 1)$ дорог с односторонним движением: по одной дороге из $X$ в $Y$ для каждой упорядоченной пары городов $X ⁄= Y.$ У каждой дороги есть цена её обслуживания. Для данного $k= 1,$ …, $N$ рассмотрим все способы выделить $k$ городов и $N − k$ дорог так, чтобы из каждого города можно было попасть в какой-то выделенный город, пользуясь только выделенными дорогами. Такую систему городов и дорог с наименьшей суммарной стоимостью обслуживания назовём $k$ -оптимальной. Докажите, что города можно пронумеровать от 1 до $N$ так, что при каждом $k= 1,2,$ …, $N$ существует $k$ -оптимальная система дорог с выделенными городами $1,2,$ …, $k.$

Источники: ВСОШ, ЗЭ, 2023, 11.8 (см. olympiads.mccme.ru)

Показать доказательство

Рассматриваемые сети из $N − k$ дорог называем далее $k$ -сетями. Рассмотрим неориентированный граф, образованный дорогами $k$ -сети. В нём не более чем $k$ компонент связности, поскольку в каждой есть выделенный город. С другой стороны, компонент не менее $k,$ поскольку рёбер всего не более чем $N − k.$ Поэтому компонент ровно $k,$ каждая из них есть дерево, содержит единственный выделенный город и — вспоминая про ориентацию — рёбра каждого дерева направлены по направлению к выделенному городу. В частности, из каждого не выделенного города должна выходить ровно одна дорога, а из выделенного 0 дорог.

Рассмотрим $(k+1)$ -оптимальную сеть $A$ с выделенными городами

y0,y1,...,yk

и $k$ -оптимальную сеть $B$ с выделенными городами

x1,...,xk.

Не умаляя общности, ни из одного $xi$ нельзя добраться в сети $A$ до города $y0.$ Пусть $U$ — множество городов, из которых в $A$ можно добраться до $y0,$ а $α,β$ — множества дорог, выходящих из $U$ в сетях $A,B$ соответственно. Имеем

|α|= |U|− 1, |β|= |U |.

Рассмотрим сеть

D :=(A ∖α)∪β.

Утверждается, что это $k$ -сеть для выделенных городов $y1,...,yk.$ В самом деле, число дорог в ней равно

|D|= N − k− 1− (|U|− 1)+ |U|= N − k.

Из каждого города, кроме $y1,...,yk$ выходит ровно одна дорога. Выезжая из любого города вне $U$ и используя дороги сети, мы по-прежнему можем попасть в один из городов $y1,...,yk.$ Выезжая из города в $U,$ мы либо попадаем вне $U$ — и далее в один из городов $y1,...,yk,$ — либо зацикливаемся в $U.$ Но тогда $β$ содержит цикл, что невозможно.

Рассмотрим сеть

C :=(B ∖β)∪α.

Утверждается, что это $(k+ 1)$ -сеть для выделенных городов $x1,...,$ $xk,y0.$ В самом деле,

|C|= N − k − 1,

и, выезжая из любого города по дорогам сети $C,$ мы либо попадаем в $U$ — и тогда по $α$ доезжаем до $y0,$ — либо ни разу не попадаем в $U$ и тогда доезжаем до одного из городов $x1,...,xk.$

Итак, $C,D$ — $k$ -сеть и $(k+ 1)$ -сеть. Сумма их стоимостей такая же, как у $A$ и $B.$ Значит, они обе оптимальны. Таким образом, для сети $A$ удалось выкинуть выделенный город и найти оптимальную $k$ -сеть с оставшимися выделенными городами. Теперь можно построить требуемую нумерацию в обратном порядке (начиная с пустой $N$ -сети).

Предыдущая подтема

Следующая подтема