Давайте разберем каждую задачу по порядку, подробно объясняя решение и логику.
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
]
Это нецелое число.
Вывод:
Невозможно, потому что число городов нецелое, а это невозможно.
Итог:
- Нет, невозможно соединить 15 компьютеров так, чтобы каждый имел 5 соединений.
- Да, возможно, из сети городов есть путь из столицы в Дальний.
- Нет, невозможно, чтобы сумма дружб была нечетной.
- Нет, не может — сумма степеней нечетная.
- Нет, столько дорог при одинаковой степени — невозможно, потому что число городов должно быть целым.
Если нужна помощь по какой-либо задаче подробнее — скажите!
