Arrange positive divisors of n in rectangular table!

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Arrange positive divisors of n in rectangular table!

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2016 IMO Shortlist C2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

510 posts

#1 h Jul 19, 2017, 4:31 PM • 9 Y

Y by tenplusten, Davi-8191, megarnie, michaelwenquan, whslovemath, lian_the_noob12, Adventure10, Mango247, NicoN9

Find all positive integers $n$ for which all positive divisors of $n$ can be put into the cells of a rectangular table under the following constraints:

each cell contains a distinct divisor;
the sums of all rows are equal; and
the sums of all columns are equal.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6870 posts

#2 h Jul 19, 2017, 4:44 PM • 46 Y

Y by rafayaashary1, MSTang, laegolas, samuel, vsathiam, gemcl, A_Math_Lover, Twistya, Wizard_32, WindTheorist, AlastorMoody, rashah76, Siddharth03, star32, v4913, aops29, RAMUGAUSS, cmsgr8er, Jc426, edfearay123, Modesti, blackbluecar, centslordm, Wizard0001, HamstPan38825, rayfish, meowme, W.R.O.N.G, PIartist, mijail, metricpaper, michaelwenquan, whslovemath, megarnie, Iora, veirab, sabkx, SPHS1234, kamatadu, Math.1234, Adventure10, Mango247, panche, NicoN9, Sedro, Funcshun840

This is an amusing problem --- it's impossible for size reasons, except in the trivial situation $n = 1$ . (One can gain this intuition very quickly from small cases.)

Suppose the grid has dimensions $a$ rows and $b$ columns, $a \ge b > 1$ (the $b=1$ situation gives $n=1$ ).

Clearly the common sum is more than $n$ . On the other hand, there are at most $b-1$ divisors exceeding $\frac nb$ . Since there are $a > b-1$ rows, some row has all entries at most $n/b$ . So that row has sum at most $b \cdot n/b = n$ , impossible.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

715 posts

#3 h Jul 19, 2017, 5:03 PM • 21 Y

Y by MathStudent2002, fattypiggy123, WL0410, mathwizard888, tenplusten, Wizard_32, Siddharth03, fukano_2, Modesti, megarnie, hakN, mijail, michaelwenquan, Quidditch, whslovemath, Adventure10, Mango247, Kingsbane2139, Sedro, NicoN9, Funcshun840

This problem should be Number Theory

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4071 posts

#4 h Jul 19, 2017, 5:11 PM • 3 Y

Y by whslovemath, Adventure10, Mango247

Cute problem

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

92 posts

#5 h Jul 19, 2017, 11:37 PM • 4 Y

Y by BogdanB, whslovemath, Adventure10, Mango247

We claim that $n = 1$ is the only solution. Clearly, it is a solution. Suppose for some $n > 1$ we can arrange its divisors into a $r \times c$ grid where the conditions are all satisfied. If $r = 1$ or $c = 1$ , then the task is impossible, as the number of divisors is greater than one but we can only fit them in one row or column, so there must be two columns (or rows) with distinct sum.

Suppose $r, c > 1$ now. WLOG let $r \ge c$ . Now, as $n$ is a divisor, there must be a row with sum strictly larger than $n$ (as $r, c > 1$ ). Consider the largest number in each row. There must be a row whose largest number is at most the $r$ -th largest divisor. However, we know that the $r$ -th largest divisor is at most $\frac{n}{r}$ (as the smallest possible value for the $r$ -th smallest divisor is clearly $r$ ), so the sum of the row is strictly less than $\frac{n}{r} \cdot c \le \frac{n}{r} \cdot r = n$ , and thus the row containing $n$ and this row must not have the same sum (since $r > 1$ , they are not the same row.). Thus, the task is impossible for $n > 1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1979 posts

#6 h Jul 20, 2017, 1:49 AM • 10 Y

Y by rafayaashary1, tenplusten, biomathematics, math_and_me, L567, MrOreoJuice, Inconsistent, whslovemath, Adventure10, Funcshun840

Anyone wishes to add this to the N ShortList

cjquines0 wrote:

Find all positive integers $n$ for which all positive divisors of $n$ can be put into the cells of a rectangular table under the following constraints:

each cell contains a distinct divisor;
the sums of all rows are equal; and
the sums of all columns are equal.

The only such number is $n=1$ . To see $n>1$ does not satisfy the original condition (call it tableaux property), consider the following.

Let the common value of the row sums be $r$ and of column sums be $c$ . Let there be $k$ rows and $\ell$ columns. Then, $kr=lc=\sigma(n)$ and $kl=\tau(n).$ Since $n$ occurs in one of the cells, $\min \{r, c\} \geqslant n$ so $\tau(n) \leqslant \left(\frac{\sigma(n)}{n}\right)^2.$ Writing $n= \prod^{k}_{i=1}p_i^{e_i}$ in canonical form, we have $\prod_{i} \sqrt{1+e_i} \leqslant \prod_{i} \left(\frac{p_i^{1+e_i}-1}{p_i^{e_i}(p_i-1)}\right).$
Suppose there exists a prime $p$ such that $p^3 \mid n$ , then $\sqrt{\tau(n)} \geqslant 2\left(\sqrt{2}\right)^{k-1}=\left(\sqrt{2}\right)^{k+1},$ and $\frac{\sigma(n)}{n}< \prod \left(1+\frac{1}{p_i-1}\right) \leqslant 2\cdot (1.5) \cdot (1.25)^{k-2}=3\cdot \left(\frac{5}{4}\right)^{k-2},$ so if $k=1$ then $2<1+\frac{1}{p-1},$ contradiction! Else, if $k>1$ then for $k=3$ the inequality fails, so for all subsequent $k$ the LHS grows by $\sqrt{2}$ while the RHS by $1.25<1.4$ so it fails to hold. For $k=2$ we have $2\sqrt{2} \leqslant 2.5,$ contradiction (unless no $p>3$ is a divisor).

Thus, we split into following cases:

Case 1. $n=2^a3^b$ for $(a+1)(b+1) \geqslant 9$ .

Note that $\tau(n)=(a+1)(b+1) \geqslant 9$ so $3 \leqslant \frac{\sigma(n)}{n}=\left(1+\frac{2^a-1}{2^a}\right)\cdot \left(1+\frac{3^b-1}{2.3^b}\right)<2 \cdot (1.5)=3,$ contradiction!

Case 2. $n=2^a3^b$ for $(a+1)(b+1)<9$ .

Note that $n>1$ so a $1 \times t$ table is insufficient; if $k, l \geqslant 3$ then $(a+1)(b+1)=\tau(n)=kp \geqslant 9,$ so we have $2 \in \{k, l\}$ , say $k=2$ . Since all proper divisors of $n$ are at most $0.5n$ and $r \geqslant n+1$ we get a contradiction!

Case 3. $n$ is cube-free.

Write $n=(p_1p_2\dots p_k)\cdot (q_1q_2\dots q_l)^2$ . Then, we have $\tau(n)=2^k3^l$ and $\frac{\sigma(n)}{n}<2(1.5)(1.25)^{k+l-2}=3(1.25)^{k+l-2},$ so $2^k3^{l-2}<(1.5625)^{k+l-2}$ which is clearly, false!

Evidently, no $n>1$ is having the tableaux property, so we are done. $\blacksquare$

