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

Поиск
?

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

Всего: 65 1–20 | 21–40 | 41–60 | 61–65

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

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

Каждый член партии доверяет пяти однопартийцам, но никакие двое не доверяют друг другу. При каком минимальном размере партии такое возможно?

Не забудьте показать, что при указанном Вами размере партии это действительно возможно, а при меньших  — нет.

Решение.

Будем представлять партию в виде ориентированного графа: партийцев  — в виде вершин, а если партиец A доверяет партийцу B, то соединим вершину A с B ребром со стрелкой, направленной от A к B. Условие того, что никакие два партийца не доверяют друг другу, эквивалентно условию того, что никакие две вершины не соединены двумя противоположно направленными ориентированными рёбрами. Будем называть это условием одного ребра. Построим пример партии из 11 человек, удовлетворяющей условию задачи. Разместим 11 человек в вершинах правильного 11-угольника A₁ . . . A₁₁. Для каждой вершины A_i направим по ориентированному ребру из неё в каждую из пяти вершин, следующих за ней по часовой стрелке. Утверждается, что условие одного ребра выполнено. Действительно, для каждого ориентированного ребра, идущего от некоторой вершины A_i к A_j, имеется не более 4 вершин, следующих от A_i к A_j в направлении по часовой стрелке. А остальных вершин 11-угольника, отличных от A_i, A_j и вышеупомянутых последовательных вершин между ними не меньше, чем 11 − 6 = 5, и они идут последовательно от A_j к A_i по часовой стрелке «с другой стороны». Предположим противное: условие одного ребра не выполнено, то есть некоторая пара вершин A_i и A_j соединена двумя противоположно направленными рёбрами. Тогда в силу предыдущего, имеется два набора последовательных вершин, каждый из не более, чем 4 вершин: вершины одного набора идут от A_i к A_j по часовой стрелке, а вершины другого  — от A_j к A_i по часовой стрелке. Следовательно, эти наборы не пересекаются, и вместе с вершинами A_i и A_j (итого не более, чем 4 + 4 + 2 = 10 вершин) они покрывают все 11 вершин 11-угольника. Полученное противоречие доказывает, что условие одного ребра выполнено.

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

$C_n в квадрате = дробь: числитель: n левая круглая скобка n минус 1 правая круглая скобка , знаменатель: 2 конец дроби .$

Тем самым,

$5n меньше или равно дробь: числитель: n левая круглая скобка n минус 1 правая круглая скобка , знаменатель: 2 конец дроби равносильно дробь: числитель: левая круглая скобка n минус 1 правая круглая скобка , знаменатель: 2 конец дроби больше или равно 5 равносильно n больше или равно 11$

что и требовалось доказать.

Ответ: 11.

Критерии оценивания выполнения задания	Баллы
Приведено построение партии из 11 человек и доказано, что меньше нельзя.	20
Приведено построение партии из 11 человек, но не доказано, что меньше нельзя.	14
Доказано, что меньше 11 сделать нельзя, но пример не построен.	12
Решение не соответствует ни одному из перечисленных выше критериев.	0
Максимальный балл	20

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

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

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

Решение.

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

Давайте немного порисуем. Представим себе, что в каждую точку, являющуюся концом для трёх сторон шестиугольника, мы поставили точку красным фломастером. А каждый путь по сторонам шестиугольников от красной точки до красной точки мы обвели синим фломастером. Таким образом, синие линии идут по сторонам шестиугольников и через вершины, из которых выходит только две стороны (иными словами, которые являются вершинами ровно для одного шестиугольника). Заметим, что синие линии не пересекаются иначе, чем в своих концах, являющихся красными точками. Легко понять, что если точка является концом для хотя бы одной стороны шестиугольника, она является концом для двух или для трёх сторон: больше чем 3 быть не может потому что все углы равны 120°.

Рис. 1: Пример многоугольника, сделанного из шестиугольников.

Таким образом, мы получили изображение мультиграфа на плоскости. Для него верна формула Эйлера F − E + V  =  2, где F, E, V  — количества граней, рёбер и вершин соответственно. Поскольку все вершины имеют степень 3, 3V  =  2E. Кроме того F = n + 1, поскольку это все шестиугольники и внешняя грань. Из этих трёх уравнений выводится E  =  3n − 3. Пройдём по внешнему циклу. При этом мы шли по всем n шестиугольникам, значит, при n > 1 не менее чем n раз меняли шестиугольник, по которому идем (внимание: этот утверждение неверно, если n = 1: так и ходили по одному шестиугольнику, ни разу его не поменяв). Значит, во внешнем цикле не менее n ребер, значит, в остальном графе не больше 2n − 3 рёбер. Каждое из них состоит ровно из одного отрезка, бывшего стороной для двух шестиугольников, поскольку внутри многоугольника не может быть точек, являющихся концами ровно для двух отрезков сторон. Значит, внутри не больше 4n − 6 сторон шестиугольников, склеенных по парам, значит, на границе лежит не менее 2n + 6 сторон.

Ответ: 2n + 6 при n ≥ 2, 6 при n = 1

Критерии оценивания выполнения задания	Баллы
Приведено полное решение.	20
Незначительные ошибки в доказательстве.	18
Серьезные пробелы в доказательстве (например, не доказано существование шестиугольника, касающегося других не более чем по 2 сторонам).	10
Имеется утверждение о том, что минимальный периметр для n и n + 1 отличается на 2, но доказательство отсутствует. Пример есть.	6
Есть пример на 2n + 6 или имеются идеи, как в критерии выше, но нет внятного примера.	4
Решение не соответствует ни одному из перечисленных выше критериев.	0
Максимальный балл	20

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

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

В вершинах квадрата со стороной 4 расположены четыре города. Эти города надо соединить дорогами так, чтобы из

любого города можно было по ним добраться в любой. Предложите хоть один вариант таких дорог, общей длиной менее 11.

Указание. При решении задачи может оказаться полезным следующее утверждение (которое допустимо использовать без доказательства). Пусть внутренние углы треугольника ABC меньше 120°. Сумма расстояний $AT плюс BT плюс CT$ от точки T до вершин треугольника минимальна, если из точки T стороны треугольника видны под углом 120° (T  — точка Торичелли треугольника). Если же один из углов треугольника больше или равен 120°, то точкой минимума суммы расстояний будет вершина этого угла.

Решение.

Предположим, что у нашей системы дорог перекрестков нет, то есть имеется одна дорога, соединяющая последовательно вершины квадрата E, F, G и H. Тогда ее длина будет не меньше трех сторон квадрата (буквы «П» на рис. (а)), то есть не меньше 12 (дорога, соединяющая соседние вершины квадрата, не меньше его стороны). Значит, искомая (а в идеале кратчайшая) система дорог должна иметь перекрестки (например, как на рис. (д)). Чтобы понять каким образом можно эффективно общую длину дорог уменьшать, полезно прежде обратить внимание на некоторые свойства, которыми кратчайшая система дорог обязана обладать:

1.  Кратчайшая система дорог состоит из отрезков, соединяющих перекрестки и вершины квадрата. Это очевидно, поскольку кратчайшим путем из одной точки в другую является отрезок прямой. Отметим без доказательства, хотя и это почти очевидно, что для любой системы городов кратчайшая система дорог их соединяющая  — это связный граф без замкнутых путей, ребрами которого служат отрезки.

2.  Каждый перекресток должен быть соединен минимум с тремя вершинами графа (вершинами квадрата или перекрестками). (Если он соединен только с двумя, то смысла в нем немного: его можно удалить, а эти две вершины соединить напрямую; получится короче.)

3.  Угол между любыми двумя дорогами, выходящими из одного перекрестка (или из одной вершины квадрата) не может быть меньше 120°. Действительно, пусть из точки A выходят дороги AB и AC, и угол BAC меньше 120°. Тогда дороги AB и AC можно заменить дорогами с меньшей суммарной длиной. Если в треугольнике ABC все внутренние углы меньше 120°, то дороги AB и AC заменим на дороги TA, TB и TC, где T  — точка Торичелли треугольника ABC (рис. (б)). Если же, например, угол B больше 120°, то AB и AC заменим на AB и BC (рис. (в)).

4.  Из одного перекрестка выходят ровно три дороги под углами 120° (иначе длина дорог может быть уменьшена). Это немедленно следует из свойств (2) и (3).

Предположим, что система дорог обладает одним перекрестком. Если он соединен со всеми вершинами рис. (г), то длина дорог не меньше суммы диагоналей, которая равна $8 корень из: начало аргумента: 2 конец аргумента больше 11.$ Если же он соединен только с тремя вершинами (рис. (д)), то T  — точка Торичелли треугольника EFH, вершина G соединена с F. В этом случае длина дорог приблизительно равна 11,7. Более того, нарушено свойство (3), так как $\angle THG меньше 120 градусов,$ а значит длину дорог можно уменьшить, добавив еще один перекресток (как в случае на рис. (б)).

Пусть перекрестков два. Из соображений симметрии расположим их на параллельной двум сторонам оси симметрии квадрата (рис. (е)) так, чтобы из каждого перекрестка дороги выходили под углами 1200 (свойство (4)). В этом случае суммарная длина дорог равна $4 левая круглая скобка корень из: начало аргумента: 3 конец аргумента плюс 1 правая круглая скобка меньше 10,92.$

Ответ: например, система дорог с двумя перекрестками на параллельной двум сторонам оси симметрии квадрата (рис. (е)). Из каждого перекрестка дороги выходят под углами 120°. Их суммарная длина равна $4 левая круглая скобка корень из: начало аргумента: 3 конец аргумента плюс 1 правая круглая скобка меньше 11.$

Комментарий.

Система дорог на рис. (е) называемая сетью Штейнера данных четырех точек, вершин квадрата E, F, G и H. Без доказательства отметим, что эта система имеет минимальную длину из всех возможных.

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

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

В некоторой стране 450 городов и 6 авиакомпаний. Каждые два города соединены рейсами одной из шести авиакомпаний. Можно ли утверждать, что найдётся авиакомпания и больше 150 городов, между любыми двумя из которых можно добраться рейсами этой авиакомпании (возможно, с пересадками)?

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

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

В некоторой стране 200 городов и 8 авиакомпаний. Каждые два города соединены рейсами одной из восьми авиакомпаний. Можно ли утверждать, что найдётся авиакомпания и больше 50 городов, между любыми двумя из которых можно добраться рейсами этой авиакомпании (возможно, с пересадками)?

Решение.

Построим контрпример. Разобьём города на 8 групп по 25 городов. Назовём эти группы A, B, C, D, E, F и H.

Внутри каждой группы соединим города рейсами компании номер 1.

Компания номер 2 будет соединять города группы A с городами группы B, C с H, D с G, a E c F.

Компания номер 3 будет соединять города группы A с городами группы D, B с C, E с H, a F c G.

Компания номер 4 будет соединять города группы A с городами группы F, G с H, B с E, a C с D.

Компания номер 5 будет соединять города группы A с городами группы H, B с G, C с F, а E с D.

Компания номер 6 будет соединять города группы A с городами группы E, B с F, C с G, а D c H.

Компания номер 7 будет соединять города группы A с городами группы C, B с H, D с F, a E c G.

Компания номер 8 будет соединять города группы A с городами группы G, F с H, D с B, a E c C.

Таким образом, рейсы компании номер 1 связывают по 25 городов, а рейсы остальных компаний ровно по 50.

Это построение схематично изображено на рисунке. Разные компании обозначены разными цветами. Данный контрпример, разумеется, не единственный.

Ответ: Нет, это не обязательно верно.

Аналоги к заданию № 740: 739 Все

Решение · Прототип задания · Помощь

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

В стране 50 городов, каждые два города соединены (двусторонними) авиалиниями, цены всех перелетов попарно различны (для любой пары городов цена перелета «туда» равна цене «обратно»). В каждом городе находится турист. Каждый вечер все туристы переезжают: богатые туристы  — по самой дорогой, бедные  — по самой дешевой линии, ведущей из соответствующего города. Через k дней оказалось, что в каждом городе снова по одному туристу. За это время ни один турист не посетил никакой город дважды. При каком наибольшем k такое возможно?

(К. Кохась)

Решение.

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

Допустим, что среди туристов имеется 25 (или более) «богачей». Нарисуем граф: вершины  — это города, из каждого города проведем самый дорогой выходящий путь. Тогда этот граф представляет собой лес, в каждом дереве которого все ребра направлены к корню, за исключением единственного ребра, выходящего из корня,  — это ребро в дереве как бы двустороннее. Возьмем богача, который расположен ближе всего к корню своего дерева. Этот богач будет в течение 25 ходов самым близким к корню. Значит, он проедет по городам, в которых еще не было других богачей. Это может быть только если граф  — это путь из 50 вершин, богачи занимают первые 25 вершин этого пути (т. е. половину) и гуськом движутся по этому пути в сторону второй половины. Отсюда следует, что богачей не может быть больше 25, а также что количество переездов тоже не превосходит 25. Тогда бедных туристов тоже 25 и они двигаются по аналогичному «бедному» пути, причем в начальный момент они занимают всю вторую половину «богатого» пути. Эти пути не имеют общих звеньев, и при этом движение бедняков таково, что с каждым ходом они должны освобождать от своего присутствия очередную вершину второй половины богатого пути, смещаясь гуськом в первую половину. Тогда движение туристов может происходить, например, следующим образом. Обозначим города $A_1, A_2, \ldots,A_50.$ Допустим, что путь

$A_1 arrow A_2 arrow A_3 arrow умножить на s arrow A_49 arrow A_50$

составлен из самых дорогих авиалиний, для определенности пусть цена перелета $A_i arrow A_i плюс 1$ равна $10 в степени левая круглая скобка 6 правая круглая скобка минус i$ рублей. А «бедный путь» пусть сначала проходит по городам с большими четными номерами, потом  — по городам с большими нечетными, а далее  — с малыми: сначала с четными, потом с нечетными:

$A_26 arrow A_28 arrow умножить на s arrow A_50 arrow A_27 arrow A_29 arrow умножить на s arrow A_49 arrow A_2 arrow A_4 arrow умножить на s arrow A_24 arrow A_1 arrow A_3 arrow умножить на s arrow A_25.$

Цены этих авиалинии пусть убывают от 49 до 1 рубля при движении вдоль этого пути. Цены остальных авиалиний назначим произвольно в диапазоне от 100 до 100 000 рублей.

Ответ: при $k=25.$

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

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

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

(Д. Картов)

Решение.

Построим орграф G, города  — вершины, дороги  — ориентированные ребра (будем называть их стрелками). Напомним, что орграф называется сильно связном, если между любыми двумя вершинами существует путь по стрелкам (именно такой орграф у нас получился). Если орграф не является сильно связным, его вершины можно разбить на компоненты сильной связности  — максимальные по включению сильно связные подграфы. В отличие от обычных компонент связности, между двумя компонентами сильной связности могут быть проведены стрелки, но только одного направления, иначе эти две компоненты нужно было бы объединить в одну.

Компонента сильной связности называется крайней, если из нее не выходит ни одной стрелки в другие компоненты сильной связности. Такая компонента сильной связности обязательно есть (докажите это!).

Вернемся к решению задачи. Для цикла Z в орграфе G обозначим через $G_Z$ граф, полученный из G в результате удаления стрелок цикла Z. Предположим противное, пусть для любого цикла Z граф $G_Z$ не сильно связен. Тогда выберем Z так, чтобы одна из крайних компонент сильной связности орграфа $G_Z$ содержала наименьшее возможное число вершин обозначим ее U. Из каждой вершины U выходит хотя бы две стрелки в орграфе G, а значит, хотя бы одна стрелка в орграфе $G_Z$ (цикл проходит по вершине не более одного раза). Следовательно, в компоненте U более одной вершины. Так как орграф U сильно связен, в нем есть цикл C.

Рассмотрим орграф $G_C .$ Все отличные от U компоненты $G_Z$ остались сильно связными подграфами и в графе $G_C,$ так как все стрелки между ними сохранились, а стрелки цикла Z  — добавились. Если орграф $U_C$ (результат удаления из U рёбер цикла C) сильно связен, то и $G_C$ сильно связен, в этом случае задача решена. Если же $U_C$   — не сильно связен, то в нем есть крайняя компонента сильной связности W, строго меньшая, чем U. Легко понять, что W является крайней компонентой сильной связности и в $G_C$ (это сильно связный орграф, из которого не выходит рёбер вовне), что противоречит выбору цикла Z.

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

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

В стране некоторые математики знакомы между собой и при любом разбиении математиков на две непустые группы найдутся двое знакомых из разных групп. Известно, что если посадить за круглый стол любой набор из 4 или более математиков так, чтобы любые два соседа были знакомы, то за столом найдутся двое знакомых, не сидящих рядом. Обозначим через c_i количество наборов из i попарно знакомых математиков. Докажите, что $c_1 минус c_2 плюс c_3 минус c_4 плюс \dots =1.$

(Ф. Петров)

Решение.

Рассмотрим граф знакомств математиков. По условию этот граф хордовий, т. е. в нем любой цикл из 4 или более вершин содержит хорду (пару смежных вершин, не соседних в цикле). Докажем, что для хордового графа G выражение

$f левая круглая скобка G правая круглая скобка :=c_1 минус c_2 плюс c_3 минус \ldots,$

где $c_i$   — количество клик в G на i вершинах, равно числу $k левая круглая скобка G правая круглая скобка$ компонент связности графа G.

Решение 1. Предположим, что это не так, и рассмотрим в качестве G наименьший по числу вершин контрпример. Ясно, что граф G содержит больше одной вершины и связен (иначе одна из компонент связности была бы меньшим контрпримером). Удалим из графе G произвольную вершину υ, пусть новый граф $дробь: числитель: G , знаменатель: v конец дроби$ распался на компоненты $G_1, \ldots, G_k .$ Пусть $H_1,$ $H_2, \ldots, H_k$   — подграфы в $G_1, \ldots, G_k$ соответственно на соседях вершины υ. Несложно видеть, что

$f левая круглая скобка G правая круглая скобка =1 плюс \sum_i=1 в степени левая круглая скобка k правая круглая скобка f левая круглая скобка G_i правая круглая скобка минус \sum_i=1 в степени левая круглая скобка k правая круглая скобка f левая круглая скобка H_i правая круглая скобка , \qquad левая круглая скобка * правая круглая скобка$

где слагаемое 1 соответствует клике $левая фигурная скобка v правая фигурная скобка ,$ слагаемые $f левая круглая скобка G_i правая круглая скобка$   — кликам, не содержащим υ, слагаемые  — $f левая круглая скобка H_i правая круглая скобка$   — кликам, содержащим υ (при удалении из них вершины υ меняется четность, а стало быть, знак в выражении для f). В силу минимальности контрпримера $f левая круглая скобка G_i правая круглая скобка =1,$ $f левая круглая скобка H_i правая круглая скобка =k левая круглая скобка H_i правая круглая скобка .$ Проверим, что $k левая круглая скобка H_i правая круглая скобка =1$ при всех i. Предположим противное, тогда вершины одного из графов $H_i$ можно разбить на два непустых подмножества $V в степени левая круглая скобка минус правая круглая скобка ,$ $V в степени левая круглая скобка плюс правая круглая скобка$ так, что ни одно ребро не ведет из $V в степени левая круглая скобка минус правая круглая скобка$ в $V в степени левая круглая скобка плюс правая круглая скобка .$ Рассмотрим наименьший по числу ребер путь $x \ldots y$ из $V в степени левая круглая скобка минус правая круглая скобка$ в $V в степени левая круглая скобка плюс правая круглая скобка$ в графе $G_i.$ Тогда цикл $v x \ldots y v$ не имеет хорды в графе $G .$ Мы проверили, что $f левая круглая скобка H_i правая круглая скобка =f левая круглая скобка G_i правая круглая скобка$ при всех i. Тогда по формуле (*) $f левая круглая скобка G правая круглая скобка =1=k левая круглая скобка G правая круглая скобка ,$ т. е. граф G оказался не контрпримером.

Решение 2. Назовем вершину допустимой, если все ее соседи попарно смежными между собой.

Лемма. В хордовом графе, имеющем хотя бы две вершины, есть хотя бы две допустимые вершины.

Доказательство. Предположив противное, рассмотрим наименьший по числу вершин контрпример  — граф G. Заметим, что в G нет вершины υ, смежной со всеми (иначе $дробь: числитель: G , знаменатель: v конец дроби$   — меньший контрпример). Пусть υ — недопустимая вершина в G, N  — множество соседей вершины υ, $H= дробь: числитель: G , знаменатель: левая круглая скобка N \cup v правая круглая скобка конец дроби$   — граф на оставшихся вершинах. Заметим, что если $u_1,$ $u_2$   — несмежные соседи υ, то не существует пути из $u_1$ в $u_2,$ все промежуточные вершины которого принадлежат H,  — иначе бы наименьший по числу ребер подобный путь, дополненный путем $u_2 v u_1,$ оказался бы циклом без хорд. Пусть $H_1$   — одна из компонент связности графа $H, N_1 минус$ множество вершин в N, имеющих соседа в $H_1.$ По доказанному $N_1$   — клика, так что $N_1 не равно q N .$ Рассмотрим (хордовый, разумеется) граф на вершинах υ, $N_1,$ $H_1 .$ В нем в силу минимальности контрпримера имеется допустимая вершина w, отличная от υ. Она не может принадлежать $N_1,$ потому что каждая вершина в $N_1$ имеет соседями υ и какую-то вершину в $H_1.$ Значит, она принадлежит $H_1,$ а потому является допустимой и в G. Чтобы найти допустимую вершину, отличную от w, повторим рассуждение, взяв в качестве исходной вершины υ соседа вершины w.

Возвращаясь к решению задачи, будем рассуждать по индукции по числу вершин. Для допустимой вершины υ индукционный переход от графа $дробь: числитель: G, знаменатель: v конец дроби$ к графу G очень простой: если она изолированная, интересующая нас сумма увеличивается на 1, в противном случае ни сумма, ни число компонент связности не меняются.

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

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

Пусть между городами A, B, C и D есть дороги AB и CD, но нет дорог BC и AD. Назовем перестройкой замену пары дорог AB и CD на пару дорог BC и AD. Изначально в стране было несколько городов, некоторые пары городов были соединены дорогами, причем из каждого города выходило по 100 дорог. Министр нарисовал новую схему дорог, в которой из каждого города по-прежнему выходит 100 дорог. Известно, что как в старой, так и в новой схемах никакие два города не соединены более, чем одной дорогой. Докажите, что новую схему можно получить из старой с помощью нескольких перестроек.

Решение.

Рассмотрим множество M, состоящее из всех возможных 100-регулярных графров на данном множестве вершин V (наши две схемы дорог  — среди них). Докажем что любые два графа из М можно перевести друг друга серией перестроек. Для двух графов $G, G в степени левая круглая скобка \prime правая круглая скобка принадлежит M$ пусть $F левая круглая скобка G, G в степени левая круглая скобка \prime правая круглая скобка правая круглая скобка$   — множество необщих рёбер этих графов, а

$f левая круглая скобка G, G в степени левая круглая скобка \prime правая круглая скобка правая круглая скобка =\left|F левая круглая скобка G, G в степени левая круглая скобка \prime правая круглая скобка правая круглая скобка | .$

Очевидно $f левая круглая скобка G, G в степени левая круглая скобка \prime правая круглая скобка правая круглая скобка$ четно, а в $F левая круглая скобка G, G в степени левая круглая скобка \prime правая круглая скобка правая круглая скобка$ поровну рёбер из G и $G в степени левая круглая скобка \prime правая круглая скобка .$

