Skip to main content
Links to specific answers
Source Link
LSpice
  • 12.9k
  • 4
  • 45
  • 69

Here is the solution of the Promys 2020 problem, following RobPratt and Mike Earnest at https://math.stackexchange.com/q/3518460Can we arrange $\{1,...,16\}$ in $4\times 4$-grid so {products of rows} = {products of columns}?.

Theorem. For $n\in\{1,3,4,5,6,7,8,10\}$ one can arrange $\{1,\dotsc,n^2\}$ in an $n\times n$ grid so that the set of products of columns equals the set of products of rows. For $n\not\in\{1,3,4,5,6,7,8,10\}$$n\notin\{1,3,4,5,6,7,8,10\}$ there is no such arrangement.

Proof. For $n\in\{1,3,4,5,6,7,8,10\}$, see the constructionsconstructions of RobPratt at the link above. For $n=2$ it is easy to check by hand there there is no arrangement. Now assume that $n=9$ or $n\geq 11$. Then, following Mike Earnest's great idea at the link abovegreat idea, it suffices to show that $\pi(n^2)-\pi(n^2/2)>n$. For $n\in\{9,11,12,13,14,15,16\}$ we can verify this by hand. For $n\geq 17$ the required inequality follows from Corollary 3 in Rosser-SchoenfeldRosser–Schoenfeld: Approximate formulas for some functions of prime numbers. Indeed, by this theorem we have that $$\pi(n^2)-\pi(n^2/2)>\frac{(3/10)n^2}{\log(n^2/2)}>n,\qquad n\geq 17.$$

Here is the solution of the Promys 2020 problem, following RobPratt and Mike Earnest at https://math.stackexchange.com/q/3518460

Theorem. For $n\in\{1,3,4,5,6,7,8,10\}$ one can arrange $\{1,\dotsc,n^2\}$ in an $n\times n$ grid so that the set of products of columns equals the set of products of rows. For $n\not\in\{1,3,4,5,6,7,8,10\}$ there is no such arrangement.

Proof. For $n\in\{1,3,4,5,6,7,8,10\}$, see the constructions of RobPratt at the link above. For $n=2$ it is easy to check by hand there there is no arrangement. Now assume that $n=9$ or $n\geq 11$. Then, following Mike Earnest's great idea at the link above, it suffices to show that $\pi(n^2)-\pi(n^2/2)>n$. For $n\in\{9,11,12,13,14,15,16\}$ we can verify this by hand. For $n\geq 17$ the required inequality follows from Corollary 3 in Rosser-Schoenfeld: Approximate formulas for some functions of prime numbers. Indeed, by this theorem we have that $$\pi(n^2)-\pi(n^2/2)>\frac{(3/10)n^2}{\log(n^2/2)}>n,\qquad n\geq 17.$$

Here is the solution of the Promys 2020 problem, following RobPratt and Mike Earnest at Can we arrange $\{1,...,16\}$ in $4\times 4$-grid so {products of rows} = {products of columns}?.

Theorem. For $n\in\{1,3,4,5,6,7,8,10\}$ one can arrange $\{1,\dotsc,n^2\}$ in an $n\times n$ grid so that the set of products of columns equals the set of products of rows. For $n\notin\{1,3,4,5,6,7,8,10\}$ there is no such arrangement.

Proof. For $n\in\{1,3,4,5,6,7,8,10\}$, see the constructions of RobPratt. For $n=2$ it is easy to check by hand there there is no arrangement. Now assume that $n=9$ or $n\geq 11$. Then, following Mike Earnest's great idea, it suffices to show that $\pi(n^2)-\pi(n^2/2)>n$. For $n\in\{9,11,12,13,14,15,16\}$ we can verify this by hand. For $n\geq 17$ the required inequality follows from Corollary 3 in Rosser–Schoenfeld: Approximate formulas for some functions of prime numbers. Indeed, by this theorem we have that $$\pi(n^2)-\pi(n^2/2)>\frac{(3/10)n^2}{\log(n^2/2)}>n,\qquad n\geq 17.$$

Source Link
GH from MO
  • 105.4k
  • 8
  • 293
  • 398

Here is the solution of the Promys 2020 problem, following RobPratt and Mike Earnest at https://math.stackexchange.com/q/3518460

Theorem. For $n\in\{1,3,4,5,6,7,8,10\}$ one can arrange $\{1,\dotsc,n^2\}$ in an $n\times n$ grid so that the set of products of columns equals the set of products of rows. For $n\not\in\{1,3,4,5,6,7,8,10\}$ there is no such arrangement.

Proof. For $n\in\{1,3,4,5,6,7,8,10\}$, see the constructions of RobPratt at the link above. For $n=2$ it is easy to check by hand there there is no arrangement. Now assume that $n=9$ or $n\geq 11$. Then, following Mike Earnest's great idea at the link above, it suffices to show that $\pi(n^2)-\pi(n^2/2)>n$. For $n\in\{9,11,12,13,14,15,16\}$ we can verify this by hand. For $n\geq 17$ the required inequality follows from Corollary 3 in Rosser-Schoenfeld: Approximate formulas for some functions of prime numbers. Indeed, by this theorem we have that $$\pi(n^2)-\pi(n^2/2)>\frac{(3/10)n^2}{\log(n^2/2)}>n,\qquad n\geq 17.$$