This post has been edited 1 time. Last edited by anantmudgal09, Jul 20, 2017, 1:53 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

355 posts

#7 h Jul 20, 2017, 2:34 AM • 5 Y

Y by anantmudgal09, pieater314159, whslovemath, Adventure10, Mango247

@anantmudgal09 many of us at MOP initially thought this was an N problem when it appeared on a test and gave exactly that solution (proving $n>\frac{\sigma(n)}{\sqrt{\tau(n)}}$ except $1,2,4,6$ ).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

475 posts

#8 h Jul 26, 2017, 5:53 AM • 3 Y

Y by whslovemath, Adventure10, Mango247

Let $n=\displaystyle \prod^{k}_{i=1}{p_i^{\alpha_i}}$ . We claim that $\sigma(n)\le n\sqrt{\tau(n)}$ for all $n\neq 1,2,4$ . Note that $\frac{n\sqrt{\tau(n)}}{\sigma(n)}\ge 1 \iff \prod^{k}_{i=1}{\frac{p_i^{\alpha_i}(p_i-1)}{p_i^{\alpha_i+1}-1}\sqrt{\alpha_i+1}}\ge1$ Define functions $\displaystyle f(p,k)=\frac{p^k(p-1)}{p^{k+1}-1}\sqrt{k+1}$ and $\displaystyle g(p,k)=\Big(1-\frac{1}{p}\Big)\sqrt{k+1}$ . It is clear that $g$ is a strictly increasing function in $p$ and $k$ , and $f(p,k)>g(p,k)$ for all $p,k$ . We compute that $f(3,1)=\frac{3}{4}\sqrt{2}>1, f(2,1)=\frac{2}{3}\sqrt{2}=\frac{1}{f(3,1)}, f(2,2)=\frac{4}{7}\sqrt{3}>\frac{2}{3}\sqrt{2}=f(2,1)$ For any $p\ge 5$ , $f(p,k)>g(p,k)\ge g(5,1)=\frac{4}{5}\sqrt{2}>\frac{3}{4}\sqrt{2}=f(3,1)$ For any $k\ge 2$ , $f(3,k)>g(3,k)\ge g(3,2)=\frac{2}{3}\sqrt{2}>\frac{3}{4}\sqrt{2}=f(3,1)$ For any $k\ge 3$ , $f(2,k)>g(2,k)\ge g(2,3)=\frac{1}{2}\sqrt{2}=1$
Suppose $n\neq 1,2,4$ . If $2\nmid n$ , then there exist an odd prime power $p^k$ that divides $n$ , then $\frac{n\sqrt{\tau(n)}}{\sigma(n)}\ge f(p,k)\ge f(3,1)>1$ Else $2\mid n$ , if there exist an odd prime power $p^k$ that divides $n$ , then $\frac{n\sqrt{\tau(n)}}{\sigma(n)}\ge f(2,1)f(p,k)\ge f(2,1)f(3,1)\ge 1$ Else $n=2^k$ and $k\ge 3$ , then $\frac{n\sqrt{\tau(n)}}{\sigma(n)}= f(2,k)>1$ We proved our claim, and so $\sigma(n)\le n\sqrt{\tau(n)}$ for all $n\neq 1,2,4$ .

Back to main problem. Clearly $n=1$ works. Now suppose an arrangement of divisors of $n\ge 2$ in a $A\times B$ rectangle with the given conditions exist. Obviously it fails when $A$ or $B$ is $1$ , so assume $A,B\ge 2$ . We know that $AB=\tau(n)$ , so WLOG $A$ is the longer horizontal side, otherwise flip the rectangle. Then $A\ge \lceil {\sqrt{\tau(n)}} \rceil\ge \sqrt{\tau(n)}$ Consider the $A$ rows, one of the row contains $n$ , so since $B\ge 2$ , the row contains another divisor other than $n$ , so its row sum is strictly greater than $n$ . By given condition, other rows will also have row sum strictly greater than $n$ . So add up all divisors in each row, we have $nA< \sigma(n)$ . Then $n\sqrt{\tau(n)}\le nA < \sigma(n)$ False when $n\neq2,4$ by our claim. But when $n=2, 4$ , $\tau(n)<4$ , so one of the sides $A, B$ must be $1$ , which we know it fails.

So the only answer is $n=1$ . Q.E.D

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1498 posts

suli

#9 h Aug 8, 2017, 7:26 PM • 6 Y

Y by smy2012, IAmTheHazard, Elyson, whslovemath, Adventure10, Mango247

Am I the only one to treat this as an Algebra problem?

First, we will prove the following lemma:

Lemma. $\sum_{k=1}^{m^2 - 1} \frac{1}{k} < m$ for $m \ge 2$ .

Proof. This is clear by induction. Indeed, $1 + \frac{1}{2} + \frac{1}{3} < 2$ , $1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{8} < 2 + \frac{1}{4} + \frac{1}{5} + 3 \cdot \frac{1}{6} < 3$ , and $\sum_{k=m^2}^{(m+1)^2 - 1} \frac{1}{k} < \frac{2m + 1}{m^2} < 1$ for $m \ge 3$ .

Now, suppose $n > 1$ yields a valid $k \times m$ rectangular table. Without loss of generality, let $k \le m$ . Then $n$ has $km \ge 2$ divisors. Also, conditions 2 and 3 force $2 \le k \le m$ . However, there are $m$ columns, each with sum greater than or equal to $n+1$ (since $n$ is in the table), so the sum of the factors of $n$ is at least $m(n+1)$ . On the other hand, the sum of the factors is at most
$n (1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{km-1}) + 1 \le 1 + n \sum_{i=1}^{m^2-1} \frac{1}{i} < nm + 1 < m(n+1),$ contradiction. Hence $n = 1$ , which clearly yields a valid rectangular table.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

688 posts

#10 h Aug 9, 2017, 2:53 AM • 2 Y

Y by Adventure10, Mango247

Nowadays number theory is more or less combined with some combinatorics ideas. I think either part is good.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1600 posts

Vrangr

#11 h Jan 18, 2019, 1:00 PM • 5 Y

Y by AlastorMoody, Pratik12, whslovemath, Adventure10, Mango247

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1218 posts

#12 h Jan 18, 2019, 7:45 PM • 4 Y

Y by whslovemath, Adventure10, Mango247, Mango247

Weird problem

. Anyway, here's another algebraic approach (Hopefully correct): We claim that $n=1$ is the only positive integer which satisfies the given condition. Suppose to the contrary, there exists a $A \times B$ table for some $n>1$ which satisfies the given conditions. WLOG assume that $A \geq B$ . If $B=1$ , then all elements of the only column in this table must be equal, which is only possible when $n=1$ . So we must have $B>1$ . Now, we first take up the case when $A \geq 3$ . Consider the row which consists of $n$ . Then this row must have a sum of at least $n+(1+2+ \dots +(B-1))=n+\frac{B(B-1)}{2}$ Now, consider the row with the smallest sum. As $A \geq 3$ , so this row necessarily has a sum which can not exceed $\frac{n}{B+2}+\frac{n}{B+3}+ \dots +\frac{n}{2B+1}=n(H_{2B+1}-H_{B+1})$ where $H_k$ denotes the $k^{\text{th}}$ harmonic number. Thus, for the sum in these two rows to be equal, we must have $n(H_{2B+1}-H_{B+1}) \geq n+\frac{B(B-1)}{2} \Rightarrow P:=n+\frac{B(B-1)}{2}-n \left(H_{2B+2}-\frac{1}{2B+2}-H_{B+1} \right) \leq 0$ where the last statement follows using the recurrence $H_k=H_{k-1}+\frac{1}{k}$ .

