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