Floor double summation

The post below has been deleted. Click to close.

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

CyclicISLscelesTrapezoid

372 posts

CyclicISLscelesTrapezoid

#1 h Jul 12, 2022, 12:52 PM • 6 Y

Y by PRMOisTheHardestExam, Stuart111, crazyeyemoody907, deplasmanyollari, cubres, Funcshun840

Which positive integers $n$ make the equation $\sum_{i=1}^n \sum_{j=1}^n \left\lfloor \frac{ij}{n+1} \right\rfloor=\frac{n^2(n-1)}{4}$ true?

Z K Y

The post below has been deleted. Click to close.

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

Orestis_Lignos

558 posts

Orestis_Lignos

#2 h Jul 12, 2022, 12:59 PM • 2 Y

Y by Stuart111, cubres

The answer is all $n$ such that $n+1$ is prime. Note that if $n$ works, then $4 \mid n^2(n-1)$ , hence $n$ is even or $\equiv 1 \pmod 4$ . We examine the two cases:

Case 1: $n$ is even. Call a pair $(i,j)$ good if $n \mid ij$ and bad otherwise. Noe that we may organize the $n^2$ entries of the board in pairs of $4$ , as follows:

$\lfloor \frac{ij}{n+1} \rfloor, \lfloor \frac{(n+1-i)j}{n+1} \rfloor, \lfloor \frac{i(n+1-j)}{n+1} \rfloor, \lfloor \frac{(n+1-i)(n+1-j)}{n+1} \rfloor$

(note that each pair $(i,j)$ is counted $4$ times)

It can easily be checked that the sum of all numbers in each group is either $n+1$ (if $(i,j)$ is good) or $n-1$ (if $(i,j)$ is bad) -- just notice that the sum of every two numbers in the floors is an integer.

Hence, the total sum of the entries is $\frac{(n+1)x+(n-1)y}{4}$ , with $x$ being the number of good pairs and $y$ being that of the bad pairs. It is clear that $x+y=n^2$ . According to the problem statement,

$(n+1)x+(n-1)y=n^2(n-1)=(n-1)(x+y)$ , and so $x=0$ , i.e. all pairs $(i,j)$ are bad. If $n+1$ is not prime, let $n+1=ab$ with $a,b >1$ , and so the pair $(a,b)$ is good, a contradiction. However, if $n+1$ is prime, then $n+1 \mid ij$ implies $n+1 \mid i$ or $n+1 \mid j$ , both absurd since $1 \leq i,j \leq n$ .

Case 2: $n \equiv 1 \pmod 4$ . We will use the very same idea, but a bit more carefully, since now there might be some internal overlap in the groups we formed before (precisely in the $i=(n+1)/2$ or $j=(n+1)/2$ case).

Call a pair $(i,j)$ good if $i,j \neq (n+1)/2$ and $(n+1) \mid ij$ and bad if $i,j \neq (n+1)/2$ and $(n+1) \nmid ij$ . It is clear that $x+y=(n-1)^2$ , where $x$ and $y$ denote the number of good and bad pairs, respectively.

By the same idea as above, the sum of all entries of the board that do not belong in the middle row or column is

$\frac{(n+1)x+(n-1)y}{4}$ .

In order to deal with the remaining entries, we note that $\lfloor \frac{((n+1)/2)i}{n+1} \rfloor$ takes the values $0,1,1,2,2,\ldots,(n-1)/2,(n-1)/2$ when $i$ runs from $1$ to $n$ , and so the sum of the entries that belong in the middle row or column is

$2(1+1+2+2+\ldots+(n-1)/2+(n-1)/2)-(n-1)/4=(n^2-1)/2-(n-1)/4=(2n^2-n-1)/4$

Hence, $\frac{(n+1)x+(n-1)y}{4}+\frac{2n^2-n-1}{4}=\frac{n^3-n^2}{4}$ , and so

$(n+1)x+(n-1)y=n^3-3n^2+n+1$ . Moreover, $x+y=(n-1)^2,$ and so

$(n-1)^3=(n-1)x+(n-1)y\leq (n+1)x+(n-1)y=n^3-3n^2+n+1<n^3-3n^2+3n-1=(n-1)^3,$

a contradiction.

Thus, all solutions are $n=p-1$ where $p$ is prime.

Z K Y

The post below has been deleted. Click to close.

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

gghx

1072 posts

gghx

#3 h Jul 12, 2022, 1:00 PM • 19 Y

Y by David-Vieta, carefully, Supercali, Quidditch, gvole, Kimchiks926, bjump, ljxlapin, PNT, Tellocan, Dhruv777, sabkx, Mango247, aidan0626, Infinityfun, Sedro, Lhaj3, NurJyJa, cubres

When you realise A2 is a better N2 and N2 is a better A2 ...

Z K Y

The post below has been deleted. Click to close.

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

Quidditch

818 posts

Quidditch

#4 h Jul 12, 2022, 1:00 PM • 2 Y

Y by Mango247, cubres

This problem use the same idea from Baltic Way 2001… It’s basically the same but with some change.

https://artofproblemsolving.com/community/c6h378171p2089076

This post has been edited 2 times. Last edited by Quidditch, Jul 12, 2022, 1:01 PM

Z K Y

The post below has been deleted. Click to close.

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

v_Enhance

6878 posts

v_Enhance

#5 h Jul 12, 2022, 1:03 PM • 30 Y

Y by David-Vieta, HamstPan38825, W.R.O.N.G, IAmTheHazard, thinker123, JG666, PRMOisTheHardestExam, PHSH, crazyeyemoody907, bjump, a22886, userr.7, honey_lemon, ljxlapin, Mathlover_1, somebodyyouusedtoknow, mathmax12, sabkx, kamatadu, aidan0626, Stuffybear, cliid, L.M., Math_legendno12, chenghaohu, Sedro, kiyoras_2001, EpicBird08, cubres, Funcshun840