Предположим, что существуют пары непереводимых друг в друга перестройками графов в M и рассмотрим такую пару графов $левая круглая скобка A, B правая круглая скобка$ с минимальным $f левая круглая скобка A, B правая круглая скобка .$ Граф $H= левая круглая скобка V, F левая круглая скобка A, B правая круглая скобка правая круглая скобка$ имеет в каждой вершине поровну рёбер из A и из B. Следовательно, в H существует чередующийся цикл  — в котором рёбра A и B чередуются. Рассмотрим минимальный такой цикл $Z=a_1 a_2 \ldots a_2 k$ (это не обязательно простой цикл, вершины в нем могут повторяться). Первая наша цель  — найти на этом цикле четыре последовательные различные вершины. В самом деле, пусть среди a₁, a₂, a₃, a₄ есть совпадающие. Очевидно, возможно лишь совпадение $a_1=a_4.$ Так как рёбра цикла не повторяются, тогда $a_2 не равно q a_5$ и в качестве искомой четверки подойдет a₂, a₃, a₄, a₅.

Итак, не умаляя общности будем считать, что все вершины a₁, a₂, a₃, a₄ различны, причем $a_1a_2, a_3 a_4 принадлежит E левая круглая скобка A правая круглая скобка$ и $a_2 a_3 принадлежит E левая круглая скобка B правая круглая скобка .$ Рассмотрим три случая.

a) Когда $a_1 a_4 принадлежит E левая круглая скобка B правая круглая скобка .$ Тогда проведем перестройку $a_1 a_2 a_3 a_4$ в графе B (возможно, так как $a_1 a_2, a_3 a_4 \notin E левая круглая скобка B правая круглая скобка правая круглая скобка$ и получим граф C с

$f левая круглая скобка A,C правая круглая скобка =f левая круглая скобка A, B правая круглая скобка минус 2 .$

По предположению, C можно получить из A перестройками, значит, можно получить и B.

b) Когда $a_1 a_4 принадлежит дробь: числитель: E левая круглая скобка A правая круглая скобка , знаменатель: E левая круглая скобка B правая круглая скобка конец дроби .$ Тогда $a_1 a_4 a_5 \ldots a_2 k$   — чередующийся цикл, меньший чем Z, противоречие.

c) Когда $a_1 a_4 \notin E левая круглая скобка A правая круглая скобка \cup E левая круглая скобка B правая круглая скобка .$ Тогда проведем перестройку $a_1 a_2 a_3 a_4$ в графе A (возможно, так как $a_2 a_3, a_4 a_1 \notin$ $E левая круглая скобка A правая круглая скобка правая круглая скобка$ и получим граф C с

$f левая круглая скобка B, C правая круглая скобка =f левая круглая скобка A, B правая круглая скобка минус 2.$

По предположению, C можно получить из B перестройками, значит, можно получить и A.

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

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

В городе построено 2019 станций метро. Некоторые пары станций соединены тоннелями, причем от любой станции по тоннелям можно добраться до любой другой. Мэр распорядился организовать несколько линий метро: каждая линия должна включать в себя несколько различных станций, последовательно соединенных тоннелями (по одному и тому же тоннелю может проходить несколько линий). При этом каждая станция должна лежать хотя бы на одной линии. Для экономии средств следует сделать не более k линий. Оказалось, что приказ мэра неосуществим. При каком наибольшем k это могло произойти?

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

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

В социальной сети у каждого пользователя не более десяти друзей (отношение «дружба» симметрично). Сеть связна: если, узнав интересную новость, пользователь начинает рассылать её своим друзьям, те своим и так далее, то в итоге новость узнают все пользователи. Докажите, что администрация сети может разбить пользователей на группы так, чтобы выполнялись следующие условия:

1)  каждый состоит ровно в одной группе;

2)  каждая группа связна в указанном выше смысле;

3)  одна из групп содержит от 1 до 100 членов, а каждая из остальных от 100 до 900 членов.

Решение.

Социальная сеть представляет собой граф, в котором люди  — это вершины, а отношение «дружба»  — ребра. Достаточно рассмотреть случай, когда этот граф является деревом. В требованиях условия задачи группу, в которой состоит от 1 до 100 членов, будем называть малой, а группу, где от 100 до 900 членов,  — большой. Докажем утверждение задачи индукцией по числу пользователей сети. База индукции: $n меньше или равно 900.$ Если в сети не более 100 пользователей, объявим их всех малой группой. Если в сети от 101 до 900 пользователей, назначим малой группой любого пользователя, соответствующего висячей вершине, а всех остальных запишем в большую группу.

Индукционный переход. Достаточно проверить, что если число пользователей больше 900, то можно подобрать большую группу, при удалении которой граф останется связным. Подвесим наше дерево и рассмотрим наиболее далекую от корня вершину A (одну из вершин), у которой больше 900 потомков. У каждого из сыновей вершины A не более 900 потомков, при этом количество сыновей  — не более 9. Если у каждого из сыновей A не более 99 потомков, то в сумме у A не более $9 умножить на 99 меньше 900$ потомков, что противоречит выбору вершины $A .$ Значит, один из сыновей A имеет от 100 до 900 потомков, назначим его и его потомков большой группой.

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

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

В графе 400 вершин. Для любого ребра AB назовём каракатицей набор всех ребер, выходящих из вершин A и B (включая само ребро AB). На каждом ребре графа стоит число 1 или −1. Известно, что сумма чисел на ребрах любой каракатицы больше или равна 1. Докажите, что сумма чисел на всех ребрах графа не меньше чем −10000.

Решение.

Назовем весом вершины A сумму чисел на всех выходящих из нее ребрах; обозначим это число через $v левая круглая скобка A правая круглая скобка .$ Заметим, что сумма весов всех вершин графа ровно в два раза больше суммы чисел на всех его ребрах. Достаточно доказать, что сумма всех весов не меньше −20000. Из условия сразу следует, что сумма весов любых двух смежных вершин больше или равна 0. Выберем в нашем графе максимальное паросочетание, пусть в нём задействовано k рёбер. Сумма весов всех $2k$ их вершин больше или равна 0. Осталось доказать, что сумма весов остальных $400 минус 2 k$ вершин больше или равна −20000. Пусть S  — множество всех этих вершин.

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

Рассмотрим одно из ребер UV, входящее в максимальное паросочетание. Несложно проверить, что из вершин U и V в множество S может вести суммарно не более $|S|=400 минус 2 k$ ребер. Из этого следует, что между вершинами паросочетания и множеством S есть не более

$k умножить на левая круглая скобка 400 минус 2 k правая круглая скобка =2 k левая круглая скобка 200 минус k правая круглая скобка меньше или равно 2 умножить на 100 умножить на 100=20000$

ребер. На каждом из них стоит число 1 или −1, поэтому сумма чисел на этих рёбер не меньше, чем −200000, что и требовалось доказать.

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

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

В стране 100 городов, между ними действует несколько беспосадочных авиалиний так, что от любого города до любого можно добраться, возможно, с пересадками. Для каждой пары городов вычислили наименьшее количество перелётов, необходимых чтобы добраться от одного до другого. Назовём транспортной затруднённостью страны сумму квадратов этих 4950 чисел. Какое наибольшее значение может принимать транспортная затруднённость? Ответ должен быть дан в виде числа (в десятичной системе счисления).

Решение.

Сначала докажем, что транспортная затруднённость наибольшая в случае, когда города связаны «по цепочке».

Действительно, можно считать граф деревом (иначе выкинем часть рёбер так, чтобы осталось дерево  — затруднённость увеличится). Выберем в дереве самый длинный путь. Допустим, что есть вершины, не входящие в этот путь. Тогда среди них найдётся висячая вершина x (то есть вершина, в которую ведёт только одно ребро). Пусть y  — ближайшая к x вершина самого длинного пути. Перенесём всю «ветку», отходящую от y и содержащую x, в конец самого длинного пути, более удалённый от y. Заметим, что в результате попарные расстояния между вершинами в пределах «ветки» не изменились, расстояния между вершинами вне ветки  — тоже. При этом легко видеть, что для каждой вершины ветки сумма квадратов расстояний до всех остальных вершин возросла. Действительно, если k  — расстояние от некой вершины z ветки до y, то набор расстояний от z до вершин вне ветки (включая y) был

$k, k плюс 1, k плюс 1, k плюс 2, k плюс 2, \ldots, k плюс s, k плюс s, k плюс s плюс 1, k плюс s плюс 2, \ldots, k плюс s плюс t,$ $k, k плюс 1, k плюс 1, k плюс 2, k плюс 2, \ldots, k плюс s, k плюс$
$плюс s, k плюс s плюс 1, k плюс s плюс 2, \ldots, k плюс s плюс t,$

а стал $k, k плюс 1, k плюс 2, k плюс 3, \ldots$

Такими «перевешиваниями» можно привести граф к виду цепочки, причём затруднённость всё время будет возрастать; значит, для цепочки она максимальна.

Теперь посчитаем затруднённость для «цепочки». Задача сводится к нахождению суммы

$99 умножить на 1 в квадрате плюс 98 умножить на 2 в квадрате плюс 97 умножить на 3 в квадрате плюс \ldots плюс 1 умножить на 99 в квадрате .$

Обозначим

$S_n в квадрате =1 в квадрате плюс 2 в квадрате плюс \ldots плюс n в квадрате , S_n в кубе =1 в кубе плюс 2 в кубе плюс \ldots плюс n в кубе .$

Как известно,

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

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

(это можно доказать по индукции). Заметим, что искомая сумма равна

$100 умножить на левая круглая скобка 1 в квадрате плюс 2 в квадрате плюс \ldots плюс 99 в квадрате правая круглая скобка минус левая круглая скобка 1 умножить на 1 в квадрате плюс 2 умножить на 2 в квадрате плюс \ldots плюс 99 умножить на 99 в квадрате правая круглая скобка =100 S_99 в квадрате минус S_99 в кубе = =$
$=100 умножить на дробь: числитель: 99 умножить на левая круглая скобка 99 плюс 1 правая круглая скобка умножить на левая круглая скобка 2 умножить на 99 плюс 1 правая круглая скобка , знаменатель: 6 конец дроби минус левая круглая скобка дробь: числитель: 99 умножить на левая круглая скобка 99 плюс 1 правая круглая скобка , знаменатель: 2 конец дроби правая круглая скобка в квадрате =32 835 000 минус 24 502 500=8 332 500.$ $100 умножить на левая круглая скобка 1 в квадрате плюс 2 в квадрате плюс \ldots плюс 99 в квадрате правая круглая скобка минус левая круглая скобка 1 умножить на 1 в квадрате плюс 2 умножить на 2 в квадрате плюс \ldots плюс 99 умножить на 99 в квадрате правая круглая скобка =100 S_99 в квадрате минус S_99 в кубе =$
$= =100 умножить на дробь: числитель: 99 умножить на левая круглая скобка 99 плюс 1 правая круглая скобка умножить на левая круглая скобка 2 умножить на 99 плюс 1 правая круглая скобка , знаменатель: 6 конец дроби минус левая круглая скобка дробь: числитель: 99 умножить на левая круглая скобка 99 плюс 1 правая круглая скобка , знаменатель: 2 конец дроби правая круглая скобка в квадрате =$
$=32 835 000 минус 24 502 500=8 332 500.$ $100 умножить на левая круглая скобка 1 в квадрате плюс 2 в квадрате плюс \ldots плюс 99 в квадрате правая круглая скобка минус левая круглая скобка 1 умножить на 1 в квадрате плюс 2 умножить на 2 в квадрате плюс \ldots плюс 99 умножить на 99 в квадрате правая круглая скобка =$
$=100 S_99 в квадрате минус S_99 в кубе = =$
$=100 умножить на дробь: числитель: 99 умножить на левая круглая скобка 99 плюс 1 правая круглая скобка умножить на левая круглая скобка 2 умножить на 99 плюс 1 правая круглая скобка , знаменатель: 6 конец дроби минус левая круглая скобка дробь: числитель: 99 умножить на левая круглая скобка 99 плюс 1 правая круглая скобка , знаменатель: 2 конец дроби правая круглая скобка в квадрате =$
$=32 835 000 минус 24 502 500=8 332 500.$

Ответ: 8 332 500.

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

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

Развернуть

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

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

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

1.1 Докажите, что в любой момент может произойти миграция.

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

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

Необходимо соединить в одну электрическую сеть четыре светильника, находящихся в вершинах квадрата со стороной 4 метра. Хватит ли на это 11 метров провода? Другими словами, существует ли связный граф, содержащий вершины квадрата со стороной 4, сумма длин ребер которого не превосходит 11?

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

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

