Question

В одной стране количество городов равно 87, каждый из них соединён дорогами не менее чем с 43 другими. Можно ли из каждого города добраться до другого?
 Решение
1. Рассмотрим любые два города и предположим, что между ними
2.  По условию каждый из этих двух городов соединён не менее чем с 43 другими, и при этом все города различны (если есть одинаковые города, то есть и путь, соединяющий эти города).
3. Посчитаем общее количество городов.
Получили противоречие, так как по условию городов 87.

Answer 1

Дано:
Количество городов в стране = 87
Каждый город соединён дорогами не менее чем с 43 другими

Найти:
Можно ли из каждого города добраться до другого?

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

Если рассмотреть пару городов, то существует не менее 43 + 1 = 44 различных города, к которым есть пути из каждого из этих двух городов.

Таким образом, общее количество различных городов должно быть не менее 44, что противоречит количеству городов в стране (87).

Ответ:
Из каждого города в стране нельзя добраться до каждого другого города.