75th NMO Selection Tests

For $n=2$, no matter how Nicuşor chooses $a_1$ and $a_2$, on the third row we will have two equal values. For $n=3$, suppose without loss of generality that $a_3=3$. Then, in the third column, we have only values equal to $3$. Since the set $(1,2)$ admits only two permutations, among the first three rows there will be two identical ones, so these rows coincide and we cannot have any $a_i=1$.

Next, we show that for $n\ge 4$, there exists a completion that works. If $n=4$ and we take $a_1=1,a_2=2,a_3=3,a_4=4$, the following construction satisfies the

1	2	3	4
2	1	3	4
2	1	3	4
3	2	1	4
1	2	3	4

Construction 1 (induction): We will prove by induction on $n\ge 4$ that there exists a valid construction in which $a_i=i$ for every $i\in \{1,2,\dots ,n\}$ and the last row is exactly $1,2,\dots ,n$. The case $n=4$ is illustrated above. Suppose there exists a valid table $T_n$ of size $(n+1)\times n$ for $n\ge 4$, for which the chosen permutation by Nicuşor is $a_1,a_2,\dots ,a_n$ with $a_i=i$ for every $i=1,2,\dots ,n$. We construct a table $T_{n+1}$ of size $(n+2)\times (n+1)$, valid for $n+1$, as follows: we add a column at the end of $T_n$ and a new row between the last and the penultimate rows of $T_n$. We fill all the cells of the newly added last column with the value $n+1$, and the first $n$ values of the newly added row with $2,3,\dots ,n,1$ (or any permutation that preserves the values for $a_1,a_2,\dots ,a_n$). It is easy to verify that the newly constructed table is valid.

Construction 2 (direct): For $n\ge 4$, consider $a_i=i$ for every $i=1,2,3,4,\dots ,n$ and the following construction:

1	2	3	4	5	6	7	...	n
2	1	3	4	5	6	7	...	n
2	1	3	4	5	6	7	...	n
3	2	1	4	5	6	7	...	n
2	3	4	1	5	6	7	...	n
2	3	4	5	1	6	7	...	n
2	3	4	5	6	1	7	...	n
...
1	2	3	4	5	6	7	...	n

It is easy to verify that the newly constructed table is valid.