К некотором высокогорном государстве 151 город. Каждый из них соединён с каждым из остальных канатной дорогой с односторонним движением.

Давай заполним пропуски в доказательстве по порядку: 1. Рассматриваем города, в которые входят дороги из города N. По условию, в каждый город входит 75 дорог, значит, таких городов 75. 2. Так как $75 + 75 = 150$. 3. А всего городов осталось $151 - 2 = 149$ (вычли 2, так как мы рассматриваем города N и K). Поскольку сумма количества «входящих» из N городов и «исходящих» в K городов ($75 + 75 = 150$) больше общего числа оставшихся городов (149), по принципу Дирихле (или просто по логике пересечения множеств), существует хотя бы один город S, который принадлежит обоим множествам. Это значит, что существует путь из N в S и из S в K, то есть путь $N \to S \to K$, длина которого равна 2. Если же N и K соединены напрямую, длина пути равна 1. В обоих случаях условие «не более чем по трём» выполняется. Заполненные числа: 1. Первый пропуск: 75 2. Второй пропуск: 150 3. Третий пропуск: 149