Задано ціле число $n > 1$. На горном схилі на попарно різних висотах розташовано $n^2$ станцій фунікулеру. Кожна з двох компаній $A$ та $B$ володіє $k$ підйомниками. Кожний підйомник виконує регулярний трансфер (без пересадок) з однієї зі станцій на іншу, що розташована вище. $k$ трансферів компані $A$ починаються на $k$ різних станціях; також вони закінчуються на $k$ різних станціях; при цьому трансфер, який починається вище, закінчується теж вище. Ті саме умови виконано для компанії B. Будем казати, що дві станції пов’язані компанією, якщо можна дістатися з нижньої станції до верхньої, використовуючи один чи декілька трансферів цієї компанії (інші пересування між станціями заборонено). Знайдіть найменше $k$, при якому гарантовано знайдуться дві станції, що пов’язані обома компаніями.
| Source | International Mathematical Olympiad |
|---|---|
| Year | 2020 |
| Number | 4 |
| Difficulty | 10.0 |
| Themes |