В стране 13 городов.Некоторые из них соединены дорогами. Доказать, что есть два города, из которых выходит...

Для решения задачи рассмотрим следующее: у нас есть 13 городов, и каждый город соединен с некоторыми другими городами дорогами. Нам нужно доказать, что найдутся хотя бы два города, из которых выходит одинаковое количество дорог.

Этот вопрос можно рассматривать с точки зрения теории графов. Представим города как вершины графа, а дороги как ребра графа. Тогда задача сводится к доказательству того, что в графе с 13 вершинами найдутся хотя бы две вершины одинаковой степени. Степень вершины в графе — это количество ребер, выходящих из этой вершины.

Рассмотрим возможные степени вершин в нашем графе. Поскольку каждая вершина может быть соединена с максимум 12 другими вершинами (из-за того, что всего 13 вершин), степени вершин могут быть от 0 до 12. Если бы степени всех вершин были различными, у нас было бы 13 различных значений степеней (от 0 до 12).

Однако, если бы у одного города была степень 0 (город не соединен ни с каким другим городом), то у нас оставалось бы 12 городов, и один из этих городов должен был бы иметь степень 12 (соединен со всеми остальными), что невозможно, так как этот город не может быть соединен с городом со степенью 0.

Следовательно, если кто-то из городов имеет степень 12, то ни один город не может иметь степень 0. Аналогично, если хотя бы один город имеет степень 0, то ни один город не может иметь степень 12.

Теперь рассмотрим возможные степени вершин от 1 до 11. Если бы степени всех 13 городов были различными, нам нужно было бы 13 различных значений степеней, но у нас только 11 возможных значений (от 1 до 11). Это приводит к противоречию, так как мы не можем иметь 13 различных степеней при 11 возможных значениях.

Таким образом, по принципу Дирихле, в графе с 13 вершинами обязательно найдутся хотя бы две вершины с одинаковой степенью. Это означает, что в нашей задаче всегда найдутся два города, из которых выходит одинаковое количество дорог.

Для доказательства этого утверждения воспользуемся принципом Дирихле. Предположим, что каждый город соединен с другим количеством дорог. Если у каждого города количество выходящих из него дорог будет отличаться, то сумма всех этих количеств будет нечетным числом, так как сумма нечетного числа чисел нечетна. Однако общее количество дорог, выходящих из всех городов, равно удвоенному числу дорог, так как каждая дорога соединяет два города. Это означает, что общее количество дорог должно быть четным числом.

Из этого следует, что наше предположение неверно, и существуют как минимум два города, из которых выходит поровну дорог.