The answer is $n+1$ prime.
Because $\sum_{i=1}^n \sum_{j=1}^n \frac{ij}{n+1} = \frac{1}{n+1} \left( 1+2+\dots+n \right)^2 = \frac{n^2(n+1)}{4}$ the equation is equivalent to $\sum_{i=1}^n \sum_{j=1}^n \left\{ \frac{ij}{n+1} \right\} = \frac{n^2}{2} \qquad (\clubsuit)$ where $\{ x \}$ is the fractional part of $x$ .
Now $\left\{ \frac{ij}{n+1} \right\} + \left\{ \frac{i(n+1-j)}{n+1} \right\} = \begin{cases} 1 & n+1 \nmid ij \\ 0 & \text{otherwise}. \end{cases}$ So by pairing up terms, we find $(\clubsuit)$ is true only when the $0$ case never occurs. Thus $n$ works exactly if $n+1$ is not the product of two smaller positive integers, i.e. is prime.

Z K Y

The post below has been deleted. Click to close.

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

adj0109

17 posts

adj0109

#6 h Jul 12, 2022, 1:05 PM • 2 Y

Y by mathmax12, cubres

The answer is $n = p-1$ for all $p$ prime

We do pairing. Notice that, $\left \lfloor \frac{i j}{n+1} \right \rfloor + \left \lfloor \frac{i (n + 1 - j)}{n+1} \right \rfloor \geq \frac{i j}{n+1} + \frac{i (n + 1 - j)}{n+1} - 1 = i - 1$
Where equality occurs when $n + 1 \nmid i j$ .

Summing up all the entries: $\sum_{i = 1}^{n} \sum_{j = 1}^{n} \left \lfloor \frac{i j}{n+1} \right \rfloor \geq \sum_{i = 1}^{n} \left (\frac{n}{2} \cdot (i - 1) \right ) = \frac{n^2(n-1)}{4}$
So, we want $n + 1 \nmid i j \: \forall \: 1 \leq i,j \leq n$ . This obviously happens if $n+1$ is prime. Otherwise, let $n+1 = ab$ and take $i = a$ and $j = b$ .

This post has been edited 1 time. Last edited by adj0109, Jul 12, 2022, 1:41 PM

Z K Y

The post below has been deleted. Click to close.

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

Assassino9931

1374 posts

Assassino9931

#7 h Jul 12, 2022, 1:06 PM • 3 Y

Y by Alfombra12, RecursiveCo, cubres

Just like gghx, I feel like this problem (which is really number theory) and N2 (which is really algebra) should be interchanged in the Shortlist!

Rewrite the condition as $\sum_{i=0}^{m-1}\sum_{j=0}^{m-1}\left\lfloor \frac{ij}{m} \right\rfloor = \frac{(m-1)^2(m-2)}{4}$ where $m = n + 1 \geq 2$ . Since $\sum_{i=0}^{m-1}\sum_{j=0}^{m-1}ij = (\sum_{k=0}^{m-1}k)^2 = \frac{m^2(m-1)^2}{4}$ , the condition is equivalent to $\sum_{i=1}^{m-1}\sum_{j=0}^{m-1} [ij \pmod m] = \frac{m(m-1)^2}{2}$ . Now trying the first few $m$ suggest that only primes would work.

Indeed, if $m$ is coprime with a fixed $i$ , then for a fixed $i$ , the numbers $ij \pmod m$ , $j=0,1,\ldots,m-1$ are all distinct (if $ij_1 \equiv ij_2 \pmod m$ , then $m \mid i(j_1-j_2)$ , $i$ and $m$ are coprime and so $j_1\equiv j_2 \pmod m$ ) and since they are $m$ in number, they must be $0$ , $1$ , $\ldots$ , $m-1$ in some order. So the contribution of such an $i$ is $1 + 2 + \cdots + m-1 = \frac{m(m-1)}{2}$ .

More generally, it follows that if gcd $(i,m) = d_i$ , then replacing $i$ and $m$ with $i/d_i$ and $m/d_i$ in the above argument yields $\sum_{j=0}^{m-1} ij \pmod m = d_i\sum_{j=1}^{m} \frac{i}{d_i} j \pmod {\frac{m}{d_i}} = d_i^2\sum_{j=1}^{m/d_i} \frac{i}{d_i} j \pmod {\frac{m}{d_i}} = d_i^2 \frac{\frac{m}{d_i}(\frac{m}{d_i}-1)}{2} = \frac{m(m-d_i)}{2}$ . Overall, $\sum_{i=1}^{m-1}\sum_{j=0}^{m-1}ij \pmod m = \sum_{i=1}^{m-1} \frac{m(m-\mbox{\scriptsize gcd}(i,m))}{2}$ . Each summand is at most $\frac{m(m-1)}{2}$ and the number of summands is $m-1$ , so the condition requires equality to hold. But this occurs if and only if gcd $(i,m) = 1$ for all $i=1,2,\ldots,m-1$ which is equivalent to $m$ being prime.

Therefore all working $n$ are of the form $p-1$ , where $p$ is any prime.

Z K Y

The post below has been deleted. Click to close.

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

isaacmeng

113 posts

isaacmeng

#8 h Jul 12, 2022, 1:11 PM • 1 Y

Y by cubres

ISL 2021 A2. For every $n\in\mathbb Z_+$ consider the $n\times n$ table with entry $\left\lfloor\frac{ij}{n+1}\right\rfloor$ at the intersection of row $i$ and column $j$ , for every $i=1, \dots, n$ and $j=1, \dots, n$ . Determine all $n\in\mathbb Z_+$ for which the sum of the $n^2$ entries in the table is equal to $\frac14n^2(n-1)$ .