Now, from the proof given here, we have $H_{2k}-H_k \leq \ln(2)$ for all positive integers $k$ . Thus, we get that $n \left(H_{2B+2}-\frac{1}{2B+2}-H_{B+1} \right) \leq n \left(\ln(2)-\frac{1}{2B+2} \right) \Rightarrow P \geq n+\frac{B(B-1)}{2}-n \left(\ln(2)-\frac{1}{2B+2} \right)$ Now, one can easily show (say by induction) that $0<\ln(2)-\frac{1}{2B+2}<1$ for every positive integer $B$ . So we get that $n-n \left(\ln(2)-\frac{1}{2B+2} \right)>0 \Rightarrow P>\frac{B(B-1)}{2}>0 \rightarrow \text{Contradiction}$ Thus, we cannot have $A\geq 3$ ; which gives $A=2=B$ . So now we have a $2 \times 2$ table with distinct positive integral elements $w,x,y,z$ (in clockwise order) satisfying $w+x=y+z$ and $w+z=x+y$ . However, subtracting these two equalities gives $x-z=z-x$ , or equivalently $x=z$ . Thus, we arrive at a contradiction in this situation also. Hence, done. $\blacksquare$

This post has been edited 5 times. Last edited by math_pi_rate, Feb 28, 2019, 9:02 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1614 posts

yayups

#13 h Feb 28, 2019, 7:09 AM • 2 Y

Y by whslovemath, Adventure10

Probably the first time a number theory/algebra problem has been characterized as combinatorics (its usually the other way around).

For $n=1$ this is obviously possible. We show its not possible for any other $n$ . Suppose for sake of contradiction we have a solution for $n\ge 2$ .

Say the dimensions of the rectangle are $a\times b$ . We have $ab=\tau(n)$ (the number of divisors of $n$ ), so WLOG $a\ge\sqrt{\tau(n)}$ . Thus, the row sum is $f(n):=\sigma(n)/a\le\sigma(n)/\sqrt{\tau(n)}$ where $\sigma(n)$ is the sum of the divisors of $n$ . We see that $n$ is there somewhere, along with something else (we can't have an $a\times 1$ grid), so $f(n)> n$ , so $g(n)> 1$ where $g(n)=\frac{\sigma(n)}{n\sqrt{\tau(n)}}$ . Note that $g(mn)=g(m)g(n)$ for $\gcd(m,n)=1$ .

Lemma: $g(p^e)<1$ if $p^e\ne 2,4$ .

Proof of Lemma: We see that
$\begin{align*} g(p^e)&=\frac{\frac{p^{e+1}-1}{p-1}}{p^e\sqrt{e+1}}\\ &=\frac{1}{\sqrt{e+1}}\frac{1-1/p^{e+1}}{1-1/p}\\ &<\frac{1}{\sqrt{e+1}}\frac{p}{p-1}. \end{align*}$ If $p\ge 5$ , then $g(p^e)<\frac{5}{4\sqrt{2}}<1$ . If $p=3$ , and $e\ge 2$ , then $g(3^e)<\frac{\sqrt{3}}{2}<1$ , and if $p=2$ and $e\ge 3$ , then $g(2^e)<2/\sqrt{4}=1$ . Thus, we only have to check $2,3,4$ , and we see that actually $g(3)=2\sqrt{2}/3<1$ . Therefore, unless $p^e=2,4$ , we have $g(p^e)<1$ . $\blacksquare$

We see that if $\nu_2(n)\ne 1,2$ , then $g(n)<1$ , so we must have $\nu_2(n)=1,2$ . We have $g(2)=3\sqrt{2}/4$ and $g(4)=7/4\sqrt{3}$ . It is easy to see that $n=2$ and $n=4$ don't satisfy the conditions of the problem, so there is some other prime dividing $n$ besides $2$ . If that prime is at least $5$ , then we already saw that $g(p^e)<5/4\sqrt{2}$ , so $g(n)<\frac{3\sqrt{2}}{4}\frac{5}{4\sqrt{2}}=15/16<1$ . Therefore, the other prime must be $3$ .

We see that $g(3^e)\le \sqrt{3}/2$ for $e\ge 2$ , and $g(e)=2\sqrt{2}/3$ , so $g(3^e)\le 2\sqrt{2}/3$ for all $e\ge 1$ . Thus, $g(n)\le\frac{2\sqrt{2}}{3}\frac{3\sqrt{2}}{4}=1$ , so we have a contradiction since $g(n)>1$ . Therefore, there are no solutions except $\boxed{n=1}$ .

This post has been edited 1 time. Last edited by yayups, Feb 28, 2019, 7:09 AM
Reason: latex error

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1671 posts

pad

#14 h Apr 10, 2019, 6:18 PM • 3 Y

Y by whslovemath, Adventure10, Alcumusgrinder07

Let the grid be $a\times b$ . WLOG $a \ge b$ . Then $ab = \tau(n)$ , so $a\ge \sqrt{\tau(n)}$ . The sum of all numbers in the grid is $\sigma(n)$ , so the common row sum is $\sigma(n)/a$ . But some row must include $n$ , so the row sum is at least $n$ . Therefore, $\tfrac{\sigma(n)}{\sqrt{\tau(n)}}\ge n$ , or equivalently,
$f(n) := \frac{n^2\tau(n)}{\sigma(n)^2} \le 1.$ First we will find when $f(p^k) \le 1$ for a prime $p$ and $k\ge 1$ . We see that
$\begin{align*} f(p^k) &= \frac{p^{2k}\tau(p^k)}{\sigma(p^k)^2} \\ &= \frac{p^{2k}(k+1)}{\left( \frac{p^{k+1}-1}{p-1}\right)^2} \\ &= \frac{p^{2k}(p-1)^2(k+1)}{(p^{k+1}-1)^2} \\ &= \frac{p^{2k+2}(k+1)}{(p^{k+1}-1)^2} \cdot \left(\frac{p-1}{p}\right)^2\\ &> (k+1)\left(\frac{p-1}{p}\right)^2. \end{align*}$ Now we have $(k+1)\left(\tfrac{p-1}{p}\right)^2 \le 1$ . For $p=2$ , $\left(\tfrac{p-1}{p}\right)^2 = \tfrac14$ , so $k=1,2,3$ are the only possible choices. For $p=3$ , $\left(\tfrac{p-1}{p}\right)^2 = \tfrac49$ , so $k=1$ is the only possible choice. For $p\ge 5$ , $\left(\tfrac{p-1}{p}\right)^2 = \left(1-\tfrac{1}{p}\right)^2 \ge \tfrac{16}{25}$ , so no value of $k\ge 1$ works. So the only possible prime powers that work are $p^k = 2,3,4,8$ .

Since $\tau, \sigma, n$ are all multiplicative for coprime numbers, $f$ is also multiplicative for coprime numbers. Therefore, any $n$ that works must be a product of these prime powers. So we can only have $n=2^a3^b$ , where $0\le a \le 6$ and $0\le b\le 1$ . We have
$f(2^a3^b) = \frac{2^{2a}3^{2b}(a+1)(b+1)}{(2^{a+1}-1)(2^{b+1}-1)},$ and now we just check all $14$ possibilities for $n$ . Once we do this, we see that only $n=1,2,4,6$ have $f(n) \le 1$ . However, $n=2$ and $n=3$ clearly don't work (we would need a 1 by 2 or 1 by 3 grid), and $n=6$ also does not work (1 by 4 does not work, and 2 by 2 doesn't either). Clearly, $n=1$ works, so only $\boxed{n=1}$ satisfies the original property.

