20.17

Altheman

Prove that given any $n^2$ integers, we can always put
them in an $n\times n$ matrix whose determinant is divisible by
$n^{\lfloor \frac{n-1}{2}\rfloor}$ .

**Posted:** Wed Jul 22, 2009 8:23 pm

_________________
-Alex
Altheman's Problem Column

fedja

Suppose we have more than $n$ numbers. Then we can choose two with the same remainder modulo $n$ . Now put $n\left\lfloor\frac{n-1}2\right\rfloor$ vertical dominoes in our matrix starting from the left upper corner and going row by row. Fill them in any order by numbers having the same remainder modulo $n$ (if not all dominoes are filled, there are at least $n+2$ numbers left, so we can fill the next one). Now, if we subtract from each odd row the following even row (which does not change the determinant), we'll get $\left\lfloor\frac{n-1}2\right\rfloor$ rows with all numbers divisible by $n$ in the matrix, which makes the desired divisibility statement obvious.

**Posted:** Tue Jul 28, 2009 1:44 pm

me@home

Fedja, what exactly do you mean by $n\left\lfloor\frac{n-1}2\right\rfloor$ vertical dominoes? $n$ rectangles that are $1\times\left\lfloor\frac{n-1}2\right\rfloor$ ? I do not understand your construction in either case.
construction

**Posted:** Sat Oct 03, 2009 9:56 pm

_________________
↓What did the Buddhist monk say when ordering a hamburger?
↓Make me one with everything.
↓Check out my website... I mean, when was the last time you visited a url with "hamburger" embedded into it?

fedja

**Posted:** Sun Oct 04, 2009 5:22 am