Solution. All such integers $n$ are those of the form $n=p-1$ , where $p$ is a prime. Define $\begin{align*}f(n)&=\sum_{i, j=1}^n\left\lfloor\frac{ij}{n+1}\right\rfloor,\\g(n)&=\frac14n^2(n-1),\\\overline f(n)&=\sum_{i, j=1}^n\frac{ij}{n+1}=\frac1{n+1}\sum_{i=1}^n\left(i\sum_{j=1}^nj\right)=\frac14n^2(n+1),\\ [a]_b&\text{ to be the integer such that a}\equiv [a]_b\pmod b\text{ and }0\le[a]_b<b,\\\tilde f(n)&=\sum_{i, j=1}^n\left\{\frac{ij}{n+1}\right\}=\sum_{i, j=1}^n\frac{[ij]_{n+1}}{n+1}.\end{align*}$ Observe that $\overline f(n)=f(n)+\tilde f(n)$ , so $f(n)=g(n)\iff\tilde f(n)=\overline f(n)-g(n)=\frac12n^2.$ Now it is well-known that $\{1, \dots, n\}=k\{1, \dots, n\}$ for any $\gcd(k, n+1)=1$ . Hence $\tilde f(p-1)=\frac1p\sum_{i, j=1}^{p-1}[ij]_p=\frac1p(p-1)\sum_{j=1}^{p-1}j=\frac12(p-1)^2.$ Therefore all integers of the form $n=p-1$ satisfy the problem condition. On the other hand, if $n$ is not of this form then choose a prime $p\mid n+1$ but $p<n+1$ . Claim that $\sum_{j=1}^n[kpj]_{n+1}<\frac{n(n+1)}2$ for all $k\in\mathbb Z_+$ . In fact, all the residues $[kpj]_{n+1}$ are multiples of $p$ , and they are $p, 2p, 3p, \dots, \left(\frac{n+1}p-1\right)p, 0, p, 2p, 3p, \dots, \left(\frac{n+1}p-1\right)p, 0, \dots$ . Thus the sum is just $p\sum_{r=1}^{\frac{n+1}p-1}rp=p^2\left(\frac{\left(\frac{n+1}p-1\right)\left(\frac{n+1}p\right)}2\right)=\frac12(n+1-p)(n+1)<\frac12n(n+1),$ as desired. Therefore $\begin{align*}\tilde f(n)&=\frac1{n+1}\sum_{i, j=1}^n[ij]_{n+1}\\&=\frac1{n+1}\left(\sum_{\substack{1\le i, j\le n\\\gcd(i, n+1)\ne 1}}[ij]_{n+1}+\sum_{\substack{1\le i, j\le n\\\gcd(i, n+1)=1}}[ij]_{n+1}\right)\\&<\frac1{n+1}\left((n-\phi(n+1))\frac12n(n+1)+\sum_{\substack{1\le i, j\le n\\\gcd(i, n+1)=1}}[ij]_{n+1}\right)\\&=\frac1{n+1}\left((n-\phi(n+1))\frac12n(n+1)+\sum_{\substack{1\le i, j\le n\\\gcd(i, n+1)=1}}[j]_{n+1}\right)\\&=\frac1{n+1}\left((n-\phi(n+1))\frac12n(n+1)+\phi(n+1)\frac{n(n+1)}2\right)\\&=\frac1{n+1}\left(n\cdot\frac{n(n+1)}2\right)\\&=\frac12n^2.\end{align*}$ This suggests that all integers $n$ that are not of that form are not satisfying the problem condition, establishing the proof.

Z K Y

The post below has been deleted. Click to close.

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

DottedCaculator

7357 posts

DottedCaculator

#9 h Jul 12, 2022, 1:15 PM • 7 Y

Y by Iora, levifb, PNT, ESAOPS, Mango247, cubres, MS_asdfgzxcvb

We have
$\begin{align*} 2\sum_{i=1}^n\sum_{j=1}^n\left\lfloor\frac{ij}{n+1}\right\rfloor&=\sum_{i=1}^n\sum_{j=1}^n\left(\left\lfloor\frac{ij}{n+1}\right\rfloor+\left\lfloor\frac{i(n+1-j)}{n+1}\right\rfloor\right)\\ &\geq\sum_{i=1}^n\sum_{j=1}^n\left(\left\lfloor\frac{i(n+1)}{n+1}\right\rfloor-1\right)\\ &=\sum_{i=1}^n\sum_{j=1}^n(i-1)\\ &=\sum_{i=1}^nn(i-1)\\ &=\frac{(n-1)n^2}2. \end{align*}$ Therefore, the equation is true if and only if equality holds in all of the equation. This happens if and only if $\frac{ij}{n+1}$ is a noninteger for all $n+1$ , which happens if and only if $n+1$ is prime.

Z K Y

The post below has been deleted. Click to close.

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

vsamc

3789 posts

vsamc

#10 h Jul 13, 2022, 12:25 AM • 1 Y

Y by cubres

The answer is $n = p-1$ , where $p$ is a prime.

