Задание №163611: Дроби
Задача 6. В совет входит n ⩾ 5 эльфов, каждый из которых доверяет одному или нескольким другим эльфам (доверие необязательно взаимно). Они хотят, чтобы один из эльфов взял Кольцо Всевластья, а затем текущий владелец Кольца передавал его одному из тех, кому доверяет. Известно, что так от любого эльфа Кольцо может перейти (необязательно напрямую) к любому другому. Эльфы хотят действовать так, чтобы в результате k передач Кольца оно хотя бы раз побывало у каждого эльфа. При каком наименьшем k (для данного n) у них обязательно получится это сделать (вне зависимости от того, кто кому доверяет)? XXIII устная городская олимпиада по геометрии для 8–11 классов состоится 12 апреля. Подробности — на странице olympiads.mccme.ru/ustn/ Задачи, решения, информация о закрытии LXXXIX Московской математической олимпиады — на сайте mmo.mccme.ru
Что проверяет это задание
Задание относится к теме «Дроби» и рассчитано на уровень 8 класса. Для решения понадобятся:
- анализ условия
- выбор формулы
- проверка вычислений
Источник: Московская олимпиада школьников — официальный архив
Качество материала
Показываем, из чего состоит страница и можно ли проверить материал по первоисточнику.
Последняя проверка решения:
Происхождение задания
- Банк заданий
- Московская олимпиада школьников — официальный архив
- Организатор
- Редакция «Я сам решу»
- Материалы
- 1 файл
Связанные понятия
План самостоятельного решения
- Перепишите известные данные и отдельно сформулируйте, что требуется найти или доказать.
- Свяжите условие с темой «Дроби» и выберите подходящее правило, формулу или способ рассуждения.
- Запишите промежуточные шаги: это помогает заметить потерянный знак, случай или логический переход.
- Сверьте результат со всеми ограничениями условия и только затем откройте подробный разбор.
Ориентировочное время: 15 минут.
Закрепить тему
После разбора попробуйте решить ещё десять заданий по предмету «Математика». Вариант формируется заново, а ответы можно сразу проверить.
Решение по шагам
6. В совет входит n ⩾ 5 эльфов, каждый из которых доверяет одному или нескольким другим
эльфам (доверие необязательно взаимно). Они хотят, чтобы один из эльфов взял Кольцо
Всевластья, а затем текущий владелец Кольца передавал его одному из тех, кому доверяет.
Известно, что так от любого эльфа Кольцо может перейти (необязательно напрямую) к
любому другому. Эльфы хотят действовать так, чтобы в результате k передач Кольца оно
хотя бы раз побывало у каждого эльфа. При каком наименьшем k (для данного n) у них
обязательно получится это сделать (вне зависимости от того, кто кому доверяет)?
(М. Федотова)
Решение. Ответ: k = [n2] ([n2] — целая часть выражения n2). Оценка k ⩾ [n2]. В оцен-
4 4 4 4
ке мы должны доказать, что гарантированно быстрее передать Кольцо не получится,
для этого достаточно привести конкретный набор доверий, при котором осуществить же-
ланное не удастся быстрее. Назовем двух из эльфов Келебримбором и Галадриэлью, r
эльфов назовем промежуточными (далее мы укажем, какое надо взять r), а всех осталь-
ных эльфов назовем обычными, их будет n − r − 2. Пусть доверия устроены следующим
образом: Келебримбор доверяет всем обычным эльфам, все обычные эльфы доверяют Га-
ладриэль, Галадриэль доверяет первому промежуточному эльфу, каждый промежуточный
эльф, кроме последнего доверяет следующему промежуточному эльфу, последний проме-
жуточный эльф доверяет Келебримбору, других доверий нет. Легко видеть, что любой
эльф (необязательно напрямую) может передать Кольцо любому другому. Заметим, что
самый короткий путь от одного обычного эльфа до другого занимает r + 3 передач: от
него Кольцо может попасть только Галадриэль, затем за r+1 передач попадет Келебрим-
бору (других вариантов передачи нет), и понадобится еще хотя бы одна передача, чтобы
оно оказалось у нужного обычного эльфа. Так как Кольцо должно побывать у всех обыч-
ных эльфов, не существует искомого пути менее чем за (n − r − 3)(r + 3) передач. Взяв
r + 3 = [n+1], получим оценку на [n2].
2 4
Пример для k = [n2]. В примере мы должны доказать, что такое k действительно подходит,
Используемые формулы
Ответ: k = [n2] ([n2] — целая часть выражения n2).r + 3 = [n+1], получим оценку на [n2].Пример для k = [n2].
Самопроверка после решения
- Я использовал все данные из условия и не добавил неподтверждённых предположений.
- Каждый переход в рассуждении объяснён правилом, формулой или ранее доказанным фактом.
- Ответ соответствует вопросу, а обозначения и единицы измерения записаны однозначно.
- Я сравнил свой ход решения с разбором и понял причину каждого отличия.
Типичные ошибки
- Не проверить область допустимых значений.
- Потерять знак при переносе или раскрытии скобок.
- Не выполнить обратную подстановку.