В подземной стране есть столица и еще 99 городов. Некоторые города (в том числе и столица) соединены подземными ходами с односторонним движением. Количество дорог, которые выходят из всех городов, кроме столицы, равно 15, а которые входят — 16. Докажи, что в столицу нельзя приехать ни из одного города.

Для решения этой задачи воспользуемся методом подсчёта общего количества дорог. В графе (где города — это вершины, а дороги — рёбра) сумма входящих степеней всех вершин равна сумме исходящих степеней и равна общему количеству дорог $n$. 1. Пусть $x$ — количество дорог в стране. Из условия известно, что из каждого города (включая столицу) выходит не более 15 дорог. Всего городов 100, значит, общее количество дорог $x \le 100 \cdot 15 = 1500$. 2. С другой стороны, в каждый город, кроме столицы, входит ровно 16 дорог. Городов без столицы 99. Значит, в них суммарно входит $99 \cdot 16$ дорог. Пусть в столицу входит $k$ дорог. 3. Тогда общее количество дорог $x = 99 \cdot 16 + k = 1584 + k$. 4. Мы получили противоречие: с одной стороны $x \le 1500$, а с другой $x \ge 1584$ (так как $k \ge 0$). Заполним пропуски согласно логике задачи на изображении: Доказательство: пусть $n$ — это количество дорог. Выразим общее количество дорог, входящих в города: $16 \cdot 99 + k$ (где $k$ — количество дорог, входящих в столицу). Общее количество выходящих дорог не больше: $15 \cdot 100 = 1500$. Приравняем количество входящих и выходящих дорог: $16 \cdot 99 + k \le 1500$; $1584 + k \le 1500$; $1584 - 1500 + k \le 0$; $84 + k \le 0$. А это и означает, что к столице нельзя приехать ни из одного города, так как даже при $k=0$ условие $1584 \le 1500$ ложно. Допущение о том, что такая система дорог возможна, неверно. **Ответ:** Доказано методом от противного через подсчёт количества дорог.