# Can we arrange $\{1,...,16\}$ in $4\times 4$-grid so {products of rows} = {products of columns}?

My motivation is the following question asked by Jacob Steiner, which he then deleted. For which $$n\in\Bbb N$$ is it possible to arrange $$\{1,\ldots,n^2\}$$ in an $$n\times n$$-grid so that the set of products of columns equals the set of products of rows?

The answer for $$n=2$$ is clearly No, since the only possibility, up to a transposition and a permutation of rows and columns, is

1 2
3 4


Since the set of products of rows are $$\{2,12\}$$ and the set of products of columns are $$\{3,8\}$$, this arrangement does not work. So for $$n=2$$, it is not possible to make such an arrangement.

• See related discussion here. Jan 29, 2020 at 5:44
• This is a question from the 2020 PROMYS admissions exam. Mar 2, 2020 at 22:02

Here's a solution for $$n=4$$, with products 6240, 672, 2520, and 1980:

13 16  3 10
4  6 14  2
8  7  5  9
15  1 12 11


$$n=5$$:

17  2  7 15 20
14 25  9 11 16
6 21 13  3 12
10 22 18 23  1
5 24  4  8 19


$$n=6$$:

34 10  5 30 27 14
25 19 36 11  7  2
18 33 29  4 20  8
3 35 22 31 32  9
15 12 16 21 17 26
28  1  6 24 13 23


I used the following integer linear programming formulation. Let binary decision variable $$x_{i,j,k}$$ indicate whether cell $$(i,j)$$ has value $$k$$. You can use any objective function, and the constraints are: \begin{align} \sum_k x_{i,j,k} &= 1 &&\text{for all i, j}\\ \sum_{i,j} x_{i,j,k} &= 1 &&\text{for all k}\\ \sum_{j,k} \log(k) x_{t,j,k} &= \sum_{i,k} \log(k) x_{i,t,k} &&\text{for all t} \end{align} The first constraint forces each cell to contain exactly one value. The second constraint forces each value to appear in exactly one cell. The third constraint forces row $$t$$ and column $$t$$ to have the same product.

• Do you mind telling us how you found this? E.g. by hand, or did you write code, and if code, how smart vs brute-force was it? Jan 22, 2020 at 18:54
• I think (see my answer) the $4 \times 4$ case might not need a factor of $5$ in the diagonal. Any chance you can see if such a solution exists? (Although I think, in terms of computer time usage, solving more $n$ might be more interesting...) Jan 22, 2020 at 19:20

Not an answer, but pointing out a flaw in the OP logic.

If a prime factor appears singly (i.e. not squared) an odd number of times (like $$5$$ appearing as $$\{5, 10, 15\}$$ in the $$4\times 4$$ grid), that does not imply one of the appearances must be along the diagonal. E.g.

* 10  *  *
*  * 15  *
5  *  *  *
*  *  *  *


would meet the requirement as far as factors of $$5$$ are concerned: the first $$3$$ rows and the first $$3$$ columns each has exactly one factor of $$5$$ (and the last row and last column has no factor of $$5$$).

(These positions represent a (fixed-point-free) permutation in the $$3 \times 3$$ submatrix.)

UPDATE: Indeed Rob Pratt found such a matrix:

$$\begin{matrix} 9 &15 &12 &1\\ 3 &11 &14 &5\\ 6 &7 &13 &16\\ 10 &2 &4 &8\end{matrix}$$

where the positions of the multiples of $$5$$ represent a fixed-point-free permutation of the $$3\times 3$$ submatrix after deleting the $$3$$rd row & column.

So the OP claim that the $$4\times 4$$ grid must have a factor of $$5$$ along the diagonal is wrong, and similarly, it is still unproven that $$8 \times 8$$ cannot be filled because that last $$X$$ does not need to be any multiple of $$11, 17, 19$$.

• @MishaLavrov - Sorry I don't understand you. Are you saying e.g. in the $4 \times 4$ grid, the number $13$ does not have to appear in the diagonal? Remember that the OP has (very reasonably) restricted to looking for solutions where row $i$ product $=$ column $i$ product... My answer assumes this very reasonable restriction (see OP paragraph "Since the answer is invariant under permutation...") Jan 22, 2020 at 19:28
• Here's one with no multiple of 5 on the diagonal:\begin{matrix} 9 &15 &12 &1\\ 3 &11 &14 &5\\ 6 &7 &13 &16\\ 10 &2 &4 &8\end{matrix} But if you exclude both diagonal and antidiagonal, there is no feasible solution. Jan 22, 2020 at 19:40
• If a prime has precisely three appearances in a table then either it occurs on the diagonal or it occurs in locations $(a,b),(b,c),(c,a)$ where $a,b,c$ are all different. In the case of $n=4$ this latter possibility means that two of $a,b,c$ must sum to $5$ and the associated location therefore has to be on the anti-diagonal.
– user502266
Jan 23, 2020 at 18:01