This post has been edited 2 times. Last edited by pad, Apr 10, 2019, 10:01 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2726 posts

#15 h Jun 14, 2020, 12:14 AM • 4 Y

Y by yayups, fukano_2, whslovemath, Iora

I claim that our unique answer is $\boxed{n = 1}$ . Now consider $n > 1$ .

Suppose that this grid has $a$ rows and $b$ columns, where WLOG we assume $a \geq b$ . Let each row have common sum $s$ and each column have common sum $t$ . Note that some row and column would have to contain $n$ , hence $s, t > n$ .

Claim: Some row has sum at most $n$ .
Proof: It suffices to show that there exists a row such that all $b$ of its elements are less than $\tfrac{n}{b}$ . Note that for any $b$ , at most $b - 1 < b \leq a$ of $n$ 's divisors could exceed $\tfrac{n}{b}$ since these divisors must be from $\{\tfrac{n}{1}, \tfrac{n}{2}, \ldots , \tfrac{n}{d-1}\}$ . Since there are less than $a$ divisors of $n$ that exceed $\tfrac{n}{b}$ , by pigeonhole principle, one of these $a$ rows will not receive any such divisor of $n$ greater than $\frac{n}{b}$ . This row has maximum possible sum $b \cdot \tfrac{n}{b} = b$ , as desired.

This finishes the problem with contradiction. Hence for all $n > 1$ is it not possible. $\blacksquare$

Remark: I was motivated to find this solution because this problem was in the Combinatorics shortlist.

This post has been edited 1 time. Last edited by jj_ca888, Jun 14, 2020, 12:29 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

626 posts

#16 h Oct 5, 2020, 5:48 PM

Y by

Obviously $n=1$ works; we show that no other $n$ work.

Let the grid have $k$ columns and $m$ rows with $m \leq k$ . If $m=1$ then it's obvious that $k=1$ and thus $n=1$ ; thus assume $m \geq 2$ . The common column sum must be at greater than $n$ , so every column must contain some divisor greate than $\tfrac{n}{m}$ . However, there are only $m-1$ such divisors, which is a contradiction because we have $k>m-1$ columns.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

77 posts

#17 h Oct 15, 2020, 1:52 AM • 1 Y

Y by whslovemath

Anyways without thinking I jumped straight into NT. So I ended up solving it by proving the bound
$\sqrt{\tau(n)} > \frac{\sigma(n)}{n}$ Not too too bad, because easy to show that at most 4 prime factors, and just some casework after.

But... it is a lot of extra work compared to the combinatorics solution.
Anyways, I'm super mad because I was once again tricked by the nefarious problem selection committee. :bomb:

:bomb:

:wallbash_red:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

597 posts

#18 h Mar 15, 2021, 3:48 AM • 1 Y

Y by whslovemath

This problem exhibits high concentrations of meme

Let the rectangle be $a$ by $b$ , with WLOG $a \leq b$ . Consider the largest number in each of the $b$ rows. Since there are at most $b$ divisors greater than or equal to $\frac{n}{b}$ , we know that one of the $b$ rows must have greatest element at most $\frac{n}{b}$ . Thus the sum in that row is $\frac{n}{b} \cdot a < n$ .

However, by looking at the row containing $n$ , we get that the sum is at least $n$ . Thus contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

243 posts

lneis1

#19 h Mar 29, 2021, 3:59 AM • 2 Y

Y by whslovemath, Mango247

STORAGE

Remark

This post has been edited 4 times. Last edited by lneis1, Mar 29, 2021, 4:12 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

434 posts

#20 h Jun 30, 2021, 12:41 AM • 3 Y

Y by whslovemath, Mango247, kamatadu

v_Enhance wrote:

This is an amusing problem --- it's impossible for size reasons, except in the trivial situation $n = 1$ . (One can gain this intuition very quickly from small cases.)

Suppose the grid has dimensions $a$ rows and $b$ columns, $a \ge b > 1$ (the $b=1$ situation gives $n=1$ ).

Clearly the common sum is more than $n$ . On the other hand, there are at most $b-1$ divisors exceeding $\frac nb$ . Since there are $a > b-1$ rows, some row has all entries at most $n/b$ . So that row has sum at most $b \cdot n/b = n$ , impossible.

That is so clever it makes me wanna cry. ;-;
----
We claim the only answer is $n=1.$ Each column and row must have sum at least $n.$ As a result, it must be true that for all valid $n,$
$\sigma(n) \ge n\sqrt{d(n)},$ In other words, over all prime powers $p^k$ of $n,$
$\prod_{p\mid n} \sum_{i=0}^{k} p^i \ge \prod_{p\mid n} p^k \prod \sqrt{k+1} \iff \prod_{p\mid n} \sum_{i=0}^k \frac{1}{p^i} \ge \prod\sqrt{k+1}$ Observe that for all $p>3,$
$\sum_{i=0}^k \frac{1}{p^i} < \sum_{i=0}^\infty \frac{1}{p^i} = \frac{p}{p-1} < \sqrt2 \le \sqrt{k+1},$ And additionally, for $p=3,$ $1 + 1/3 < \sqrt{2}$ and for $k>1,$
$\sum_{i=0}^k \frac{1}{3^i} < \frac 32 < \sqrt{3} \le \sqrt{k+1},$ Implying for all $p>2,$ the right hand side factor is larger. Thus, in order for $\sigma(n) \ge n\sqrt{d(n)},$ must be true that either $n=1$ or $2\mid n$ and
$2 \ge \sum_{i=0}^k \frac{1}{2} \ge \sqrt{k+1},$ Implying $v_2(n) \le 3.$ However, it is obvious that $15/8 \le \sqrt4$ so $v_2(n) \le 2.$

Claim: $\sqrt{k+1} \ge \dfrac{p\sqrt2}{p+1}\sum_{i=0}^k 1/p^i.$

Proof. Note that it is obviously true for $k=1,2.$ For $k>2,$
$\dfrac{p\sqrt2}{p+1}\sum_{i=0}^k 1/p^i \le \sqrt{2} + \frac{\sqrt2}{p^2-1} \le \frac{4\sqrt2}{3} <\sqrt4 \le \sqrt{k+1}. \blacksquare$
If $v_2(n) = 1,$ then from our earlier claim,
$\frac{3}{2\sqrt2} \prod_{2\ne p\mid n} \sum_{i=0}^e \frac{1}{p^i} \ge \prod_{e\ne v_2(n)} \sqrt{e+1} \iff \frac{3}{2\sqrt2} \ge \prod_{2\ne p^e \mid n} \frac{\sqrt{e+1}}{1+ 1/p + \cdots + 1/p^e} \ge \prod_{p} \frac{p\sqrt2}{p+1},$ Implying $v_3(n)\le 1$ and $v_p(n) = 0$ for all other primes. Hence, $n=2$ or $n=6$ are the only such possibilities. Similarly, if $v_2(n) = 2,$
$\frac{7}{4\sqrt3} \prod_{2\ne p\mid n} \sum_{i=0}^e \frac{1}{p^i} \ge \prod_{e\ne v_2(n)} \sqrt{e+1} \iff \frac{7}{4\sqrt3} \ge \prod_{2\ne p^e \mid n} \frac{\sqrt{e+1}}{1+ 1/p + \cdots + 1/p^e} \ge \prod_{p} \frac{p\sqrt2}{p+1} \ge \frac{3\sqrt2}{4} > \frac{7}{4\sqrt3},$ Implying no other primes $p$ may divide such $n,$ so remaining possible value of $n$ is $n=4.$ It is easy to see that $n=2,4,6$ all fail, so $n=1$ is the only solution. $\blacksquare$

