20
$\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$
1
  • 1
    $\begingroup$ Because there are a lot of flags on this question noting that it is part of the PROMYS exam: (1) without a link to the problem set and rules stating that using the internet is disallowed, the competition problem policy on Math SE does not apply, and (2) it appears that this question has already been answered on Math SE---it is up to the writers of the exam to vet their problems before posting them. We are not going to retroactively close or delete a three year old question because a new competition is using it. $\endgroup$
    – Xander Henderson
    Commented Jan 14 at 16:02

3 Answers 3

23
$\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
    Commented 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
    Commented 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$ Commented Feb 23, 2023 at 23:16
14
$\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$ Commented Feb 11, 2023 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$ Commented Feb 11, 2023 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$ Commented Feb 23, 2023 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
    Commented 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
    Commented 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
    Commented 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 .