Let $n$ be a positive integer satisfying the inequality (there exists an $n$ since $n = 1$ can be easily seen to work). Note that $\sum_{i=1}^{n}\sum_{j=1}^{n}\left \lfloor \frac{ij}{n+1}\right \rfloor = \sum_{i=1}^{n}\sum_{j=1}^{n}\left(\frac{ij}{n+1} - \left \{\frac{ij}{n+1}\right \}\right) = \frac{1}{n+1}\sum_{i=1}^{n}\sum_{j=1}^{n}ij - \sum_{i=1}^{n}\sum_{j=1}^{n}\left \{\frac{ij}{n+1}\right \} = \frac{1}{n+1}\cdot (1 + 2 + \cdots + n)^2 - \sum_{i=1}^{n}\sum_{j=1}^{n}\left \{\frac{ij}{n+1}\right \} = \frac{1}{n+1}\left(\frac{n(n+1)}{2}\right)^2 - \sum_{i=1}^{n}\sum_{j=1}^{n}\left \{\frac{ij}{n+1}\right \} = \frac{n^2(n+1)}{4} - \sum_{i=1}^{n}\sum_{j=1}^{n}\left \{\frac{ij}{n+1}\right \}.$ Thus, we have $\sum_{i=1}^{n}\sum_{j=1}^{n}\left \{\frac{ij}{n+1}\right \} = \frac{n^2(n+1)}{4} - \frac{n^2(n-1)}{4} = \frac{n^2}{2}.$ Now, fix a $1\leq i\leq n$ , and let $g := \gcd(i, n+1)$ . Then, $\{i, 2i, \cdots, ni\}$ is a permutation of $\{g, 2g, \cdots, ng\}$ modulo $n+1$ (since $f(k) = \frac{i}{g}k$ is a bijection modulo $(n+1)/g$ ), so the sum for that particular $i$ is $\left \{\frac{0}{n+1}\right \} + \left \{\frac{g}{n+1}\right \} + \left \{\frac{2g}{n+1}\right \} + \cdots + \left \{\frac{ng}{n+1}\right \}.$ Since $f(k) = gk$ repeats after every $\frac{n+1}{g}$ (modulo $n+1$ ), and there are $g$ such blocks of repetition, we have that this is equal to $g\left(\left \{\frac{0}{n+1}\right \} + \left \{\frac{g}{n+1}\right \} + \cdots + \left \{ \frac{g\left(\frac{n+1}{g} - 1\right)}{n+1}\right \}\right) = \frac{g^2}{n+1}\left(0 + 1 + 2 + 3 + \cdots + \frac{n+1}{g}-1\right) = \frac{g^2}{n+1}\cdot \frac{\left(\frac{n+1}{g} - 1\right)\frac{n+1}{g}}{2} = \frac{n+1-g}{2} \leq \frac{n}{2},$ equality holding when $g = 1$ . Thus, summing over all $1\leq i\leq n$ , this is $\leq \frac{n}{2}\cdot n = \frac{n^2}{2}$ , equality holding when all $\gcd(i, n+1) = 1$ for all $1\leq i\leq n$ , i.e. $n+1$ is prime (if $n+1$ wasn't prime, take a prime divisor to get a non- $1$ gcd, and if $n+1$ is prime, than clearly everything less than $n+1$ is prime). However, the total sum is exactly $\frac{n^2}{2}$ , so equality must indeed hold everywhere, ergo $n+1$ is prime, as desired.

Z K Y

The post below has been deleted. Click to close.

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

VicKmath7

1391 posts

VicKmath7

#11 h Jul 13, 2022, 7:27 AM • 1 Y

Y by cubres

This is easier even than A1 in my opinion, the grouping idea is too classical. Otherwise, nothing new here, but this is more like a sketch.
Rewrite as $\sum \{ \frac{ij}{n+1}\} = \frac{n^2}{2}$ and group the terms $\{ \frac{ij}{n+1}\}+\{ \frac{i(n+1-j)}{n+1}\}$ and note that there sum is $1$ only if $n+1$ doesn't divide $ij$ and $0$ otherwise. Since zero can't appear, there are no numbers in $\{1,2,...,n\}$ divisible by $n+1$ , hence it's prime.

This post has been edited 2 times. Last edited by VicKmath7, Jul 13, 2022, 7:47 AM

Z K Y

The post below has been deleted. Click to close.

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

mango5

123 posts

mango5

#12 h Jul 13, 2022, 2:06 PM • 2 Y

Y by anirbanbz, cubres

The answer is all numbers that are one less than a prime.

First, the statement can be reduced algebraically: $\sum_{i=1}^n \sum_{j=1}^n \left\lfloor \frac{ij}{n+1} \right\rfloor + \sum_{i=1}^n \sum_{j=1}^n \left\{ \frac{ij}{n+1} \right\}=\sum_{i=1}^n \sum_{j=1}^n \frac{ij}{n+1}= \frac{(\sum_{m=1}^n m)^2}{n+1}=\frac{(\frac{n(n+1)}{2})^2}{n+1}=\frac{n^2(n+1)}{4}$ If $\sum_{i=1}^n \sum_{j=1}^n \left\lfloor \frac{ij}{n+1} \right\rfloor=\frac{n^2(n-1)}{4}$ then it remains to find $n$ such that $\sum_{i=1}^n \sum_{j=1}^n \left\{ \frac{ij}{n+1} \right\} = \frac{n^2(n+1)}{4} - \frac{n^2(n-1)}{4} = \frac{n^2}{4}\left((n+1)-(n-1)\right)=\frac{n^2}{2}.$ By pairing, the above is only false when $n+1 \mid ij$ for some pair(s) $(i, j)$ . Since $i$ and $j$ range from $1$ to $n$ , if $n+1$ were composite, it could be written as the product of two numbers less than it, which is covered in some pair $(i, j)$ . Otherwise, $n+1$ would be prime, and no pair would be divisible by it as $n+1$ is greater than all $i$ and $j$ . Therefore the answer is $n+1=p \Rightarrow \boxed{n=p-1}.$

Solved with a hint after the manipulation part, which was literally just "try finding the sol set".

This post has been edited 3 times. Last edited by mango5, Jul 13, 2022, 2:30 PM

Z K Y

The post below has been deleted. Click to close.

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

Hedra

110 posts

Hedra

#13 h Jul 13, 2022, 4:24 PM • 2 Y

Y by Mango247, cubres

Exactly same as v_Enhance's , Just posting for reference

Motivation?

Solution

Z K Y

The post below has been deleted. Click to close.

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

biomathematics

2568 posts

biomathematics

#14 h Jul 14, 2022, 3:19 PM • 2 Y

Y by Mango247, cubres

Fix $i$ . Since $\frac{ij}{n} + \frac{i(n+1-j)}{n} = i$ is an integer,
$\left \{ \frac{ij}{n+1} \right \} + \left \{ \frac{i(n+1-j)}{n+1} \right \} = \begin{cases} 0 & \text{ if } n+1 \mid ij \\ 1 & \text{otherwise.} \end{cases}$
Adding from $j=1$ to $n$ , we get
$2 \sum_{j=1}^n \left \{ \frac{ij}{n+1} \right \} = \text{ number of indices } j \text{ such that } (n+1) \nmid ij \implies \sum_{j=1}^n \left \{ \frac{ij}{n+1} \right \} \le \frac{n}{2}$
Adding over all $1 \le i \le n$ , we get
$\sum_{i=1}^n \sum_{j=1}^n \left \{ \frac{ij}{n+1} \right \} \le \frac{1}{2} \cdot n \cdot n = \frac{n^2}{2}$
Since
$\sum_{i=1}^n \sum_{j=1}^n \frac{ij}{n+1} = \frac{n(n+1)}{2} \cdot \frac{n(n+1)}{2} \cdot \frac{1}{n+1} = \frac{n^2(n+1)}{4},$ we get
$\sum_{i=1}^n \sum_{j=1}^n \left\lfloor \frac{ij}{n+1} \right\rfloor \ge \frac{n^2(n+1)}{4} - \frac{n^2}{2} = \frac{n^2(n-1)}{4}$
For equality, it must be the case that for all $1 \le i,j \le n$ , we have $(n+1) \nmid ij$ . Clearly, this is true if and only if $n+1$ is prime.

Z K Y

The post below has been deleted. Click to close.

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

Supercali

1261 posts

Supercali

#15 h Jul 14, 2022, 7:04 PM • 3 Y

Y by mango5, lahmacun, cubres

We will prove something stronger:
$\sum_{i=1}^n \sum_{j=1}^n \left\lfloor \frac{ij}{n+1} \right\rfloor=\frac{n^2(n-1)}{4} + \sum_{\substack{d \mid n+1 \\ d<n+1}} \left(\frac{d-1}{2} \right) \varphi \left(\frac{n+1}{d} \right)$ From the above it is evident that $n$ satisfies the given equation iff $n+1$ is prime.

To prove the identity, fix an $i<n+1$ , and let $d=\gcd(i,n+1)$ . Look at
$\sum_{j=1}^n \left\lfloor \frac{ij}{n+1} \right\rfloor = \sum_{j=1}^n \frac{ij}{n+1} - \sum_{j=1}^n \frac{r(ij)}{n+1}= \frac{in}{2}-\frac{1}{n+1}\sum_{j=1}^n r(ij)$ where $r(\cdot)$ is the remainder upon division by $n+1$ . Now, the numbers $i,2i, \dots ni, (n+1)i$ leave all possible remainders divisible by $d$ : In fact the remainders are $d, 2d \dots n+1-d,0$ in some order, repeated $d$ times (because $\frac{n+1}{d} \cdot i \equiv 0 \pmod{n+1}$ ). Now the final remainder is $0$ , so we can ignore it. The sum of all these remainders is then $d(d+2d+ \cdots (n+1-d))$ , which simplifies to $\frac{(n+1)(n+1-d)}{2}$ . Putting this in the above expression, we get
$\sum_{j=1}^n \left\lfloor \frac{ij}{n+1} \right\rfloor = (i-1)\frac{n}{2} +\frac{d-1}{2}$ Note that we must have $d<n+1$ , and the number of $i<n+1$ with $\gcd(i,n+1)=d$ is $\varphi \left(\frac{n+1}{d} \right)$ . Therefore summing over all $i$ gives us the required answer.

Z K Y

The post below has been deleted. Click to close.

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

mathmax12

6051 posts

mathmax12

#42 h Sep 14, 2023, 8:25 PM • 1 Y

Y by cubres

We claim that this is true if and only if $n+1,$ is prime.

Note, that $\sum_{i=1}^n \sum_{j=1}^n \frac{ij}{n+1}=\sum_{i=1}^n \frac{i(1+2+3+4+5+......+n)}{n+1}=\frac{(1+2+3+4+5+.....+n)^2}{n+1}=\frac{\frac{(n(n+1))^2}{4}}{n+1}=\frac{(n+1)\cdot n^2}{4}.$ Now, let $\left \{x\right\}=x-\lfloor x \rfloor$ note that $\sum_{i=1}^n \sum_{j=1}^n \left\{ \frac{ij}{n+1}\right\}=\frac{(n+1) \cdot n^2}{4}-\frac{(n-1)\cdot n^2}{4}=\frac{n^2}{2},$ next $\left\{\frac{ij}{n+1}\right\} + \left \{\frac{i(n+1-j)}{n+1}\right\},$ is $0$ if and only if $\frac{ij}{n+1}$ is an integer, but then contradicion so $n+1$ is prime.

This post has been edited 2 times. Last edited by mathmax12, Sep 14, 2023, 8:27 PM

Z K Y

The post below has been deleted. Click to close.

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

john0512

4191 posts

john0512

#43 h Nov 29, 2023, 4:28 AM • 1 Y

Y by cubres

The answer is when $n+1$ is prime. Multiply the equation by $n+1$ to get $\sum ij-\sum (ij\pmod{n+1})=\frac{n^2(n+1)(n-1)}{4}.$ Of course, we have $\sum ij = (\frac{n(n+1)}{2})^2,$ so this simply becomes $\sum (ij\pmod{n+1})=\frac{n^2(n+1)}{2}.$
Looking carefully at this statement, this is saying that the "average" residue in the multiplication table mod $n+1$ is $\frac{n+1}{2}$ , aka the average of all distinct nonzero residues. If $n+1$ is prime this is clearly true as each row contains each nonzero residue exactly once.

This "summing by row" method motivates the following claim:

\begin{claim}
Fix $i$ . Then, we have $\sum_{1\leq j\leq n}(ij\pmod{n+1})\leq n\times \frac{n+1}{2}$ with equality if and only if $i$ is relatively prime to $n+1$ .
\end{claim}

\begin{proof}
Every nonzero residue that is a multiple of $\gcd(i,n+1)$ shows up a $\gcd(i,n+1)$ times. Let this be $d$ . Then, the total sum is $d\times d(\frac{(\frac{n+1}{d}-1)(\frac{n+1}{d})}{2})=\frac{(n+1-d)(n+1)}{2}\leq \frac{n(n+1)}{2}$ with equality only when $d=1$ .
\end{proof}

Summing this over all $i$ , we get that all such $i$ need to be relatively prime to $n+1$ . Hence, $n+1$ must be prime.

This post has been edited 1 time. Last edited by john0512, Nov 29, 2023, 4:38 AM

Z K Y

The post below has been deleted. Click to close.

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

blackbluecar

303 posts

blackbluecar

#44 h Jan 10, 2024, 5:44 AM • 1 Y

Y by cubres

We note that $\frac{n^2(n-1)}{4} = \sum_{i=1}^n \sum_{j=1}^n \left\lfloor \frac{ij}{n+1} \right\rfloor = \sum_{i=1}^n \sum_{j=1}^n \frac{ij}{n+1} - \sum_{i=1}^n \sum_{j=1}^n\left \{ \frac{ij}{n+1} \right \}$ First, we have $\sum_{i=1}^n \sum_{j=1}^n \frac{ij}{n+1} = \sum_{i=1}^n \left ( \frac{i+2i+ \cdots +ni}{n+1} \right ) = \sum_{i=1}^n \frac{i}{n+1} \cdot \frac{n(n+1)}{2} = \sum_{i=1}^n \frac{in}{2} = \frac{n}{2} \cdot \frac{n(n+1)}{2} = \frac{n^2(n+1)}{4}$
Thus, $\frac{n^2(n-1)}{4} = \frac{n^2(n+1)}{4} - \sum_{i=1}^n \sum_{j=1}^n\left \{ \frac{ij}{n+1} \right \} \Longleftrightarrow \sum_{i=1}^n \sum_{j=1}^n\left \{ \frac{ij}{n+1} \right \} = \frac{n^2}{2}$
Claim: $\sum_{i=1}^n\left \{ \frac{ki}{n+1} \right \} \leq \frac{n}{2}$ with equality only at $\gcd(k,n+1)=1$ .

Assume $\gcd(k,n+1)=d$ . We note that $\sum_{i=1}^n \left \{ \frac{ki}{n+1} \right \} = d \cdot \sum_{i=1}^{\frac{n+1}{d}} \frac{i}{(n+1)/d} = \frac{n-d+1}{2} \leq \frac{n}{2}$ with obvious only equality case at $d=1$ as desired. $\square$

Since $\frac{n^2}{2} = \sum_{i=1}^n \sum_{j=1}^n\left \{ \frac{ij}{n+1} \right \} \leq n \cdot \frac{n}{2}$ which implies that equality holds for each inequality above. Thus, if $k < n+1$ then $\gcd(k,n+1)=1$ which is equivalent to $n+1$ being prime.

Z K Y

The post below has been deleted. Click to close.

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

Shreyasharma

684 posts

Shreyasharma

#47 h Feb 19, 2024, 12:08 AM • 1 Y

Y by cubres

The answer is $\boxed{n + 1 \text{ prime}}$ .

We cry. Split the double sum into integer and fractional parts so that we have,
$\begin{align*} \sum_{i = 1}^n \sum_{j = 1}^n \left\{ \frac{ij}{n+1} \right\} &= \sum_{i = 1}^n \sum_{j = 1}^n\left( \frac{ij}{n+1} \right) - \frac{n^2(n-1)}{4}\\ &= \sum_{i=1}^n \frac{n \cdot i}{2} - \frac{n^2(n-1)}{4}\\ &= \frac{n^2(n+1)}{4} - \frac{n^2(n - 1)}{4}\\ &= \frac{n^2}{2} \end{align*}$ Now interpret the fractional part thing as follows. We really just need,
$\begin{align*} \sum_{i=1}^n \sum_{j=1}^n (ij \bmod{n + 1}) &= \frac{n^2(n+1)}{2} \end{align*}$ Note that,
$\begin{align*} ij + i(n + 1 -j) \equiv 0 \pmod{n+1} \end{align*}$ For $n+1 \nmid ij$ we find that neither term is $0 \bmod n + 1$ and hence we have,
$\begin{align*} \left[ij \bmod{n+1}\right] + \left[i(n + 1 - j) \bmod{n+1}\right] = n + 1 \end{align*}$ for $n + 1 \nmid ij$ . Otherwise if $n + 1 \mid ij$ clearly both terms are individually $0$ so they contribute $0$ to the sum. Thus let us define,
$\begin{align*} f(i, j) = \begin{cases} n+1 & n+1 \nmid ij \\ 0 & n + 1 \mid ij \end{cases} \end{align*}$ Now our double sum then evaluates to,
$\begin{align*} \sum_{i=1}^n \sum_{j=1}^n (ij \bmod{n + 1}) = \sum_{(i, j)} f(i, j) \end{align*}$ Note then that,
$\begin{align*} \sum_{(i, j)} f(i, j) \leq \frac{n^2(n + 1)}{2} \end{align*}$ with equality if and only if every $(i, j)$ contributes $n + 1$ . This happens precisely when $n + 1 \mid ij$ never occurs. Thus we need the condition $n + 1$ prime as claimed.

Z K Y

The post below has been deleted. Click to close.

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

EpicBird08

1755 posts

EpicBird08

#48 h Mar 9, 2024, 4:36 AM • 1 Y

Y by cubres

We require that $n+1$ is a prime.

We first rewrite the equation as
$\sum_{i=1}^n \sum_{j=1}^n \left\{\frac{ij}{n+1}\right\} = \frac{n^2}{2}.$ Multiplying both sides by $n+1,$ if $f(k)$ is the remainder when $k$ is divided by $n+1,$ then we get
$\sum_{i=1}^n \sum_{j=1}^n f(ij) = \frac{n^2(n+1)}{2}.$ For a fixed $i,$ consider the sequence $0,i,2i,\dots,ni.$ If we let $\gcd(n+1,i) = d,$ then this sequence is just $d$ copies of $0,d,2d,\dots,n+1-d,$ each of which has sum $d \cdot \frac{\frac{n+1}{d} \cdot \left(\frac{n+1}{d} - 1\right)}{2},$ which gives
$\frac{(n+1)(n+1-d)}{2}.$ If we sum up over all $i,$ this becomes
$\frac{n+1}{2} \cdot \sum_{i=1}^n (n+1-\gcd(n+1,i)).$ Spliting the sum gives
$\frac{n+1}{2} \cdot (n(n+1) - \sum_{i=1}^n \gcd(n+1,i)).$ The sum on the right is at least equal to $n,$ so the entire sum is at most equal to
$\frac{n+1}{2} \cdot (n(n+1) - n) = \frac{n^2(n+1)}{2}.$ Equality is achieved if and only if all of the gcd's are equal to $1,$ which happens if and only if $n+1$ is prime.

Therefore, since all our steps are reversible, $n+1$ being prime is necessary and sufficient.

Z K Y

The post below has been deleted. Click to close.

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

trk08

614 posts

trk08

#49 h Mar 11, 2024, 2:30 AM • 1 Y

Y by cubres

We claim the answer is all $n$ such that $n+1$ is prime. To start, rewrite the equation as:
$\sum_{i,j=1}^{n}{\frac{ij}{n+1}}-\sum_{i,j=1}^{n}{\left\lfloor\frac{ij}{n+1}\right\rfloor}=\frac{n^2(n-1)}{4}$ $\frac{n^2(n+1)}{4}-\sum_{i,j=1}^{n}{\left\lfloor\frac{ij}{n+1}\right\rfloor}=\frac{n^2(n-1)}{4}$ $\sum_{i,j=1}^{n}{\left\lfloor\frac{ij}{n+1}\right\rfloor}=\frac{n^2}{2}.$
Lemma:
For constants $a,k$ , if $\gcd (a,k)=1$ , then $ab\pmod{k}$ contains all residues modulo $k$ for $b\in \{0,1,\dots,k-1\}$ .

Let $d_i=\gcd (n+1,i)$ . We make the following claim:
Claim:
$\sum_{i,j=1}^{n}{\left\lfloor\frac{ij}{n+1}\right\rfloor}=\frac{1}{n+1}\cdot\sum_{i=1}^{n}{\frac{(n+1)(n+1-d_i)}{2}}$ Proof:
For now, disregard the denominator of $n+1$ . This means we are looking at $ij \pmod{n+1}$ . Fix $i$ . To find the sum of the residues, such that $j\in S=\{0,1,\dots,n\}$ , we factor out $d_i$ . This results in the sum being:
$d_i\cdot \sum_{j\in S}{\frac{i}{d_i}\cdot j\pmod{\frac{n+1}{d_i}}}.$ Using our previous lemma, this is:
$d_i^2\cdot \frac{\left(\frac{n+1}{d_i}-1\right)\left(\frac{n+1}{d_i}\right)}{2}$ $\frac{(n+1)(n+1-d_i)}{2}\text{ }\square$
Summing over all $i$ , we get the sum being:
$\frac{1}{n+1}\sum_{i\in S}{\frac{(n+1)(n+1-d_i)}{2}}\leq \frac{1}{n+1}\sum_{i\in S}{\frac{(n+1)(n)}{2}}\leq \frac{n^2}{2},$ with equality occuring iff $d_i=1\text{ }\forall i\in S$ , implying that $n+1$ must be prime, as desired $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

Mr.Sharkman

501 posts

Mr.Sharkman

#50 h Apr 4, 2024, 5:39 PM • 1 Y

Y by cubres

Solution

Z K Y

The post below has been deleted. Click to close.

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

Sammy27

83 posts

Sammy27

#51 h Jul 7, 2024, 12:55 PM • 2 Y

Y by Eka01, cubres

Solution

Z K Y

The post below has been deleted. Click to close.

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

onyqz

195 posts

onyqz

#52 h Sep 26, 2024, 4:11 PM • 1 Y

Y by cubres

Quite easy actually
solution

Remark: Proving the identity was actually a problem, that appeared as a P6 in the German Federal Round just a few years ago.

Z K Y

The post below has been deleted. Click to close.

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

Maximilian113

575 posts

Maximilian113

#53 h Nov 28, 2024, 10:23 PM • 1 Y

Y by cubres

Just pairing lol
Note that $\sum_{i=1}^n \sum_{j=1}^n \frac{ij}{n+1} = \frac{1}{n+1} \cdot \left( \frac{n(n+1)}{2} \right)^2 = \frac{n^2(n+1)}{4}.$ Therefore, we just need to have $\sum_{i=1}^n \sum_{j=1}^n \left \{ \frac{ij}{n+1} \right \} = \frac{n^2}{2}.$ But this becomes $n^2 = 2\sum_{i=1}^n \sum_{j=1}^n \left \{ \frac{ij}{n+1} \right \} = \sum_{i=1}^n \sum_{j=1}^n \left(\left \{ \frac{ij}{n+1} \right \} + \left\{ \frac{(n+1-i)j}{n+1} \right \} \right) = \sum_{i=1}^n \sum_{j=1}^n \left( \left \{ \frac{ij}{n+1} \right \} + \left\{ \frac{-ij}{n+1} \right \} \right).$ There are $n^2$ of these terms in total, and note that if $\frac{ij}{n+1}$ was an integer, then clearly $\left \{ \frac{ij}{n+1} \right \} + \left\{ \frac{-ij}{n+1} \right \}$ becomes $0.$ Otherwise, it becomes $1.$ Hence, for $1 \leq i, j \leq n,$ $\frac{ij}{n+1}$ cannot be an integer. Clearly, if $n+1$ is prime this works, but if $n+1=mn$ for $m, n \geq 2$ then we can just let $(i, j) = (m, n),$ so $n+1$ cannot be composite. Hence, only $n$ such that $n+1$ is prime works.

Z K Y

The post below has been deleted. Click to close.

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

eg4334

636 posts

eg4334

#54 h Mar 2, 2025, 5:39 PM • 1 Y

Y by cubres

The only $n$ are when $\boxed{n+1 = p}$ is prime. First we tackle the case where $n$ is even. We can pair up the floors based on $i$ : $\begin{align*} S &= \sum_{i = 1}^{\frac{n}{2}} \sum_{j=1}^n \left( \lfloor \frac{ij}{n+1} \rfloor + \lfloor \frac{(n+1-i)j}{n+1} \rfloor \right) \\ &= \sum_{i=1}^{\frac{n}{2}} \sum_{j=1}^n \left( \frac{n(n+1)}{2} + \lfloor \frac{ij}{n+1} \rfloor + \lfloor - \frac{ij}{n+1} \rfloor \right) \\ &= \frac{n^2(n+1)}{4} + \sum_{i=1}^{\frac{n}{2}} \sum_{j=1}^n \left( \lfloor \frac{ij}{n+1} \rfloor + \lfloor - \frac{ij}{n+1} \rfloor \right) \end{align*}$ Notice that each sum of floors is $0$ when $\frac{ij}{n+1}$ is an integer and $-1$ otherwise. If all the terms are not integers, we get $\frac{n^2(n+1)}{4} - n \cdot \frac{n}{2} = \frac{n^2(n-1)}{4}$ , perfect. But this only happens when $n+1$ is prime obviouly. Otherwise, there must exist some $ij$ that is a multiple of $n+1$ , and our sum must be greater than the desired which is a contradiction.

Otherwise, $n \equiv 1 \pmod{4}$ . Then by an identical argument the minimum possible sum is $\frac{n(n+1)}{2} \cdot \frac{n-1}{2} + \frac{n^2-1}{4} - n \cdot \frac{n-1}{2} = \frac{n^3}{4} - \frac{n^2}{4} + \frac{n}{4} - \frac14$ which is too big and thus this case cannot happen. Therefore we have exhausted all cases and are done.

Z K Y

The post below has been deleted. Click to close.

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

Ilikeminecraft

667 posts

Ilikeminecraft

#55 h Mar 14, 2025, 8:12 PM • 1 Y

Y by cubres

very cool

Note that $\lfloor x \rfloor = x - \{x\}.$ Thus, we can rewrite our LHS as:
$\begin{align*} \sum_{i = 1}^n \sum_{j = 1}^n \left\lfloor \frac{ij}{n+1} \right\rfloor & = \sum_{i = 1}^n \sum_{j = 1}\frac{ij}{n + 1} - \left\{\frac{ij}{n+1} \right\} \\ & = \frac{n^2(n + 1)}{4} - \sum_{i = 1}^n \sum_{j = 1}^n \left\{\frac{ij}{n + 1}\right\} \end{align*}$ Now we do casework on if $n + 1$ is prime. If $n + 1$ is prime, it follows that each residue modulo $n + 1$ is covered in the sum exactly $n$ times. Thus, the sum simplifies to:
$\begin{align*} \frac{n^2(n + 1)}{4} - \sum_{i = 1}^n \sum_{j = 1}^n \left\{\frac{ij}{n + 1}\right\} & = \frac{n^2(n + 1)}{4} - n\cdot \sum_{j = 1}^n \frac j{n + 1} \\ & = \frac{n^2(n + 1)}{4} - \frac{n^2}2 \\ & = \frac{n^2(n - 1)}{4} \end{align*}$ Now, assunme that $n + 1$ is composite. It can be seen that at $(i, n + 1) = 1,$ we have that the sum is equivalent to $\frac{n}{2}.$ At $(i, n + 1) > 1,$ the sum is clearly less than $\frac n2$ . Thus, $n + 1$ composite doesn't work.

Z K Y

The post below has been deleted. Click to close.

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

cubres

119 posts

cubres

#56 h Apr 3, 2025, 10:47 AM

Y by

Yapping
Storage - grinding ISL problems

Z K Y

The post below has been deleted. Click to close.

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

lpieleanu

3007 posts

lpieleanu

#57 h Apr 23, 2025, 10:23 PM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

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

ezpotd

1303 posts

ezpotd

#59 h May 18, 2025, 9:47 PM

Y by

The answer is only $n + 1$ prime.

First, write each floor as $\frac{ij}{n + 1}- \frac{ij \mod n +1}{n+ 1}$ . Then summing gives $\frac{n^2(n + 1)}{2} - \sum_{i=1}^n \sum_{j =1}^n \frac{ij \mod n + 1}{n + 1}$ . Thus we want $\sum_{1 \le i,j \le n} ij \mod n = \frac 12 n^2 (n + 1)$ . When $n + 1$ is prime, we can pair $ij, i(n + 1 - j)$ to sum to $n + 1$ , and there are $\frac{n^2}{2}$ pairs of this form. However, when $n + 1$ is not prime, some of these pairs are guaranteed to have both elements equal to zero (pick any two numbers that multiply to $n + 1$ as $i,j$ ), which means that the corresponding sum will be less than the desired value, which finishes.

Z K Y