№1. В стране Семерка 15 городов, каждый из городов соединен дорогами не менее, чем с семью другими. Докажите, что из каждого города модно добраться в любой другой. №2. В Тридевятом царстве только один вид транспорта ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний одна, а из всех остальных городов,- по 20. Докажите, что из столицы можно долететь в город Дальний. №3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

Question

Вопрос:

№1. В стране Семерка 15 городов, каждый из городов соединен дорогами не менее, чем с семью другими. Докажите, что из каждого города модно добраться в любой другой. №2. В Тридевятом царстве только один вид транспорта ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний одна, а из всех остальных городов,- по 20. Докажите, что из столицы можно долететь в город Дальний. №3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

Ответ:

ФИО:Телефон:Емаил:Полное описание сути нарушения прав (почему распространение данной информации запрещено Правообладателем):

Accepted Answer

Ответ: 1. Да, из каждого города можно добраться в любой другой. 2. Да, из столицы можно долететь в город Дальний. 3. Нет, невозможно соединить 15 телефонов так, чтобы каждый был соединен ровно с пятью другими.

Краткое пояснение: В задачах используются понятия графов и их свойств, в первой и второй нужно доказать связность, а в третьей - невозможность существования графа с заданными условиями.

№1

В стране Семерка 15 городов, и каждый соединен дорогами не менее чем с семью другими. Нужно доказать, что из любого города можно добраться в любой другой.

Представим города как вершины графа, а дороги между ними как ребра.
Если каждый город соединен как минимум с 7 другими, то не может быть изолированных частей графа.
Логика такая: даже если мы попробуем разделить города на две группы, в каждой группе должно быть достаточно связей, чтобы можно было добраться из любого города в другой.

Таким образом, из каждого города можно добраться в любой другой.

№2

В Тридевятом царстве есть только ковры-самолеты. Из столицы выходит 21 ковролиния, из города Дальний - одна, а из остальных городов - по 20. Доказать, что из столицы можно долететь в город Дальний.

Представим города как вершины графа, а ковролинии как ребра.
Столица имеет степень 21, город Дальний - степень 1, остальные города - степень 20.
Предположим, что из столицы нельзя долететь в Дальний. Тогда есть группа городов, не соединенных со столицей и содержащих Дальний.
Но это невозможно, так как каждый город в этой группе должен быть соединен с 20 другими городами внутри группы, что требует большого количества связей.

Таким образом, из столицы можно долететь в город Дальний.

№3

В городе Маленьком 15 телефонов. Возможно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

Представим телефоны как вершины графа, а провода как ребра.
Если каждый телефон соединен с пятью другими, то степень каждой вершины равна 5.
Сумма степеней всех вершин должна быть четной, так как каждое ребро считается дважды (для каждой из двух вершин, которые оно соединяет).
В данном случае сумма степеней равна 15 * 5 = 75, что является нечетным числом.

Следовательно, невозможно соединить 15 телефонов так, чтобы каждый был соединен ровно с пятью другими.

Ответ: 1. Да, из каждого города можно добраться в любой другой. 2. Да, из столицы можно долететь в город Дальний. 3. Нет, невозможно соединить 15 телефонов так, чтобы каждый был соединен ровно с пятью другими.

Ты сегодня просто Цифровой Архитектор! Achievement unlocked: Домашка закрыта. Минус 15 минут нудной домашки. Потрать их на катку или новый рилс. Не будь NPC — кинь ссылку бро, который всё еще тупит над этой задачей