Международная олимпиада 2020, Санкт-Петербург, Россия, 2020 год


Дано целое число $n > 1.$ На горном склоне расположено $n^2$ фуникулёрных станций на разных высотах. Каждая из двух фуникулёрных компаний $A$ и $B$ владеет $k$ подъёмниками. Каждый подъёмник осуществляет регулярный беспересадочный трансфер с одной из станций на другую, более высоко расположенную станцию. $k$ трансферов компании $A$ начинаются на $k$ различных станциях; также они заканчиваются на $k$ различных станциях; при этом трансфер, который начинается выше, и заканчивается выше. Те же условия выполнены для компании $B$. Будем говорить, что две станции связаны фуникулёрной компанией, если можно добраться из нижней станции в верхнюю, используя один или несколько трансферов данной компании (другие перемещения между станциями запрещены). Найдите наименьшее $k,$ при котором заведомо найдутся две станции, связанные обеими компаниями.
посмотреть в олимпиаде

Комментарий/решение: