Croatian Mathematical Olympiad 2021 Problem I-2

Neka je $N$ prirodan broj i neka je $S = \{1, 2, \ldots, N\}$. Neka su $a_{i,j}$ međusobno različiti realni brojevi takvi da za sve $i, j \in S$ vrijedi: ako je $i < j$, onda je $$a_{i,k} < a_{j,k} \quad \text{i} \quad a_{k,i} < a_{k,j}, \quad \text{za sve} \quad k \in S.$$

Neka je $n$ prirodan broj takav da je $2(n-1)^2 < N$. Dokaži da postoje $n$-člani podskupovi $I, J \subset S$ takvi da vrijedi jedna od sljedeće dvije tvrdnje:

• za sve $i, k \in I$ vrijedi: ako je $i < k$, onda je $a_{i,j} < a_{k,l}$, za sve $j, l \in J$,

• za sve $j, l \in J$ vrijedi: ako je $j < l$, onda je $a_{i,j} < a_{k,l}$, za sve $i, k \in I$.