This post has been edited 1 time. Last edited by cmsgr8er, Jun 30, 2021, 12:44 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

46 posts

Mano

#21 h Nov 8, 2021, 8:46 PM • 1 Y

Y by whslovemath

A new idea which I haven't seen in the posts before (Using Cauchy-Schwarz and $\frac{\pi^2}{6}$

):
First, we obtain the bound $\sigma(n)\geq n\sqrt{\tau(n)}$ (which should be true for all such $n$ ) like in any of the posts before. It is equivalent to $\left(\sum_{d\mid n}d\right)^2\geq n^2\sum_{d\mid n}1$ or alternatively, $\left(\sum_{d\mid n}\frac{1}{d}\right)^2\geq \sum_{d\mid n}1,$ where the bijection between $\frac{d}{n}$ and $\frac{1}{d}$ is used. Assume semi-WLOG that $n$ is not a square number (the other case is similar) and by Cauchy-Schwarz, we obtain: $\left(\sum_{d<\sqrt{n}}\left(\frac{1}{d}+\frac{d}{n}\right)^2\right)\left(\sum_{d<\sqrt{n}}1\right)\overset{C-S}{\geq}\left(\sum_{d<\sqrt{n}}\left(\frac{1}{d}+\frac{d}{n}\right)\cdot1\right)^2=\left(\sum_{d<\sqrt{n}}\left(\frac{1}{d}+\frac{d}{n}\right)\right)^2\geq \sum_{d\mid n}1,$ where $d<\sqrt{n}$ only runs over divisors of $n$ . But because of the bijection, $\sum_{d<\sqrt{n}}1$ is just $\frac{\tau(n)}{2}$ . Using the bijection once more, we obtain $2\leq\sum_{d<\sqrt{n}}\left(\frac{1}{d}+\frac{d}{n}\right)^2=\sum_{d<\sqrt{n}}\left(\frac{1}{d^2}+\frac{d^2}{n^2}+\frac{2}{n}\right)=\sum_{d\mid n}\frac{1}{d^2}+\sum_{d<\sqrt{n}}\frac{2}{n}<\frac{\pi^2}{6}+\frac{\tau(n)}{2}\cdot\frac{2}{n}<\frac{5}{3}+\frac{2\sqrt{n}}{n},$ which gives $\sqrt{n}<6$ or $n<36$ , which cases can be done manually.

This post has been edited 1 time. Last edited by Mano, Nov 8, 2021, 8:47 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5542 posts

#22 h Dec 19, 2021, 5:29 AM

Y by

The answer is $\boxed{n=1}$ , which clearly works. So henceforth assume $n>1$ .

Let the dimensions be $a$ rows and $b$ columns, where $a\ge b>1$ (as $b=1$ gives $n=1$ ).

Consider the largest cell in each of the $a$ rows. Clearly, one of them must be less than or equal to $\frac{n}{a}$ , which implies the common sum of each row is at most $\frac{nb}{a}\le n$ .

Since one of the rows has $n$ in it, the common sum must be greater than $n$ , a contradiction.

This post has been edited 1 time. Last edited by megarnie, Dec 19, 2021, 5:29 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

496 posts

#23 h Feb 21, 2022, 1:20 AM • 1 Y

Y by whslovemath

There's probably an elegant way to do this that I missed :sadge:
We claim $n=1$ is the only solution. It is easy to see that this works because it's literally just a square with the number $1$ in it.
Let $f(n)$ and $\delta (n)$ denote the number and sum of the positive divisors of $n$ respectively.
Let the grid be $x$ by $y$ . So, $xy=f(n)$ . Note the row and column sums are $\frac{\delta(n)}x$ and $\frac{\delta(n)}y$ respectively. Because $n$ is in a row and column, $\frac{\delta(n)}x>n$ and $\frac{\delta(n)}y>n$

WLOG $x\geq \sqrt{f(n)}$ . Then,
$\frac{\delta(n)}{\sqrt{f(n)}}>n$ $\frac{\delta(n)}{n}>\sqrt{f(n)}$ $\left( \frac{\delta(n)}{n}\right)^2>f(n)$ Assume towards a contradiction that $n$ has a prime factor. Let $n=p_1^{a_1}\ldots p_m^{a_m}$ where $p_1,\ldots,p_m$ are distinct primes and $a_1,\ldots, a_n$ are positive integers. Then,
$\delta (n)=\prod_{i=1}^m \left(\sum_{k=0}^{a_i} p_i^k \right)$ $f (n)=\prod_{i=1}^m (a_i+1)$ Therefore,
$\Bigg( \frac{\prod_{i=1}^m \left(\sum_{k=0}^{a_i} p_i^k \right)}{\prod_{i=1}^m p_i^{a_i}}\Bigg)^2 \geq \prod_{i=1}^m (a_i+1)$ $\Bigg( \prod_{i=1}^m \frac{\sum_{k=0}^{a_i} p_i^k}{p_i^{a_i}}\Bigg)^2 \geq \prod_{i=1}^m (a_i+1)$ $\Bigg( \prod_{i=1}^m \sum_{k=0}^{a_i} p_i^{k-a_i}\Bigg)^2 \geq \prod_{i=1}^m (a_i+1)$ Taking the maximum value of the LHS and the minimum value of the RHS, we get
$\prod_{i=1}^m \left(\frac{p_i}{p_i-1}\right)^2 \geq 2^m$ $\prod_{i=1}^m \frac{p_i^2}{2(p_i-1)^2} \geq 1$ We claim that this implies $m\leq 4$ . Note that the LHS is maximized when the $p_i$ are minimized. So, assume the $p_i$ are the first $m$ prime numbers. For all $p_i\geq 5$ , $\frac{p_i^2}{2(p_i-1)^2}\leq 1$ . Therefore for $m\geq 3$ , the LHS is decreases as $m$ increases. So, to show the inequality does not hold for $m\geq 5$ , it suffices to show that it does not hold for $m=5$ . We can do this by plugging in $2, 3, 5, 7, 11$ to get
$\frac{2^2}{2(2-1)^2}\frac{3^2}{2(3-1)^2}\frac{5^2}{2(5-1)^2}\frac{7^2}{2(7-1)^2}\frac{11^2}{2(11-1)^2}=\frac{5929}{8192} \geq 1$ which is obviously false.

