IMO 2020 Shortlist C3
Let n be an integer with n ě 2. On a slope of a mountain, n2 checkpoints are marked, numbered from 1 to n2 from the bott...
Category: Combinatorics
Problem
Let n be an integer with n ě 2. On a slope of a mountain, n2 checkpoints are marked, numbered from 1 to n2 from the bottom to the top. Each of two cable car companies, A and B, operates k cable cars numbered from 1 to k; each cable car provides a transfer from some checkpoint to a higher one. For each company, and for any i and j with 1 ď i ă j ď k, the starting point of car j is higher than the starting point of car i; similarly, the finishing point of car j is higher than the finishing point of car i. Say that two checkpoints are linked by some company if one can start from the lower checkpoint and reach the higher one by using one or more cars of that company (no movement on foot is allowed). Determine the smallest k for which one can guarantee that there are two checkpoints that are linked by each of the two companies. (India)