In several cells of a square grid there live hedgehogs. Every hedgehog multiplies the number of hedgehogs in its row by the number of hedgehogs in its column. Is it possible that all the hedgehogs get distinct numbers?
Problem
Source: Kyiv mathematical festival 2021
Tags: Kyiv mathematical festival, combinatorics
TheStrayCat
24.06.2021 22:38
If the definition of "several" includes one then yes - just take one hedgehog in a random cell.
building
26.06.2021 00:43
Claim: If there is more than one hedgehog, it is impossible for them all to get distinct numbers.
Proof: If no two hedgehogs share a row or column, then clearly every hedgehog gets the number $1\cdot1 = 1$, which is no good. Thus we may assume there is some row or column with at least $2$ hedgehogs. Consider a row or column (assume wlog it is a row) containing the maximal number of hedgehogs, say, $n$ hedgehogs where $n \geq 2$. The $n$ columns containing those hedgehogs must all have distinct numbers of hedgehogs, but they each have at most $n$ hedgehogs. Hence, the columns have $1, 2, \dots, n$ hedgehogs in some order. In particular, the hedgehog in the $1$-hedgehog column gets the number $n\cdot1 = n$. Applying the same logic to the column with $n$ hedgehogs, we find that the $n$ rows containing these hedgehogs have $1, 2, \dots, n$ hedgehogs in some order, so the hedgehog in the $1$-hedgehog row gets the number $1\cdot n = n$. Thus, there are two distinct hedgehogs that both get the number $n$. (Note that they are necessarily distinct because $n \neq 1$.)