We claim that $m=1, 2, 3, 4$ does not work either. Let $m=4$ . Then,
$\prod_{i=1}^m \left(\frac{p_i}{p_i-1}\right)^2 \geq \prod_{i=1}^m (a_i+1)$ $\left(\frac{2}{1}\frac{3}{2}\frac{5}{4}\frac{7}{6}\right)^2 \geq \prod_{i=1}^m (a_i+1)$ $19 \geq \prod_{i=1}^m (a_i+1)$ Therefore for all $i$ , $a_i=1$ . Thus,
$\Bigg( \prod_{i=1}^m \frac{p_i+1}{p_i}\Bigg)^2 \geq 16$ $\prod_{i=1}^m \frac{p_i+1}{p_i} \geq 4$ The LHS is maximized when the $p_i$ are minimized. However, plugging in $2, 3, 5, 7$ , we get
$\frac{3}{2}\frac{4}{3}\frac{6}{5}\frac{8}{7}=\frac{96}{35}\geq 4$ which is obviously false.

We claim that if $n>1$ the width and height must both be greater than $2$ . If the width is $1$ , then different factors are in different rows, causing them to have different sums. If the width is 2, there is a row containing $n$ and a row not containing $n$ . Each proper divisor of $n$ is less than or equal to $\frac{n}2$ . Therefore, the row without $n$ has sum at most $n$ . However, the row with $n$ must have a sum more than $n$ because it contains $n$ and another factor. Because there are at least 3 rows and columns, $f(n)\geq 9$ , so $\prod_{i=1}^m (a_i+1)\geq 9$ .
We can see
$\left(\frac{2}{1}\frac{3}{2}\frac{5}{4}\right)^2 \geq \prod_{i=1}^m (a_i+1)$ $14 \geq \prod_{i=1}^m (a_i+1)\geq 9$ If the $a_i$ 's are all $1$ , then $\prod_{i=1}^m (a_i+1)<9$ . If two of them are $2$ or one of them is $3$ then $\prod_{i=1}^m (a_i+1)>14$ . Therefore WLOG $a_1=2$ and $a_2=a_3=1$ . We have
$\left(\frac{(p_1^2+p_1+1)(p_2+1)(p_3+1)}{p_1^2p_2p_3}\right)^2 \geq 12$ Note that the LHS is maximized when the $p_i$ are minimized. Assume towards a contradiction $p_1>2$ . To maximize the LHS let $p_1=3$ and $p_2=p_3=2$ . This isn't technically possible because the $p_i$ have to be different, but if the inequality doesn't work in this case it cannot work in any case, because in any other case the LHS will be smaller. Indeed, the inequality doesn't hold because we get
$\left(\frac{(9+3+1)(2+1)(2+1)}{3^2\cdot 2\cdot 2}\right)^2=\frac{169}{16} \geq 12$ which is clearly false. Therefore, $p_1=2$ . In this case, the maximum that the LHS can be is
$\left(\frac{(4+2+1)(3+1)(5+1)}{2^2\cdot 3\cdot 5}\right)^2=\frac{196}{25}$ which is less than $12$ .
Now, assume towards a contradiction $m=2$ .
Then $(2)^2(\frac32)^2\geq f(n)$ . Because $9\geq f(n)\geq 9$ , $f(n)=9$ . Thus $n$ is of the form $p_1^2p_2^2$ . We get
$\left( \frac{(p_1^2+p_1+1)(p_2^2+p_2+1}{p_1^2p_2^2}\right)^2\geq 9$ $\frac{(p_1^2+p_1+1)(p_2^2+p_2+1)}{p_1^2p_2^2} \geq 3$ Again, the LHS is maximized when the $p_i$ are minimized. Plug in $2$ and $3$ to get
$\frac{(4+2+1)(9+3+1)}{2^2\cdot 3^2}=\frac{91}{36} \geq 3$ which is obviously false, a contradiction.

Finally, if $m=1$ , then we get $(2)^2\geq f(n)$ , which contradicts $f(n)\geq 9$ . Therefore, $n$ cannot have any positive number of prime factors, so the only solution is $n=1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5542 posts

#24 h Feb 21, 2022, 1:25 AM

Y by

awesomehuman wrote:

There's probably an elegant way to do this that I missed :sadge:
hidden for length

Yes there is

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

496 posts

#25 h Feb 21, 2022, 1:29 AM • 1 Y

Y by whslovemath

Yeah I read the other solutions after

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

11125 posts

#26 h Mar 30, 2022, 3:12 PM • 1 Y

Y by whslovemath

Suppose that the grid has only one column. Then the sums of all rows must be equal, so there can only be one row, and so $n=1$ which satisfies the conditions.

Now we return to the general case. Let there be $a$ rows each with sum $x$ and $b$ columns each with sum $y$ . We can assume that $y\ge x\ge2$ and that $n$ is composite. Note that $ab=\tau(n)$ and $ax=by=\sigma(n)$ , so $xy=\frac{\sigma(n)^2}{\tau(n)}$ .
On the other hand, multiplying the sums of the row and column containing $n$ gives $xy\ge n^2$ , so we should have:
$\frac{\sigma(n)^2}{\tau(n)}\ge n^2.$
But instead, we claim that:
Claim: $\frac{\sigma(n)^2}{\tau(n)}<n^2$
Let $f(n)=\frac{\sigma(n)^2}{\tau(n)}$ . Note that $f(nm)=f(n)f(m)$ if $\gcd(n,m)=1$ , so it suffices to show that $f(p^k)<p^{2k}$ for prime powers $p^k$ .

Suppose first that $p\ge5$ . This is equivalent to checking that:
$\frac{\left(\frac{p^{k+1}-1}{p-1}\right)^2}{k+1}<p^{2k}\Leftrightarrow (p^{k+1}-1)^2<(k+1)(p-1)^2p^{2k},$ which is true since $p^2\le2(p-1)^2$ and:
$(p^{k+1}-1)^2<p^{2k+2}\le2p^{2k}(p-1)^2\le(k+1)(p-1)^2p^{2k}.$
Now suppose that $p=2$ . We need to prove that:
$(2^{k+1}-1)^2<(k+1)2^{2k}\Leftrightarrow (k-3)2^{2k}+2^{k+2}-1>0.$ This is satisfied for $k\ge3$ . If $k=1$ then $\frac{\sigma(n)^2}{\tau(n)}-n^2=\frac72$ , and if $k=2$ then $\frac{\sigma(n)^2}{\tau(n)}-n^2=\frac13$ .

Finally, take the case $p=3$ . We will show that:
$(3^{k+1}-1)^2<4(k+1)3^{2k}\Leftrightarrow (4k-5)3^{2k}+2\cdot3^{k+1}>1.$ It's true for $k\ge2$ clearly, and for $k=1$ we see that it's equivalent to $9>1$ .

The inequality we proved in our claim implies a contradiction, so the only possibility is $n=1$ .

This post has been edited 1 time. Last edited by jasperE3, Mar 30, 2022, 3:13 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3217 posts

#27 h Apr 12, 2022, 10:13 PM • 1 Y

Y by whslovemath

$n=1$ works; now assume otherwise that $n$ has at least $2$ divisors.

if the grid has $x$ rows, then there are at least $n-x+1$ divisors of $n$ greater than $x$ . By pigeonhole, a row must have sum less than or equal to $n$ , which can't happen since $n$ is a divisor of itself.

This post has been edited 1 time. Last edited by mathleticguyyy, Apr 12, 2022, 10:14 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1455 posts

#28 h Apr 24, 2022, 7:53 AM • 1 Y

Y by whslovemath

I almost used PNT on this... That should be a crime for so many reasons...

$\tau(\text{lcm}(1, \ldots, n)) \geq 2^{\pi(n)} \geq 2^{\frac{n}{3\ln n}} \geq \frac{2^n}{n^3} \geq n^2$ for $n \geq 23$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1674 posts

awesomeming327.

#29 h Jun 16, 2022, 10:53 PM • 1 Y

Y by whslovemath

Suppose there are $a$ rows and $b$ columns, $a\ge b$ and $b>1.$ If the board own has $1$ column that every divisor is the same, implying $n=1.$ Note that the sum of each row must be at least $n+3$ so the sum of all the divisors must be $a(n+3).$

Now, the sum of each column will be $\frac{a}{b}(n+3)$ so the average value of each column will be $\frac{n+3}{b}.$ Thus, by pigeonhole, in each column there is a divisor of value at least $\frac{n+3}{b}$ so there are at least $b$ divisors of this type.

For each divisor $k\ge \frac{n+3}{b}$ there is a divisor $k'\le \frac{n}{n+3}(b) < b.$ Thus, there cannot be at least $b$ divisors $k$ so no such boards exist. The only possible $n$ is $1.$

what's PNT?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6870 posts

#30 h Jun 17, 2022, 3:05 AM • 4 Y

Y by HamstPan38825, awesomeming327., Cygnet, megarnie

awesomeming327. wrote:

what's PNT?

https://en.wikipedia.org/wiki/Prime_number_theorem

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

966 posts

lrjr24

#31 h Jul 21, 2022, 4:14 AM

Y by

We claim the answer is $n=1$ . It is easy to check this is the only solution among $n=1,2,4$ . Henceforth assume $n \neq 1,2,4$ . Note that there is at least $\sqrt{\tau(n)}$ rows or $\sqrt{\tau(n)}$ columns. Assume there is at least $\sqrt{\tau(n)}$ rows. Note that the grid has dimensions bigger than $1$ , so the common sum of the rows is greater than $n$ . Thus $n \sqrt{\tau(n)} < \sigma(n)$ . Thus $f(n)=\frac{n^2\tau(n)}{\sigma(n)^2}<1.$ We claim that $f(n) \ge 1$ for $n \neq 1,2,4$ , proving the problem. Note that $f(n)$ is multiplicative. We have that $f(p^k) = \frac{p^{2k}(k+1)}{(\frac{p^{k+1}-1}{p-1})^2} > \frac{(p-1)^2(k+1)}{p^2}.$ Note that $f(2)=\frac{8}{9}$ , $f(4)=\frac{48}{49}$ , $f(8)=\frac{256}{225}$ , and $f(3)=\frac{9}{8}$ . For all other values, the inequality gives that $f(p^k)>\frac{9}{8}$ . If $2 \nmid n$ or $8|n$ , then we have $f(n)>1$ as all $p^k|n$ have $f(p^k)>1$ . If $v_2(n)=1$ , then we get that $n=2$ and if $v_2(n)=2$ we get that $n=4$ using similar arguments and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

54 posts

#32 h Aug 1, 2022, 9:55 PM

Y by

We claim that $n=1$ is the only solution. We can check that $n=1$ works, so suppose $n>1$ . Let the table have $a$ columns and $b$ rows, with $a\geq b$ . Clearly if $b=1$ we can't have that the sums of all columns are equal, so $a\geq b>1$ . Then $ab=\tau(n)$ , where $\tau(n)$ is the number of positive divisors of $n$ . We can see from the column including $n$ that the column-sums must be greater than $n$ .

Furthermore, there are at most $b-1$ positive divisors of $n$ that are greater than $\tfrac{n}{b}$ , since they must all be in the list $\tfrac{n}{1},\tfrac{n}{2},\dots,\tfrac{n}{b-1}$ . Since $a\geq b$ , it follows from pigeonhole that there is a column with entries being at most $\tfrac{n}{b}$ . Then the sum of the elements in that column is at most $b\cdot \tfrac{n}{b}=n$ , contradicting the lower bound for column sums.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

559 posts

#33 h Oct 19, 2022, 10:03 PM

Y by

We claim that $n=1$ is the only such integer (it clearly satisfies the property). Suppose for $n>1$ we have a putting of it's divisors into the cell of table $a\times b$ with $a$ rows and $a\geq b.$ Notice that $b>1,$ since either $n=1,$ and since $n$ is placed into the table, equal sums of rows are more than $n.$ There are at most $b-1$ divisor of $n$ exceeding $\frac nb$ , therefore by Pigeonhole principle some of $a>b-1$ rows doesn't include such a divisor - it has sum at most $b\cdot \frac nb.$ This contradiction finishes our proof.

This post has been edited 2 times. Last edited by JAnatolGT_00, Oct 19, 2022, 10:03 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

194 posts

Iora

#34 h Nov 25, 2022, 6:35 AM

Y by

Same solutions as everyone, posting for storage

Checking smaller cases, one may notice that by size reasons $n>1$ doesn't work. This is our motivation.
Clearly $n=1$ works. Consider the case $n>1$ . Let $a,b$ be number of rows and columns our rectangle has respectively. Notice that $a>b-1>0$ .
Notice that $n$ is a divisor of $n$ too, hence $n$ is placed in a row and a column, hence sum of rows and columns are bigger than $n$ .
Note that there are at most $b-1$ divisors greater than $\frac{n}{b}$ which is clear why. But since $a>b-1$ , by PHP there are at least one row such that its elements are smaller or equal to $\frac{n}{b}$ . Since each row has $b$ elements, then there are atleast one row such that the sum is not greater than $n$ , contradiction, hence $n>1$ is impossible. (Notice that $n=1$ makes $b-1=0$ ,that is why this case works.)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1878 posts

#35 h Dec 10, 2022, 1:55 PM

Y by

Solved with Coolmath2046.

We claim that the answer is when $\boxed{n=1}$ , which works. We will now prove that this is the only value of $n$ that works.

Assume WLOG that the number of rows in the grid is less than or equal to the number of columns in the grid. Then every column must have a sum of at least $n$ , which means that $n\sqrt{d(n)}\le n\cdot(\text{number of columns})\le\sigma(n)\le n\left(1+\frac12+\dots+\frac1{d(n)}\right).$ So $\sqrt{d(n)}\le 1+\frac12+\dots+\frac1{d(n)}.$ If $d(n)=9$ , this doesn't work(the RHS is a bit less than $3$ ). Then, the LHS grows faster than the RHS when $d(n)>9$ , because $\sqrt{d(n)+1}-\sqrt{d(n)}=\frac{1}{\sqrt{d(n)+1}+\sqrt{d(n)}}\ge\frac{1}{2\sqrt{d(n)+1}}\ge\frac{1}{d(n)+1}.$ So, $d(n)\le 8$ .

If $d(n)\in\{2,3,5,7\}$ , the grid has exactly one row, which clearly doesn't work because the sum of column 1 cannot equal the sum of column 2. If $d(n)\in\{4,6,8\}$ , then the grid must have exactly two rows. Let $n$ be in the top left cell. Then the sum of column $2$ is at least $n+1$ , so there must be at least one number greater than or equal to $\frac{n+1}{2}$ in column 2, absurd. Finally, if $d(n)=1$ , we must have $n=1$ , which clearly works.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

577 posts

#36 h Apr 19, 2023, 3:34 PM

Y by

Suppose the grid has $a$ rows and $b$ columns, and WLOG $a \ge b$ . Then $ab=\tau(n)$ , from which $a \ge \sqrt{\tau(n)}$ . This induces the bound $\sqrt{\tau(n)} \ge \frac{\sigma(n)}{n}.$ In light of the above inequality, define $f(n) := \frac{n^2\tau(n)}{\sigma(n)^2},$ where we want solutions in integers to $f(n) \le 1$ . The key to finding these solutions is to recognize the multiplicative nature of $f$ , so we examine $f(p^k)$ for prime $p$ . One can write $f(p^k) = \frac{p^{2k+2}(k+1)}{(p^{k+1}-1)^2} \cdot \left(\frac{p-1}{p}\right)^2 > (k+1)\left(\frac{p-1}{p}\right)^2.$ Thus if $f(p^k) \le 1$ , then $(k+1)\left(\tfrac{p-1}{p}\right)^2 \le 1$ . We test for $p=2, 3$ to find that $(p, k)$ has solutions $(2, 1), (2, 2), (2, 3), (3, 1)$ , but there are no solutions when $p \ge 5$ . Thus the only prime powers $m$ that yield $f(m) \le 1$ are $2, 3, 4, 8$ . As $f$ is multiplicative, solutions are of the form $2^a 3^b$ for $0\le a \le 6$ and $0\le b\le 1$ . We can check all possibilities for $n$ to find that $n=1, 2, 4, 6$ . We also check the grids for each value of $n$ , and find that $\boxed{n=1}$ is the only solution.

This post has been edited 2 times. Last edited by Leo.Euler, Apr 20, 2023, 2:39 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lian_the_noob12

173 posts

lian_the_noob12

#37 h Aug 3, 2023, 4:06 PM

Y by

$\color{magenta} \boxed{\textbf{SOLUTION C2}}$

Clearly $n=1$ is a solution

$\color{green} \textbf{CLAIM :}$ $n > 1$ doesn't satisfy the conditions

$\textbf{Proof :}$ Let $n>1$ and We have $a \times b$ rectangular grid with $a$ rows and $b$ columns

WLOG, $b=1$ and $a>b=1$ then we have $a$ rows and every row has just one divisor of $n$ But as all the divisors of $n$ are distinct so every row contains a different number which doesn't satisfy the condition

So, WLOG $a \ge b >1$ [If $b\ge a=1$ Just Consider Columns instead of Rows]
As $n$ is a divisor of $n$ it must lie in a row say $i-th$ row, Every row contains atleast $2$ numbers as $b>1$ So the sum of the numbers in $i-th$ row is, $S_{r_{i}} > n$ Consider the largest number in each row [The number of largest numbers is $a$ ] , and let $c_j$ be the minimum of the largest numbers which lies in $j-th$ row. $c_j$ is the $a-th$ largest divisor of $n$
So, $c_j \le \frac{n}{a}$
The sum of the numbers in $j-th$ row $S_{r_{j}} \le b \times \frac{n}{a} \le a\times \frac{n}{a} = n$ So, We get a row $j$ where the sum of the number is less than the sum of the numbers in row $i$
$\blacksquare$

This post has been edited 3 times. Last edited by lian_the_noob12, Aug 3, 2023, 4:10 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1500 posts

#38 h Sep 9, 2023, 2:11 AM • 1 Y

Y by Inconsistent

Never cook again.

We show that this is impossible for $n > 1$ .
Let the table be $a \times b$ for $a > b$ . Then the sum of the entry in each row is at least $n$ .
However, there are at most $b-1$ divisors of $n$ strictly greater than $\frac{n}{b}$ , so by pigeonhole some row must have all elements less than or equal to $\frac{n}{b}$ , contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7586 posts

#39 h Dec 3, 2023, 7:17 PM

Y by

I got the bounding solution guys (the bad one). RIP

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

132 posts

#40 h Oct 10, 2024, 11:56 PM

Y by

Note that the sum is always $>n$ because $n$ is a factor of $n.$ Consider a grid of proportions $a$ by $b.$ Note that a maximum of $a-1$ factors of $n$ are more than $\frac{n}{a},$ so we must have a row or column consisting of all numbers being $\leq \frac{n}{a},$ so we must have $a=b=1,$ otherwise known as the only working number is $n=1.\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3177 posts

#41 h Nov 3, 2024, 2:02 PM

Y by

The answer is $\boxed{1}$ , which clearly works. We will prove that $n>1$ fails. Suppose that there are $a$ columns and $b\ge a$ rows. For each of the $b$ rows, there must be at least one element that is $>\frac{n}{a}$ (the common sum is $>n$ ). There are not $b$ numbers greater than $\frac{n}{a}$ , since $b\ge a$ .

This post has been edited 1 time. Last edited by megahertz13, Nov 3, 2024, 2:04 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7586 posts

#42 h Dec 21, 2024, 4:41 PM

Y by

to be honest i've failed this problem several times previously so i had a vague memory of what the solution was.

Pretty sure the way I ordered the dimensions is not conventional, so: $a\times b$ means $a$ rows and $b$ columns.

Assume that the table has dimensions $a\times b$ , with $1<a\le b$ . The sum of each column's numbers is at least $n$ , so in each of the $b$ columns $a\times 1$ the largest divisor is more than $\frac{n}{a}$ , and is thus equal to $\frac{n}{d}$ for $1\le d\le a-1$ , with each $d$ being distinct across each of the $b$ columns. This is a contradiction.

Hence $a=1$ (the case we have not handled). In this case there can only be one factor, so $n=1$ . We are done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SimplisticFormulas

84 posts

SimplisticFormulas

#43 h Mar 21, 2025, 12:16 PM

Y by

Indeed, there is no such $n>1$ . We shall show that $n$ is greater than either the sum of an individual row or the sum of an individual column.
Let $n=p_1^{a_1} \cdot p_2^{a_2} \dots p_m^{a_m}$ be the prime factorisation of $n$ . Note that the sum of divisors is $B=\prod_{k=1}^{m} \frac{p^{a_k+1}-1}{p-1}$ and the number of divisors is $A=\prod_{k=1}^{m} (a_k+1)$ Let the table be $a \times b, a \ge b$ . Then $a \ge \sqrt{A}$ . Observe that the sum of one row is $\frac{B}{a} \le \frac{B}{A}$ . We claim that $\frac{B}{\sqrt{A}}<n$ . Indeed, note that
$\frac{B}{\sqrt{A}}<n$ $\iff \prod_{k=1}^m \frac{ \frac{p_k^{a_k+1}-1}{p-1} }{\prod_{k=1}^m (a_k +1)} \le \prod_{k=1}^m p_k^{a_k}$ Observe that
$\frac{p^{a_k+1}-1}{(p-1) \sqrt{a_k +1}} \le p_k^{a_k}$ $\iff 1 + \frac{1}{p_k} \le \sqrt{a_k +1}$ which is true except when $p=2, a=1$ , which is only a single term in the product. The remaining terms easily make up for this for, hence our assumption is true (to make this argument more formal, small cases till, say, $n=20$ may be verified).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

174 posts

#44 h Mar 22, 2025, 11:46 AM • 1 Y

Y by L13832

Storage

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a