Proof concerning Latin squares

Question

I'm asked to solve this problem :

Let $R$ be an $r\times c$ partial Latin rectangle using the numbers $[n]= \{1,2,...,n\}$. Suppose that $r < n$ and $c < n$, and let $N(i)$ be the number of times the number $i$ appears in $R$. Prove that $R$ can be completed into an $n\times n$ Latin square if and only if, for all $i$ from $1$ to $n$ we have $N(i)\geq r+c-n$.

I tried to see why it was true through examples, and it's quite intuitive, but I don't know how to prove it formally.

Can anyone give me a small help, I'm not asking here for a complete answer, just a hint.

Thanks in advance

Answer 1

Two hints (but there are several possible proof strategies):

• how many columns and how many rows do you have left so that N(i) = n when the latin square is completed ?

• N(i) = max( number of times i appears in columns, number of times i appears in rows)