Открытая летняя олимпиада: хард

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

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

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

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

Решаем задачу:

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

Задача 1#126432

Во времена расцвета Долины Мира проводился Великий Совет Целителей. От каждого храма исцеления на Совет было приглашено по пять мудрейших лекарей. Однако каждый из них обучался в двух храмах, поэтому представлял на Совете оба. Мастера следовали древнему правилу: для любых двух храмов обязательно найдётся хотя бы один лекарь, который обучался в обоих — чтобы сохранить связь знаний между всеми школами. Сколько могло быть храмов в Долине Мира и сколько лекарей тогда участвовали в Совете?

“Один камень — просто камень. Но множество камней, уложенных с умом, — это мост.”

— Мастер Рино

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

Обозначим количество храмов через $a,$ а число лекарей — через $b.$ Построим двудольный граф: одна доля — храмы, другая — лекари. Соединим лекаря с храмом, если он в нём обучался.

По условию:

$1)$ От каждого храма было по $5$ лекарей: всего $5a$ связей.

$2)$ Каждый лекарь представляет два храма: всего $2b$ связей.

Значит, $5a= 2b.$

Кроме того, для каждой пары храмов должен существовать хотя бы один лекарь, обучавшийся в обоих. А таких пар $a(a-− 1). 2$ Можем оценить количество лекарей снизу:

a(a-− 1) b≥ 2

Подставим $5a b= 2$ в неравенство:

5a a(a− 1) 2-≥ ---2--| ⋅2

5a≥ a(a − 1)| ÷ a⁄= 0

5≥ a− 1| + 1

a≤ 6

Кроме того, из равенства $5a= 2b$ следует, что $a$ — чётное. Остаются $a= 2,$ $4,$ $6.$

Возможные случаи:

$1)$ $a =2 =⇒ b= 5;$

Пример:


№ лекаря	Храмы

$1$	$A,$ $B$

$2$	$A,$ $B$

$3$	$A,$ $B$

$4$	$A,$ $B$

$5$	$A,$ $B$

$2)$ $a =4 =⇒ b= 10;$

Пример:


№ лекаря	Храмы

$1$	$A,$ $B$

$2$	$A,$ $C$

$3$	$A,$ $D$

$4$	$B,$ $C$

$5$	$B,$ $D$

$6$	$C,$ $D$

$7$	$A,$ $B$

$8$	$C,$ $D$

$9$	$A,$ $C$

$10$	$B,$ $D$

$3)$ $a =6 =⇒ b= 15.$

Пример:


№ лекаря	Храмы

$1$	$A,$ $B$

$2$	$A,$ $C$

$3$	$A,$ $D$

$4$	$A,$ $E$

$5$	$A,$ $F$

$6$	$B,$ $C$

$7$	$B,$ $D$

$8$	$B,$ $E$

$9$	$B,$ $F$

$10$	$C,$ $D$

$11$	$C,$ $E$

$12$	$C,$ $F$

$13$	$D,$ $E$

$14$	$D,$ $F$

$15$	$E,$ $F$

Ответ: 2 храма и 5 лекарей, 4 храма и 10 лекарей или 6 храмов и 15 лекарей

Нужна консультация? Задайте нам вопрос в чате.

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

Открытая летняя олимпиада: хард

Специальные программы

Программалояльности v2.0

Крути рулеткуи выигрывай призы!

Бесплатное онлайн-обучение

Налоговые вычеты

Специальное предложениедля учителей

Вернём деньги за курсза твою сотку на ЕГЭ

Программалояльности v2.0

Крути рулеткуи выигрывай призы!

Бесплатное онлайн-обучение

Налоговые вычеты

Специальное предложениедля учителей

Вернём деньги за курсза твою сотку на ЕГЭ

Программа
лояльности v2.0

Крути рулетку
и выигрывай призы!

Специальное предложение
для учителей

Вернём деньги за курс
за твою сотку на ЕГЭ

Программа
лояльности v2.0

Крути рулетку
и выигрывай призы!

Специальное предложение
для учителей

Вернём деньги за курс
за твою сотку на ЕГЭ