В стране 800 городов и нет дорог. Два наследника престола готовятся разделить её на две равные части (по 400 городов). Король, перед тем как сдать дела, хочет всё же провести несколько дорог, но так, чтобы при любом возможном разделе наследникам досталось поровну дорог (наследнику достаётся дорога, если ему достались оба конца этой дороги). Сможет ли он это сделать, построив ровно 3000 дорог?
Рассмотрим 800 городов и построение 3000 дорог (ребер). Условие требует, чтобы при любом разбиении городов на два равных множества по 400 городов дорожная сеть внутри каждого множества имела одинаковое число дорог. Другими словами, если наследнику достаются ровно те дороги, у которых оба конца принадлежат его части, то при любом разбиении число таких дорог должно совпадать для обеих частей.
Шаг 1. Формализация условия разбиения
Обозначим города вершинами, а дороги – ребрами графа. Пусть в любом разбиении на два равных подмножества (назовём их A и B) число ребер, це...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