В однокруговом хоккейном турнире принимало участие 2016 команд. По регламенту турнира за победу дается 3 очка, за поражение 0 очков, а в случае ничьей играется дополнительное время, победитель которого получает 2 очка, а проигравший  — 1 очко. По окончании турнира Остапу Бендеру сообщили количество очков, набранных каждой командой, на основании чего он сделал вывод, что не менее N матчей закончились дополнительным временем. Найдите наибольшее возможное значение N.

Решение.

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

Зафиксируем количество набранных очков командами и посмотрим на графы, соответствующие данному распределению очков. Среди всех таких графов выберем граф G, в котором количество красных ребер минимально.

Лемма. B красном подграфе графа G нет следующих подграфов:

1)  неориентированных циклов;

2)  ориентированных путей длины 2;

3)  вершин степени 3 и более;

4)  неориентированных путей длины 4.

Доказательство.

Покажем, как можно уменьшить количество красных ребер, если есть описанные выше подграфы.

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

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

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

Не ограничивая общности, можно считать, что ребра ведут из B в C и из C в D. Получается два случая: в первом ребро ведет из B в D, а во втором из D в B.

Тогда сотрем все ребра между A, B, C, D и нарисуем заново следующим образом:

В обоих случаях рисуем синие ребра из B в A, из A в C, из A в D. В первом случае проведем красные из B в D и из B в C и синее из C в D. Во втором случае проводим красные из D в B и из D в C и синее из C в B.

Итого распределение очков не поменялось, а количество красных ребер уменьшилось.

4.  Предположим, что есть неориентированный красный путь длины 4: A, B, C, D, E. Тогда можно считать, что красные ребра ориентированы следующим образом: $\overrightarrowA B, \overrightarrowC B,$ $\overrightarrowC D,$ $\overrightarrowE D,$ а оставшиеся ребра синие.

Если A обыграла D, то можно изменить ребра AB, BC, CD, AD следующим образом: ребра $\overrightarrowA B,$ $\overrightarrowC D$ сделаем синими, а ребра $\overrightarrowA D,$ $\overrightarrowB C$   — красными. Распределение очков не поменялось, а количество красных ребер уменьшилось, поэтому далее можно считать, что D выиграла у A, а B выиграла у E.

Если B обыграла D, то изменим ребра AB, AD, BC, BD, CD следующим образом: ребра $\overrightarrowC D,$ $\overrightarrowD B,$ $\overrightarrowB A$ сделаем синими, a $\overrightarrowA D,$ $\overrightarrowB C$   — красными.

Если D обыграла B, то изменим ребра BC, BD, BE, CD, DE: ребра $\overrightarrowC B,$ $\overrightarrowB D,$ $\overrightarrowD E$ сделаем синими, а $\overrightarrowE B,$ $\overrightarrowD C$   — красными.

Распределение очков не поменялось, количество красных ребер уменьшилось.

Таким образом, граф на красных ребрах без ориентации является лесом, в котором каждое дерево является цепочкой не более чем из 4 вершин. Тогда количество красных ребер равно $2016 минус T,$ где T  — количество деревьев в графе на красных ребрах. Так как в каждом дереве не более 4 вершин, $T больше или равно 504,$ то есть $N меньше или равно 1512.$

Рассмотрим турнир из 4 команд A, B, C, D. Пусть в нем peбра $\overrightarrowA B,$ $\overrightarrowA D,$ $\overrightarrowC D$   — красные, а ребра $\overrightarrowA C,$ $\overrightarrowB C,$ $\overrightarrowB D$   — синие. Тогда команды A, B набрали по 7 очков, а команды C, D  — по $2 .$

Заметим, что при таком распределении очков должно быть сыграно не менее 3 овертаймов, так как в дополнительное время должны закончится матчи между A и B и между C и D, так как A и B не могли проиграть в основное время, а C и D не могли победить в основное время. Если все оставшиеся матчи завершились в основное время, то суммарное количество очков у A и B будет кратно 3  —противоречие.

Разобьем 2016 команд на четверки (A₁, B₁, C₁, D₁), ..., (A₅₀₄, B₅₀₄, C₅₀₄, D₅₀₄). Пусть внутри четверок матчи закончились так, как описано выше, а при $i меньше j$ команда из i-й четверки побеждает команду из j-й в основное время. Тогда из полученного распределения очков можно сделать вывод, что команда из i-й четверки действительно побеждает команду из j-й в основное время. В описанном случае внутри каждой четверки будет распределение очков 7, 7, 2, 2, поэтому будет не менее 3 овертаймов, а значит, всего овертаймов не менее 1512.

Ответ: $N=1512.$

Критерии оценивания	Балл
Полное решение	+
Неверное решение	−

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

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

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

Решение.

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

Остается показать, что меньшего числа туземцев недостаточно.

Способ I. Облегчим задачу: пусть N туземцев не переправляются через реку, а просто совершают не более $N минус 1$ прогулки вдвоем по озеру с возвращением в компанию. Докажем, что даже в этой задаче $N больше или равно 2 в степени левая круглая скобка k правая круглая скобка .$

Построим граф: вершины  — туземцы, ребро соединяет плывших вместе. В этом графе N вершин и $N минус 1$ ребро (если некоторые пары катались вместе более одного раза, то в этом графе есть кратные ребра). Если N для данного k выбрано минимальным, то этот граф связен. Действительно, в противном случае рассмотрим компоненту связности, в которой ребер меньше, чем вершин (при этом их меньше максимум на 1 в силу связности), и выполним только рейсы из этой компоненты. Раз этот граф связен и имеет $N минус 1$ ребро, он является деревом (в частности, не имеет кратных ребер).

Докажем теперь при помощи индукции по k, что $N больше или равно 2 в степени левая круглая скобка k правая круглая скобка .$ База очевидна. Для доказательства шага выкинем из графа ребро, соответствующее первому рейсу. Граф распадется на 2 компоненты связности. В каждой знают не более одного анекдота из другой компоненты. Значит, каждый знает не менее k анекдотов из своей компоненты (считая свой). По предположению индукции, в каждой из компонент не менее $2 в степени левая круглая скобка k минус 1 правая круглая скобка$ туземцев, а всего  — не менее 2^k.

