Find all natural numbers $n$ such that $1+[\sqrt{2n}]~$ divides $2n$. ( For any real number $x$ , $[x]$ denotes the largest integer not exceeding $x$. )
Problem
Source: RMO 2018 P5
Tags: algebra, number theory, Divisibility
07.10.2018 14:29
I think the answer is \(n(n+1)/2\)
07.10.2018 14:36
In the exam, I did the problem like this : Let $k\leq \sqrt{2n}<k+1$ so that $[\sqrt{2n}]=k$. Also, we have $k^2\leq 2n<(k+1)^2$ Observation : $k+1~\vert~(k+1)(k-1)=k^2-1<2n$ Trivially, the next two integers divisible by $(k+1)$ are $(k^2-1)+(k+1)=k(k+1)$ $$\text{and}$$ $(k^2-1)+2(k+1)=(k+1)^2$ From here, it is clear that the only possible value that can be taken by $2n$ is $k(k+1)$. Therefore, the set of solutions for $n$ is the triangular numbers, i.e. $$\bigg\{\frac{k(k+1)}{2}~:k\in\mathbb{N}\bigg\}$$
07.10.2018 14:55
I got $n=2k^2+k,n=2k^2+3k+1\quad\forall k\in\Bbb W$. Together the two forms give all numbers of the form $\frac{k(k+1)}2$. How many marks will be cut for this?
07.10.2018 16:02
Let $k^2 \le 2n < (k + 1)^2$. So, $\lfloor \sqrt{2n}\rfloor = k$. Let $l = 2n - k^2$. Note that $l \in [0, (n+1)^2 - n^2) = [0, 2n]$ We have to find all $n$ such that \[\frac{k^2 + l}{k + 1} = k - 1 + \frac{l + 1}{k + 1} \in \mathbb{Z}^+\]If $l + 1 = k + 1$, $n = \tfrac12 k(k+1)$. If $\tfrac{l + 1}{k + 1} \ge 2$, $2(k + 1) \le l + 1 \le 2k + 1 \implies 0 \ge 1$, a contradiction.
07.10.2018 16:14
07.10.2018 16:14
Let $\lfloor \sqrt{2n}\rfloor = k$ or $k^2\leq 2n<(k+1)^2$. Let $2n - k^2 = m$. We have \[\frac{k^2+m}{k+1}\]is integer or \[\frac{k^2-1+m+1}{k+1} = k- 1 +\frac{m+1}{k+1}\]is integer.. Notice that $0\leq m+1 <2k+2$. Thus $m+1 = k+1$ or $n = \frac{1}{2}\cdot k\cdot (k+1)$ (triangular numbers).
07.10.2018 16:40
integrated_JRC wrote: In the exam, I did the problem like this : Let $k\leq \sqrt{2n}<k+1$ so that $[\sqrt{2n}]=k$. Also, we have $k^2\leq 2n<(k+1)^2$ Observation : $k+1~\vert~(k+1)(k-1)=k^2-1$ Trivially, the next two integers divisible by $(k+1)$ are $(k^2-1)+(k+1)=k(k+1)$ $$\text{and}$$ $(k^2-1)+2(k+1)=(k+1)^2$ From here, it is clear that the only possible value that can be taken by $2n$ is $k(k+1)$. Therefore, the set of solutions for $n$ is the triangular numbers, i.e. $$\bigg\{\frac{k(k+1)}{2}~:k\in\mathbb{N}\bigg\}$$ I think $k$ belongs to the set of odd natural numbers. if $k $ is even then $1 + [2n] = 1+k$ will be odd while 2n will be even.
07.10.2018 16:55
Arhaan wrote: integrated_JRC wrote: In the exam, I did the problem like this : Let $k\leq \sqrt{2n}<k+1$ so that $[\sqrt{2n}]=k$. Also, we have $k^2\leq 2n<(k+1)^2$ Observation : $k+1~\vert~(k+1)(k-1)=k^2-1$ Trivially, the next two integers divisible by $(k+1)$ are $(k^2-1)+(k+1)=k(k+1)$ $$\text{and}$$ $(k^2-1)+2(k+1)=(k+1)^2$ From here, it is clear that the only possible value that can be taken by $2n$ is $k(k+1)$. Therefore, the set of solutions for $n$ is the triangular numbers, i.e. $$\bigg\{\frac{k(k+1)}{2}~:k\in\mathbb{N}\bigg\}$$ I think $k$ belongs to the set of odd natural numbers. if $k $ is even then $1 + [2n] = 1+k$ will be odd while 2n will be even. You mean an odd number cannot divide an even number?
07.10.2018 17:05
DynamoBlaze wrote: Arhaan wrote: integrated_JRC wrote: In the exam, I did the problem like this : Let $k\leq \sqrt{2n}<k+1$ so that $[\sqrt{2n}]=k$. Also, we have $k^2\leq 2n<(k+1)^2$ Observation : $k+1~\vert~(k+1)(k-1)=k^2-1$ Trivially, the next two integers divisible by $(k+1)$ are $(k^2-1)+(k+1)=k(k+1)$ $$\text{and}$$ $(k^2-1)+2(k+1)=(k+1)^2$ From here, it is clear that the only possible value that can be taken by $2n$ is $k(k+1)$. Therefore, the set of solutions for $n$ is the triangular numbers, i.e. $$\bigg\{\frac{k(k+1)}{2}~:k\in\mathbb{N}\bigg\}$$ I think $k$ belongs to the set of odd natural numbers. if $k $ is even then $1 + [2n] = 1+k$ will be odd while 2n will be even. You mean an odd number cannot divide an even number? Yeah you are right. I found my mistake. Btw, how many marks can i expect if I just made this error in the question.
07.10.2018 17:43
I proved by mathematical induction that the numbers of the form $\dfrac{(n)(n+1)}{2}$ satisfy the given condition.
07.10.2018 18:05
Iceberry25 wrote: I proved by mathematical induction that the numbers of the form $\dfrac{(n)(n^2+1)}{2}$ satisfy the given condition. How do you then show that only such numbers satisfy the condition?
07.10.2018 19:59
Iceberry25 wrote: I proved by mathematical induction that the numbers of the form $\dfrac{(n)(nn+1)}{2}$ satisfy the given condition. And it is n(n+1)/2
08.10.2018 15:10
Let $2n = m(1+\lfloor \sqrt{2n} \rfloor)$ for some natural number $m$. Then $$ \sqrt{2n}-1 < \frac{2n}{1+\sqrt{2n}}\leq m = \frac{2n}{1+\lfloor \sqrt{2n} \rfloor} \leq \frac{2n}{\sqrt{2n}} = \sqrt{2n}$$ so by definition of greatest integer function, we get $$m = \lfloor \sqrt{2n} \rfloor$$Thus $2n = m(m+1)$ or $n$ is a triangular number. Indeed, all triangular numbers work.
08.10.2018 16:09
My method is a bit cumbersome, but I arrived at a different answer (the following solution is one of the four cases that I considered and did in the exam). Plz correct me if I am wrong.
09.10.2018 15:03
TheDarkPrince wrote: Iceberry25 wrote: I proved by mathematical induction that the numbers of the form $\dfrac{(n)(n^2+1)}{2}$ satisfy the given condition. How do you then show that only such numbers satisfy the condition? Ah, correct. Forgot. Nevermind :/ Edit: No, the question asks to find the numbers. They are the only numbers, and I found them.
09.10.2018 15:41
Iceberry25 wrote: TheDarkPrince wrote: Iceberry25 wrote: I proved by mathematical induction that the numbers of the form $\dfrac{(n)(n+1)}{2}$ satisfy the given condition. How do you then show that only such numbers satisfy the condition? Ah, correct. Forgot. Nevermind :/ Edit: No, the question asks to find the numbers. They are the only numbers, and I found them. No you are supposed to find all numbers that satisfy the given condition. You proved that these work but you didn't prove that others don't. DynamoBlaze wrote: I got $n=2k^2+k,n=2k^2+3k+1\quad\forall k\in\Bbb W$. Together the two forms give all numbers of the form $\frac{k(k+1)}2$. How many marks will be cut for this? Don't worry I did a similar thing (I wrote the answer as $k(2k+1)$ and $k(2k-1)$ form, which together give the required answer; although in the end I had written that this is the set of triangular numbers $1,3,6,10, \dots$). I don't think they would cut marks for that (even if they do, they won't cut more than 2 or 3, if everything else is correct).
19.10.2018 15:55
Math.Is.Beautiful wrote: My method is a bit cumbersome, but I arrived at a different answer (the following solution is one of the four cases that I considered and did in the exam). Plz correct me if I am wrong.
Someone plz check this.
26.01.2019 16:51
DynamoBlaze wrote: I got $n=2k^2+k,n=2k^2+3k+1\quad\forall k\in\Bbb W$. Together the two forms give all numbers of the form $\frac{k(k+1)}2$. How many marks will be cut for this? Your solution is correct enough. I dont think they have cut any marks for it
15.08.2019 13:20
Let $k^2\leq 2n<(k+1)^2$ Then, $[\sqrt{2n}]=k$ $k+1|2n$ Let $2n=m(k+1)$ $k^2\leq m(k+1)<(k+1)^2$ $k^2-1<m(k+1)<(k+1)^2$ $k-1<m<k+1$ $m=k$ $2n=m(k+1)$ $n=\frac{k(k+1)}{2}$ QED, and the second easiest problem of RMO 2018 acc. to me Thanks @below
15.08.2019 13:52
^ Kindly ensure that you do not confuse between your variables. Also, it is always good to make sure you do the problem both ways. Here, you proved that any number that works must be triangular. Put you should spare an extra line to show that all triangular numbers do work. P.S. It is not the second easiest(acc to me ofc). All problems except 4 were of the same difficulty (and all easy !)
15.08.2019 14:08
e_plus_pi wrote: ^ Kindly ensure that you do not confuse between your variables. Also, it is always good to make sure you do the problem both ways. Here, you proved that any number that works must be triangular. Put you should spare an extra line to show that all triangular numbers do work. Oops! I meant $k$ in the final line sorry. BTW why do we need to prove all triangular numbers work? $k$ is obviously a positive integer, so any k will work
02.11.2020 20:18
We claim all solutions are in the form $n = \frac{k(k+1)}{2}$ for $k \geq 1.$ Let $2n = k^2+m$ for $0 \leq m < 2k+1$. Then, we need $k+1 | k^2+m,$ or $k-1+\frac{m+1}{k+1}$ to be integral. We claim $m=k$ is the only solution. Notice that $2k+2=2(k+1)>m+1 \geq 0,$ so $m=k$ is only solution. Therefore, $m=k$ and all solutions are in the form $2n=k^2+k,$ or $n = \frac{k(k+1)}{2}.$
28.03.2021 10:43
$2n = x^2 + r$ such that $0 \le r < 2x + 1$ $\implies \lfloor \sqrt{2n} \rfloor = x$ $1 + x \mid x^2 + r$ $\implies 1 + x \mid r - x$ $\implies r-x = 0$ or $r-x \ge x + 1 \iff r \ge 2x + 1$ But the 2nd case is not possible. $\implies r = x \implies 2n = x^2 + x \implies \boxed{n = \frac{x(x+1)}{2}} \ \blacksquare$
28.03.2021 12:03
MrOreoJuice wrote: $2n = x^2 + r$ such that $0 \le r < 2x + 1$ $\implies \lfloor \sqrt{2n} \rfloor = x$ $1 + x \mid x^2 + r$ $\implies 1 + x \mid r - x$ $\implies r-x = 0$ or $r-x \ge x + 1 \iff r \ge 2x + 1$ But the 2nd case is not possible. $\implies r = x \implies 2n = x^2 + x \implies \boxed{n = \frac{x(x+1)}{2}} \ \blacksquare$ This was similar to an APMO problem. There were floor functions all around, and I saw that problem earlier, so this was a piece of cake. These substitutions are quite stanadard in floor function problems I guess. I did the same substitutions. And problem had quite a sharp bound as well, so yeah!
25.04.2024 05:30
we set $a:=\sqrt{2n}$ so problem statement transfers to: $\frac{a^2}{1+\lfloor a \rfloor} \in \mathbb{N}$ We notice $a<1+\lfloor a \rfloor \leqslant a+1 \implies a> \frac{a^2}{1+\lfloor a \rfloor} \geqslant \frac{a^2}{a+1}=(a-1)+\frac{1}{a+1}>a-1$ so the integer between $a$ and $a-1$ is $\lfloor a \rfloor$ we get $\frac{a^2}{1+\lfloor a \rfloor} =\lfloor a \rfloor \implies a^2=\lfloor a \rfloor +(\lfloor a \rfloor)^2$ , we set $\lfloor a \rfloor:=k \implies k \leqslant a< k+1 \implies a^2=k+k^2 \implies 2n=k+k^2 \implies n=\frac{k(k+1)}{2}$ hence all that $n$ that works are precisely the set of all triangular numbers. $\square$
17.09.2024 18:41
Claim 1: All triangular numbers satisfy the given criteria. Proof: Let $n=\frac{k(k+1)}{2}$ ($k\in \mathbb{N}$). The proposition simply becomes $1+k|k(k+1)$, which is trivially true. Claim 2: No $n$ which is not a triangular number works. Proof Let $n=\frac{k^2+p}{2}$, where $k,p\in \mathbb{N}$, such that $p<2k+1$ and $p\neq k$. $FTSOC$, the proposition becomes, $1+k|k^2+p \implies 1+k|p-k$. But $|p-k|<|k+1|$. This is a contradiction. Thus $n= \frac{k(k+1)}{2}$. ($k\in \mathbb{N}$)
01.11.2024 16:15
MrOreoJuice wrote: $2n = x^2 + r$ such that $0 \le r < 2x + 1$ $\implies \lfloor \sqrt{2n} \rfloor = x$ $1 + x \mid x^2 + r$ $\implies 1 + x \mid r - x$ $\implies r-x = 0$ or $r-x \ge x + 1 \iff r \ge 2x + 1$ But the 2nd case is not possible. $\implies r = x \implies 2n = x^2 + x \implies \boxed{n = \frac{x(x+1)}{2}} \ \blacksquare$ yes, I have the same sol! Idk why the official sol is so hella complicated