14
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ See related discussion here. $\endgroup$
    – RobPratt
    Jan 29, 2020 at 5:44
  • 2
    $\begingroup$ This is a question from the 2020 PROMYS admissions exam. $\endgroup$
    – James Done
    Mar 2, 2020 at 22:02
  • $\begingroup$ @RobPratt the link is dead $\endgroup$
    – Christian
    Nov 21, 2021 at 13:29

2 Answers 2

12
$\begingroup$

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.

$\endgroup$
2
  • 4
    $\begingroup$ 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? $\endgroup$
    – antkam
    Jan 22, 2020 at 18:54
  • $\begingroup$ 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...) $\endgroup$
    – antkam
    Jan 22, 2020 at 19:20
2
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ @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...") $\endgroup$
    – antkam
    Jan 22, 2020 at 19:28
  • 3
    $\begingroup$ 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. $\endgroup$
    – RobPratt
    Jan 22, 2020 at 19:40
  • 2
    $\begingroup$ 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. $\endgroup$
    – user502266
    Jan 23, 2020 at 18:01

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.