Способ II. Назовем индексом туземца число известных ему анекдотов сверх своего. Туземцев с ненулевым индексом назовем богатыми, остальных  — бедными, а капиталом туземца с индексом z назовем число 2^−m (здесь следует отметить, что так определенный капитал уменьшается с ростом количества анекдотов, известных туземцу).

Для моментов времени, в которые лодка находится на правом берегу, вычислим число S как сумму капиталов всех богатых туземцев (независимо от того, на каком берегу они находятся) минус количество L богатых туземцев на левом берегу. При первом появлении лодки на правом берегу $S=2 в степени левая круглая скобка минус 1 правая круглая скобка плюс 2 в степени левая круглая скобка минус 1 правая круглая скобка минус 0=1.$ Докажем, что S по мере переправы не уменьшается. Между последовательными попаданиями лодки на правый берег возможны 3 вида случаев: количество богатых туземцев в лодке на пути с левого берега на правый оказалось равным 0, 1 или 2.

В случае нуля богатых туземцев в лодке двое бедных по дороге на правый берег стали богатыми и увеличили S на $2 в степени левая круглая скобка минус 1 правая круглая скобка плюс 2 в степени левая круглая скобка минус 1 правая круглая скобка =1.$ Но на левый берег лодку перегонял богатый туземец, который на левом берегу и остался, увеличив L на 1. Значит, в этом случае S не изменилась.

Рассмотрим случай одного богатого туземца в лодке. Число L в этом случае не изменилось. Севший в лодку богатый знал (помимо своего) m анекдотов, его капитал был равен 2^−m. Теперь он и его спутник знают (помимо своих) по $m плюс 1$ анекдоту, и сумма их капиталов равна $2 в степени левая круглая скобка минус m минус 1 правая круглая скобка плюс 2 в степени левая круглая скобка минус m минус 1 правая круглая скобка =2 в степени левая круглая скобка минус m правая круглая скобка ,$ то есть вновь S не изменилась.

Наконец, в случае двух богатых туземцев в лодке число L уменьшается на 1, а сумма капиталов приплывших на правый берег богатых туземцев уменьшается, но, будучи изначально не более $2 в степени левая круглая скобка минус 1 правая круглая скобка плюс 2 в степени левая круглая скобка минус 1 правая круглая скобка =1,$ она уменьшается менее чем на 1. Тем самым, в итоге S увеличилась.

Итак, в конце $S больше или равно 1, L=0,$ а капитал каждого туземца не более 2^–k. Значит, туземцев не менее 2^k.

Ответ: 2^k.

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

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

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

Решение.

Представим описанную в условии сеть дорог в виде графа, вершинами которого являются города, раз вилки и перекрестки, а ребрами  — дороги. Покажем, что этот граф является деревом, то есть связным графом без циклов. Связность следует из того, что из любого города можно проехать в любой другой, а любая развилка или перекресток должны быть соединены с каким-либо городом. Допустим, что в нашем графе есть цикл. Он не содержит двух и более вершин-городов, так как в этом случае, двигаясь в противоположных направлениях по циклу, мы могли бы получить два различных пути из одного города в другой. Далее, пусть между некоторыми городами A и B существует путь, содержащий какую-то вершину цикла. Он обязательно найдется, так как иначе эта вершина не могла бы быть в нашей сети. Но тогда, добавляя к этому пути «кольцо» вдоль цикла, мы получим еще один путь между A и B. Значит, циклов в нашем графе быть не может и это действительно дерево.

По условию задачи все концевые вершины дерева  — города. Назовем эти города концевыми. Назовем также концевой город B следующим за концевым городом A, если по пути из A в B на каждой развилке выбирается самая правая дорога. Выберем какой-нибудь концевой город A₁ и измерим расстояние между ним и следующим за ним концевым городом A₂. Потом измерим расстояние между A₂ и следующим за ним концевым городом A₃ и так далее. После не более чем 100 таких измерений мы вернемся в исходный город A₁.

Покажем, что при этом каждая дорога нашей сети будет пройдена ровно два раза в противоположных направлениях. Рассмотрим произвольную дорогу. При удалении из дерева любого ребра оно распадается на две компоненты связности K₁ и K₂, причем каждая из них содержит города. Пусть изначально мы находились в K₁. Поскольку необходимо обойти все города сети, мы должны пройти по этой дороге два раза: первый раз  — когда движемся из K₁ в K₂, а второй  — когда возвращаемся обратно. Процедура обхода устроена таким образом, что мы посетим все вершины компоненты K₂ до того, как покинем ее, поэтому больше проходить по дороге из K₁ в K₂ не потребуется.

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

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

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

Тип 11 № 4938 Добавить в вариант

Четыре кротовые норы A, B, C, D последовательно соединены тремя тоннелями.

Каждую минуту крот по тоннелю перебегает в одну из соседних нор. Сколькими способами крот может добраться из норы A в C за 30 минут?

Аналоги к заданию № 4938: 4948 4998 5008 ...4948 4998 5008 5018 5040 5050 5226 Все

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

Тип 11 № 4948 Добавить в вариант

Четыре кротовые норы A, B, C, D последовательно соединены тремя тоннелями. Каждую минуту крот по тоннелю перебегает в одну из соседних нор. Сколькими способами крот может добраться из норы A в C за 28 минут?

Аналоги к заданию № 4938: 4948 4998 5008 ...4948 4998 5008 5018 5040 5050 5226 Все

Решение · Прототип задания · Помощь

Всего: 65 1–20 | 21–40 | 41–60 | 61–65

C₀	C₁	C₂	C₃	C₄	C₅	C₆	C₇	C₈	C₉	C₁₀	C₁₁	C₁₂	C₁₃	C₁₄	C₁₅
0	1	3	8	21	55	144	377	987	2584	6765	17711	46368	121393	317811	832040

C₀	C₁	C₂	C₃	C₄	C₅	C₆	C₇	C₈	C₉	C₁₀	C₁₁	C₁₂	C₁₃	C₁₄	C₁₅
0	1	3	8	21	55	144	377	987	2584	6765	17711	46368	121393	317811	832040