IMO 2020 — Toàn bộ Shortlist Câu hỏi 11

Đặt $n$ là một số nguyên với $n \geqslant 2$. Trên sườn núi, các điểm kiểm tra $n^{2}$ được đánh dấu, đánh số từ 1 đến $n^{2}$ từ dưới lên trên. Mỗi công ty trong số hai công ty cáp treo $A$ và $B$ đều vận hành các cáp treo $k$ được đánh số từ 1 đến $k$; mỗi cáp treo cung cấp dịch vụ chuyển từ một số trạm kiểm soát đến trạm cao hơn. Đối với mỗi công ty và đối với bất kỳ $i$ và $j$ nào có $1 \leqslant i\lt j \leqslant k$, điểm xuất phát của cabin cáp treo $j$ cao hơn điểm xuất phát của cabin cáp treo $i$; Tương tự, điểm về đích của xe $j$ cũng cao hơn điểm về đích của xe $i$. Giả sử hai trạm kiểm soát được liên kết bởi một công ty nào đó nếu một trạm có thể xuất phát từ trạm kiểm soát thấp hơn và đến trạm kiểm soát cao hơn bằng cách sử dụng một hoặc nhiều cabin cáp treo của công ty đó (không được phép đi bộ).

Xác định $k$ nhỏ nhất mà người ta có thể đảm bảo rằng có hai điểm kiểm tra được liên kết bởi mỗi công ty trong số hai công ty.