Let's take any natural number $n>0$. Let $k$ be the smallest natural number greater than $n/2.$ Now let $A$ be any $n$-element set, and let $M$ be a $k\times k$ matrix over $A$. Suppose that for any row $r$ of $M$, the elements in $r$ are pairwise different. Suppose the same about every column $c$ of $M$. I would like to know whether this implies that every element of $A$ can be found in the matrix $M$.
This is something that I've extracted from a different problem I'm thinking about. It looks true to me, but I'm not good at combinatorics, and I can't think of a way to prove this.
I will welcome both hints and full solutions.
Thank you very much.