Integers $1$ to $n^2$ in $n\times n$ table, largest possible among the smallest ratios of numbers in each row or column

Hope you're doing alright.

I'm self-studying combinatorics. I took an online course on the subject and meanwhile, I asked one of my friends for his notes so I can get familiar with the problems his professor gave him. There is this question I can not figure where even to start with!

The question is:

We have an $n\times n$ table and we randomly put numbers between $1$ to $n^2$ in them. For every two numbers that are in same row "or" column, we calculate the ratio of the bigger number to the smaller one. If C is the smallest fraction between these $n^2 (n-1)$ fractions, what is the largest possible value of C ?

I don't even fully understand the question. I tried it for $n=3$, made a random table $$1, 6 ,3$$ $$8, 4 ,9$$ $$7, 2 ,5$$ and the smallest fraction between 18 fractions is $\frac{9}{8}=1.125$ in this case. I don't know how can I figure this out when it's totally random!

Can someone please take the time and help me go through with this? Thanks in advance.

Solution 1:

Our strategy should be to avoid placing consecutive numbers in same row or column.

Among $1,2,3,\ldots, n^2-2, n^2-1, n^2$, consecutive pairs from the right end give smallest ratios. So let us begin by putting $n$ numbers from the end on the main diagonal.

\begin{array}{|c|c|c|c|c|c|} \hline \; n^2 \; & & & & & \color{red}{\unicode{x2718}} \\ \hline \color{green}{\unicode{x2714}} & n^2-1 & & & & \\ & \color{blue}{?} & {n^2-2}& & & \hline \\ & & \color{blue}{?} & \; \ddots \; & & \hline \\ \hline & & & \; \ddots \; & n^2-(n-2)& \\ \hline & & & & \color{blue}{?} & n^2-(n-1) \\ \hline \end{array}

Our next number is $n^2-n$. Where on the remaining cells should be the best spot to place it?

On the diagonal just below the main diagonal, $n^2-n$ can be placed in cell adjacent to $n^2, n^2-1$, which is the only cell (upto symmetry) not in the same row or column of other numbers which are closer to $n^2-n$ in magnitude.

Thus the unavoidable, and hence, I claim, the maximum possible ratio is $$\frac{n^2-1}{n^2-n}=\frac{n+1}{n}$$

Here is the proof that there is an arrangement of remaining numbers with all other ratios larger than $\frac{n+1}{n}$.

We keep filling the consecutive numbers from the end along the next diagonals. It can be shown that in each row and column, numbers are in arithmetic progression. If common difference is $d$, then following is true for $a>b>0$, $$\frac{a}{b} < \frac{a-d}{b-d}$$

This means shortest ratio is achieved by numbers on the two diagonals shown above. The above inequality also ensures that $\frac{n+1}{n}$ is smallest ratio among the $n$ ratios due to the two diagonals. Hence our proof is complete.