Задача про города и два министерства
Условие
В государстве 22 города располагаются на территориях областей так, что любые два города из одной области соединены дорогой и никакие два города из разных областей дорогой не соединены. Оказалось, что ответственность за состояние дорог можно распределить между двумя региональными министерствами следующим образом: не найдётся таких трёх городов A, B, C из одной области, чтобы дороги AB, BC и CA обслуживались бы одним министерством. Какое наибольшее число дорог может быть в этом государстве?
Попытки закончились
Попытки закончились
Если не получается
Как начисляется опыт
- Разбор условия — +10
- Мини-задача: сам — +20, пропуск — 0
- Верный ответ — +30
- На ответ — 3 попытки
- В мини-задаче — 3 попытки
- «Проверь себя» — ★ и +30 за задачу
Дороги одной области
В области 5 городов, и любые два из них соединены дорогой. Сколько всего дорог в этой области?
Пятиугольник и звёздочка
В области 5 городов. Дороги между соседями по кругу покрасили в синий, остальные дороги — в оранжевый. Сколько получилось треугольников, у которых все три стороны одного цвета?
Пять дорог из одного города
Из города выходят 5 дорог, каждая синяя или оранжевая. Как их ни раскрась, дорог какого-то одного цвета всегда будет не меньше, чем … Впиши это число.
Самая большая область
Какое наибольшее число городов может быть в одной области, чтобы её дороги ещё можно было раскрасить без треугольника одного цвета?
Переселяем город
В одной области 4 города, в другой 3. Один город переселили из меньшей области в большую. Сколько теперь дорог в этих двух областях вместе?
Сколько дорог всего
Какое наибольшее число дорог может быть в государстве из 22 городов?
Сначала попробуй решить сам
1
Шаг 1 · разбираем условие
Что дано и что нужно найти
1:40
Прочитаем условие по кусочкам и переведём каждый на простой язык. Здесь мы ещё ничего не решаем — только разбираемся, что к чему.
-
«В государстве 22 города располагаются на территориях областей…»
Государство поделено на области, в каждой области свои города. Всего городов 22. Сколько областей и по сколько в них городов — в условии не сказано.
-
«…любые два города из одной области соединены дорогой и никакие два города из разных областей дорогой не соединены»
Внутри области каждый город соединён дорогой с каждым. А между разными областями дорог нет совсем.
Пример: 22 города в 7 областях (4, 4, 4, 3, 3, 2 и 2 города). Внутри каждой области проведены все дороги, между областями — ни одной.
-
«…ответственность за состояние дорог можно распределить между двумя региональными министерствами…»
Каждую дорогу отдают одному из двух министерств — как именно, выбираем мы сами. Дороги Первого министерства покрасим синим, Второго — оранжевым. Каждая дорога получит ровно один цвет.
-
«…не найдётся таких трёх городов A, B, C из одной области, чтобы дороги AB, BC и CA обслуживались бы одним министерством»
Три города области соединены тремя дорогами — получается треугольник. Нельзя, чтобы все три его стороны были одного цвета. Хотя бы одна сторона должна быть другого цвета. Короче: треугольников одного цвета быть не должно.
Слева и в середине — треугольники одного цвета, так нельзя. Справа цвета разные — так можно.
-
«Какое наибольшее число дорог может быть в этом государстве?»
Разложить 22 города по областям можно по-разному. Нам годятся только такие раскладки, где дороги получится раскрасить без треугольников одного цвета. Среди них нужно найти ту, где дорог больше всего, и сосчитать эти дороги.
Задача: найти, сколько дорог может быть самое большее, если дороги можно раскрасить в два цвета без треугольника одного цвета.
Сначала реши основную задачу
3 задачи без подсказок
Те же города и министерства, другие числа.