2
$\begingroup$

Suppose I have a multiplication table mod $p$, with the $0$ row and column excluded. Suppose I wish to circle a different number from $1$ through $p-1$ in each column so that no two numbers are circled in any given row, no two numbers are circled in any given column, and no given number is circled twice in the table.

How can I prove that my wish is futile, i.e. this is not possible?

$\endgroup$
1
$\begingroup$

Let us assume $p$ is a prime, so each row and column has all the numbers $1$ through $p-1$. There are $(p-1)^2$ cells. Each one you pick excludes $3(p-2)$ other cells. Each excluded cell gets counted at most twice, so you have at least $\frac 32(p-2)(p-1)$ excluded cells. You then need $p-1+\frac 32(p-2)(p-1)=\frac 32p^2-\frac 72p+2$ cells total, which is too many when $p \ge 3$. It works fine for $p=2$

The argument still needs work when $p$ is composite. It is allowed to pick a cell with $0$?

$\endgroup$
  • $\begingroup$ No, we can't pick a cell with 0, as it is implicitly assumed that the cell with 0 has been picked already-- in the 0 column. $\endgroup$ – Fernando Pessoa Sep 11 '13 at 17:40
  • $\begingroup$ I think you can make the same argument for composites, but counting the excluded cells becomes more complicated. You have fewer cells to pick from (because of the 0's) but exclude fewer cells because there aren't as many with the same number. $\endgroup$ – Ross Millikan Sep 11 '13 at 17:52
  • $\begingroup$ Suppose we are allowed to pick 0-- how does that change the argument? $\endgroup$ – Fernando Pessoa Sep 11 '13 at 19:37
  • $\begingroup$ It gives more flexibility, reducing the number of excluded cells. It doesn't work for $p=4,6$, but for $p=8$ we have $(7,1),(6,2),(1,3),(4,4),(5,5),(3,6),(2,7)$ where the numbers are (row, column) in the table. $\endgroup$ – Ross Millikan Sep 11 '13 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.