1.В классе 15 компьютеров. Можно ли их соединить друг с другом так, чтобы каждый компьютер был соединен ровно с пятью другими? 2.В Тридевятом царстве лишь один вид транспорта…

Давайте разберем каждую задачу по порядку, подробно объясняя решение и логику.

---

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

Задача: Есть 15 компьютеров, нужно соединить их так, чтобы каждый компьютер имел ровно 5 соединений.

Решение:

Это задача о таком виде графа — ровном графе (k-regular graph), где у каждого вершины (компьютера) степень равна 5.

Обозначим:

• число вершин \( n = 15 \)
• степень каждой вершины \( k = 5 \)

Известное свойство графов: сумма степеней всех вершин равна удвоенному числу рёбер:

\[ \sum_{в всех вершинах} \deg(v) = 2E \]

Значит:

\[ n \times k = 2E \quad \Rightarrow \quad 15 \times 5 = 2E \quad \Rightarrow \quad 75 = 2E \]

Отсюда:

\[ E = \frac{75}{2} = 37.5 \]

Но количество рёбер \( E \) должно быть целым числом! Получили дробь — это невозможно.

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

---

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

Задача: Есть сеть городов и линий между ними. Можно ли добраться из столицы в Дальний?

Обозначения:

• из столицы выходит 21 линии
• из города Дальний — 1 линия
• из остальных городов — по 20 линий

Анализ:

• Это задача о достижимости в графе, где вершины — города, рёбра — ковролиния.

• В таком случае, чтобы добраться из столицы в Дальний, необходимо существование пути, соединяющего эти города.

• Достаточно проверить, есть ли путь.

Поскольку:

• У столицы есть 21 линия — она связана с некоторым количеством городов (суммарная степень вершины равна 21).
• Только один город — Дальний — связан только одной линией.

Важно:

• В графе, чтобы доехать, есть линия из столицы в город — это очевидно.
• Из города Дальний есть одна линия — значит, он подключен к какому-то городу, к которому есть связь из столицы или из другого города.

Вывод: — да, из столицы в Дальний добраться можно, потому что:

• В сети есть путь: из столицы по линиям к некоторым городам, и, наконец, из одного из них — в Дальний.

• Если город Дальний — единственный город с одной линией, скорее всего, он подключен к другому городу или к столицы.

Итог: Можно сделать логический вывод — да, долететь можно, если сеть связна, что, судя по описанию, скорее всего так и есть.

---

3. В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга, 11 — по 4 друга, а 10 — по 5 друзей? Ответ объясните.

Задача: Можно ли распределить число друзей так, чтобы его соответствовали этим группам?

Обозначим:

• Группа 1: 9 человек, у каждого — 3 друга
• Группа 2: 11 человек, у каждого — 4 друга
• Группа 3: 10 человек, у каждого — 5 друзей

Проверим сумму общего количества "дружб" (обратите внимание, что дружба — двусторонняя связь). В графе:

\[ \sum_{все люди} \deg(v) = 2 \times \text{число рёбер} \]

Посчитаем сумму степеней:

\[ 9 \times 3 + 11 \times 4 + 10 \times 5 = 27 + 44 + 50 = 121 \]

Тогда число рёбер:

\[ E = \frac{121}{2} = 60.5 \]

Но число рёбер должно быть целым — получили 60.5, что невозможно.

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

---

4. У короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального барона количество соседних баронов — 1, 5 или 9?

Задача:
В графе из 19 вершин (баронов), у каждой вершины степень — 1, 5 или 9. Возможно ли такое?

Решение:

Обозначим:

• Пусть \( x_1 \) — число баронов со степенью 1
• \( x_5 \) — с степенью 5
• \( x_9 \) — с степенью 9

Тогда:

\[ x_1 + x_5 + x_9 = 19 \]

Общее число "дружб" (других соседних баронов):

\[ \sum_{i=1}^{19} \deg(v_i) = x_1 \times 1 + x_5 \times 5 + x_9 \times 9 \]

Обозначим сумму:

\[ S = x_1 + 5x_5 + 9x_9 \]

Число рёбер равно:

\[ E = \frac{S}{2} \]

Так как количество рёбер должно быть целым, \( S \) — чётное число.

Посмотрим, возможна ли эта сумма:

• Важно, чтобы \( S \) было четным.

Обозначим:

\[ S = x_1 + 5x_5 + 9x_9 \]

Модули по 2:

• \( x_1 \equiv x_1 \pmod{2} \)
• \( 5x_5 \equiv x_5 \pmod{2} \)
• \( 9x_9 \equiv x_9 \pmod{2} \)

Значит:

\[ S \equiv x_1 + x_5 + x_9 \pmod{2} \]

Но мы знаем, что:

\[ x_1 + x_5 + x_9 = 19 \]

И 19 — нечетное число, следовательно:

\[ S \equiv 19 \equiv 1 \pmod{2} \]

То есть, сумма \( S \) нечетная. А это противоречит тому, что мы хотим, чтобы рёбер было целым, то есть \( S \) должно быть четным — не получится.

Ответ:
Нет, у каждого барона не может быть ровно 1, 5 или 9 соседних баронов, потому что сумма степеней нечетна, а для полного графа с четным числом рёбер сумма степеней должна быть четной.

---

5. Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?

Задача:

• Из каждого города выходит 3 дороги.
• Итого ровно 100 дорог.

Обозначим:

• Число городов — \( n \)
• Степень каждого города — 3 ⇒ граф — 3-регулярный граф.

Общая сумма степеней:

\[ n \times 3 = 2 \times 100 \]

Следовательно:

\[ 3n = 200 \] \[ n = \frac{200}{3} \approx 66.66 \]

Это нецелое число.

Вывод:
Невозможно, потому что число городов нецелое, а это невозможно.

---

Итог:

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

Если нужна помощь по какой-либо задаче подробнее — скажите!