Question

На континенте 28 городов и 21 дорога, причём из каждого города выходит хотя бы одна дорога. При каком наибольшем n можно утверждать, что обязательно найдутся n дорог, концы которых находятся в 2n различных городах?

Answer 1

Ответ:

7 дорог

Пошаговое объяснение:

21 дорога и 28 городов.

1) соединим хотя бы по одному городу с другим

28/2=14

2) 14 дорог уже соединяют по 1 городу с другим.

осталось еще 21-14=7 дорог

Answer 2

Для определения наибольшего значения n, при котором обязательно найдутся n дорог, концы которых находятся в 2n различных городах, мы можем использовать принцип Дирихле, также известный как лемма о ящиках и мячах.

В данной ситуации, "ящиками" могут быть города, а "мячами" - дороги, соединяющие эти города. Нам нужно найти наибольшее n так, чтобы было гарантировано, что в 2n различных городах найдутся n дорог.

Известно, что у нас есть 28 городов и 21 дорога. Давайте предположим, что для каждой пары городов имеется не более одной дороги, и мы хотим найти наибольшее n.

Если каждая пара городов соединена дорогой, то у нас есть C(28, 2) способов выбрать 2 города из 28, что равно 378 способам. То есть у нас есть 378 пар городов, которые соединены дорогами.

Теперь мы можем выбрать n дорог из 21. Это можно сделать C(21, n) способами.

Для того чтобы было гарантировано, что найдутся n дорог с концами в 2n различных городах, нужно, чтобы C(21, n) было больше или равно 378. То есть:

C(21, n) >= 378

Теперь мы можем начать вычисления для нахождения наибольшего n. Мы можем попробовать разные значения n, начиная с 1, и искать первое n, при котором выполняется неравенство.

1. C(21, 1) = 21
2. C(21, 2) = 210
3. C(21, 3) = 1330

Таким образом, наименьшее n, при котором C(21, n) >= 378, это n = 3. Это означает, что обязательно найдутся 3 дороги, концы которых находятся в 2 * 3 = 6 различных городах.