Question

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

Answer 1

Ответ:

7 дорог

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

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

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

28/2=14

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

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

Answer 2

Ответ:

7

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

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

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

28/2=14

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

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

Answer 3

Для решения этой задачи используется принцип Дирихле, также известный как лемма о ящиках и шарах. Этот принцип утверждает следующее: если n объектов распределены по k ящикам, и n > k, то как минимум один из ящиков содержит хотя бы два объекта.

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

Из условия известно, что каждый город соединен хотя бы одной дорогой, поэтому k (количество городов, в которых есть концы дорог) будет равно как минимум 21 (количество дорог). Таким образом, наибольшее значение n, при котором k < n, равно 21.

Таким образом, мы можем утверждать, что обязательно найдутся 21 дорога, концы которых находятся в 2n = 2 * 21 = 42 различных городах.