17
$\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$
7
  • $\begingroup$ See related discussion here. $\endgroup$
    – RobPratt
    Jan 29, 2020 at 5:44
  • 3
    $\begingroup$ This is a question from the 2020 PROMYS admissions exam. $\endgroup$
    – James Done
    Mar 2, 2020 at 22:02
  • 1
    $\begingroup$ @RobPratt the link is dead $\endgroup$
    – Christian
    Nov 21, 2021 at 13:29
  • $\begingroup$ Related $\endgroup$
    – MJD
    Feb 10 at 22:20
  • $\begingroup$ For $n=2$ you could have 1 opposite any of 2, 3, or 4 and those arrangements would not all be permutations of each other. But yes, none gives identical sets of products. $\endgroup$ Feb 23 at 23:22

3 Answers 3

19
$\begingroup$

Here's a solution for $n=3$, with products 30, 56, and 216:

5 2 3 
1 7 8 
6 4 9 

$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 

$n=7$:

 5 38  1 26 40 44 24 
19 29 22 28  6 20 35 
10 11 31 36 46  3  2 
32 42 18 37 39  7 21 
13 25 23  9 41 34 48 
33 14  4 12 17 43 45 
16  8 30 49 15 27 47 

$n=8$:

37  8  5 63 24 18 31 30 
12 38 19 48 58  3 15 39 
 2 57 41 14 44 51 10 60 
 7  6 45 43 40  9 49 22 
50 29 11 33 47 46 56 64 
54 27 32  1 23 53 17 13 
62 20 34 21 28  4 59 35 
36 26 42 25 55 52 16 61 

$n=9$: infeasible

$n=10$:

53  46  45  31  68  24  20  72  18  65 
78  89  64  69  33  75  57  14   8  49 
93 100  67  81  32  41   4  94  98  74 
15  91  62  83  90  10  84  11   6  23 
34  66  21  26  79  86  12  13  36  60 
30   1  82  70  43  59  88  50  99  17 
40  56  63   2   9  44  97  38  95  58 
16  76  47  25  52  77  87  71  48   3 
27  54  80  28   7  51  19  96  73  55 
92  42  37  22  39   5  35  29  85  61

$n\in\{11,12,13\}$: infeasible


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$} \tag1\label1 \\ \sum_{i,j} x_{i,j,k} &= 1 &&\text{for all $k$} \tag2\label2 \\ \sum_{j,k} \log(k) x_{t,j,k} &= \sum_{i,k} \log(k) x_{i,t,k} &&\text{for all $t$} \tag3\label3 \end{align} Constraint \eqref{1} forces each cell to contain exactly one value. Constraint \eqref{2} forces each value to appear in exactly one cell. Constraint \eqref{3} forces row $t$ and column $t$ to have the same product.


A numerically preferable alternative (with integer coefficients) to \eqref{3} is to let $P$ be the set of primes smaller than $n^2$, let $$k = \prod_{p\in P} p^{m_{k,p}}$$ be the prime factorization of $k$, and impose linear constraints \begin{align} \sum_{j,k} m_{k,p} x_{t,j,k} &= \sum_{i,k} m_{k,p} x_{i,t,k} &&\text{for all $t$ and $p$} \tag4\label4 \end{align} The idea is that row $t$ and column $t$ have the same product iff, for all $p$, prime $p$ appears with the same multiplicity in that row and column.

$\endgroup$
3
  • 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
  • $\begingroup$ Given any solution, the rows and columns may each be permuted freely to get another solution, so in your given solution you may interchange columns 1, 2 and interchange columns 3, 4; then no factor of $5$ is in either diagonal. $\endgroup$ Feb 23 at 23:16
10
$\begingroup$

RobPratt has answered the question for all $n\le 13$. I shall prove in this answer that when $n\ge 11$, there is no solution.

Let $\pi$ be the prime counting function. I claim is impossible to form a grid whenever $$ \pi(n^2)-\pi(\lfloor n^2/2\rfloor )>n\tag1 $$ For any $n$ such that the above is true, there are at least $n+1$ primes in the range $\{1,\dots,n^2\}$ which are more than half of $n^2$. This means for any placement of $\{1,\dots,n^2\}$ in an $n\times n$ grid, there will exist two such "big" primes, $p$ and $q$, which are in the same row. The product of that row is a multiple of $pq$. But then none of the column products can be a multiple of $pq$, so no solution exists.

Since $\pi(n)\sim n/\log n$ as $n\to\infty$, by the prime number theorem, the LHS of $(1)$ grows faster than the RHS, so $(1)$ holds when $n$ is sufficiently large. Specifically, I can prove:

Claim: $(1)$ holds whenever $n\ge e^5\approx 148.4$.

My proof uses two numerical inequalities.

  1. For all $n\ge 17$, we have from the Wikipedia article on $\pi(n)$ that $$\frac{n}{\log n}\le \pi(n)\le \frac43\cdot \frac{n}{\log n}$$

  2. For all $n\ge 10$, we have $$\lfloor n^2/2\rfloor \ge n^2/2-1\ge n^{3/2}.$$ The first inequality is obvious; you can check that the second inequality is true when $n=10$, and by taking the derivative with respect to $n$, you can see that the function $n^2/2-1-n^{3/2}$ is increasing for $n\in [10,\infty)$.

Proof of Claim: $$ \begin{align} \pi(n^2)-\pi(\lfloor n^2/2\rfloor ) &\stackrel{1.}\ge \frac{n^2}{\log n^2}-\frac43\cdot \frac{\lfloor n^2/2\rfloor }{\log\lfloor n^2/2\rfloor} \\&\stackrel{2.}\ge \frac{n^2}{\log n^2}- \frac43\cdot \frac{ n^2/2}{\log n^{3/2}} =\frac{n^2}{18\log n} \end{align} $$ In order to have $\frac{n^2}{18\log n}>n$, it suffices to have $\frac{n}{\log n}>18$. It is easy to check that $\frac{n}{\log n}>18$ holds when $n= e^5$. Since $\frac{n}{\log n}$ is increasing for $n>e$, it holds whenever $n\ge e^5$ as well. $\square$

Finally, you can check with the help of a computer that $(1)$ holds for all $n$ in the range $[11,148]$. Combined with my claim, this completes the proof that no solution exists when $n\ge 11$. For example, the following Mathematica code returns True:

NoCounterExamples = True;

For[n = 11, n <= 150, n++,
    If[PrimePi[n^2] - PrimePi[Floor[n^2/2]] <= n, 
        NoCounterExamples = False]
];

Print[NoCounterExamples]
$\endgroup$
3
  • $\begingroup$ Lovely idea! Those inequalities do suffice to prove (1) when $n\ge23$, as a computer-generated graph tells us—and believing that graph is at least as plausible as believing a computation that there's no solution for $n=9$. $\endgroup$ Feb 11 at 9:07
  • $\begingroup$ @GregMartin For what its worth, I included an "algebraic" proof, but I agree that it is painfully obvious from the graph. $\endgroup$ Feb 11 at 17:03
  • $\begingroup$ With a calculator we can prove that $n/\log n>18$ starting at $n=79$, so the full computer trials may be cut off after $n=78$. $\endgroup$ Feb 23 at 22:18
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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .