IMO Shortlist 2009 - Problem N4

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

IMO Shortlist 2009 - Problem N4

G H J

Reveal topic tags

modular arithmetic

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

1270 posts

April

#1 h Jul 5, 2010, 11:52 AM • 3 Y

Y by Amir Hossein, dien9c, Adventure10

Find all positive integers $n$ such that there exists a sequence of positive integers $a_1$ , $a_2$ , $\ldots$ , $a_n$ satisfying: $a_{k+1}=\frac{a_k^2+1}{a_{k-1}+1}-1$ for every $k$ with $2\leq k\leq n-1$ .

Proposed by North Korea

Z K Y

The post below has been deleted. Click to close.

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

5049 posts

Rust

#2 h Jul 5, 2010, 7:10 PM • 1 Y

Y by Adventure10

Let $b_k=a_{k-1}-a_k$ , then
${b_{k+1}=\frac{(b_k+2)a_k+b_k}{a_k+b_k+1}<b_k+2}$ .
Therefore if $a_1=N^2,a_2=N^2-1$ , then $a_3>N^2-2^2,a_4>N^2-3^2,...a_{N+1}>N^2-N^2=0.$

Z K Y

The post below has been deleted. Click to close.

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

2043 posts

Zhero

#3 h Jul 6, 2010, 8:48 PM • 6 Y

Y by Amir Hossein, nikgran, IFA, Adventure10, and 2 other users

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

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

366 posts

#4 h Apr 18, 2014, 6:26 PM • 4 Y

Y by Polynom_Efendi, Arshia.esl, Adventure10, Mango247

This is like a "troll" problem. Very simple, but it is stated in such a way that it tricks you into trying other stuff that doesn't work.

The answer is $4$ . It is easy to see that if there were $5$ , then we would have two even distinct numbers $n$ and $m$ (either $a_2$ and $a_3$ or $a_3$ and $a_4$ ) satisfying $n+1 | m^2+1$ and $m+1 | n^2+1$ . But this is impossible. To prove this, take the least two such numbers $n$ and $m$ (with $n+m$ minimal), and take $m'=(n^2+1)/(m+1)-1$ , with $m \textgreater n$ . It is easy to see $(n,m')$ also satisfies and that $m' \textless m$ . So we must have $m'=0$ so $n^2+1=m+1$ so $n^2=m$ , which is easy to discard. So the answer must be at most $4$ .

To find such a sequence of 4, one must prove a nontrivial ( $n^2 \neq m \neq \sqrt{n}$ , $n,m \ge 3$ ) solution to $n+1 | m^2+1$ and $m+1 | n^2+1$ (where they are both odd), exists. I initially thought they didn't exist. Later I did some casework and found a solution. The smallest such solution is $33$ , $217$ . I doubt the problem requires you to find this value, so I guess there's an easier way to prove these numbers exist.

Z K Y

The post below has been deleted. Click to close.

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

1576 posts

#5 h Oct 13, 2019, 7:00 PM • 1 Y

Y by Adventure10

The answer is $n\le 4$ , which is achievable with the sequence $4,33,217,1384$ .

First, suppose that $a_i$ is odd. Then, we need $2|a_{i+1}^2+1$ , so $a_{i+1}\equiv 1\pmod 2$ . So, an odd number must follow an odd number. However, $a_{i+1}^2+1\equiv 2\pmod 4$ , so $\frac{a_{i+1}^2+1}{a_i+1}\equiv 1\pmod 2\implies 2|a_{i+2}$ . Therefore, $a_{i+3}$ cannot exist. So, if $a_i$ is an odd, then $n\le i+2$ .

Suppose, then, that $2|a_1,a_2$ . Then, we need $a_1+1|a_2^2+1$ , and $a_2+1|a_3^2+1=\left(\frac{a_2^2-a_1}{a_1+1}\right)^2+1\implies a_2+1\bigg|a_2^4-2a_2^2a_1+2a_1^2+2a_1+1\implies a_2+1|2a_1^2+2\implies a_2+1|a_1^2+2$ So, we have two even numbers such that $a+1|b^2+1,b+1|a^2+1$ . I claim that no such pair exists, which we can do with Vieta Jumping. Suppose there exists such $a,b$ , and consider the pair which minimizes $a+b$ . Also, WLOG $b\le a$ and define $k=\frac{b^2+1}{a+1}-1$ . Of course, $k\in2\mathbb{Z}^+$ , since if $a=b^2$ , then $b+1|b^4+1\iff b+1|2$ , which is a contradiction. Furthermore, $k=\frac{b^2-a}{a+1}<\frac{a^2+a}{a+1}=a$ , and $k^2+1=\left(\frac{b^2-a}{a+1}\right)^2+1=\frac{b^4-2b^2a+2a^2+2a+1}{(a+1)^2}=\frac{(b+1)(b^3-b^2+(2-2a)b+(2a-2))+2(a^2+1)}{(a+1)^2}$ As $\gcd(b+1,a+1)|\gcd(b+1,b^2+1)=1$ and $b+1|a^2+1$ , we must have that $b+1|k^2+1$ . So, $(k,b)$ satisfies our conditions, and $k<a$ , so minimality is contradicted. Therefore, if $2|a_{k-1},a_k$ , then $a_{k+1}$ cannot exist.

Given these restrictions, our sequence can start like: OE, OOE, EE, EOE, EOOE, giving it a maximum length of 4, as desired.

Z K Y

The post below has been deleted. Click to close.

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

1740 posts

#6 h Jun 9, 2020, 9:55 PM • 1 Y

Y by Soundricio

Solved with goodbear, Th3Numb3rThr33.

The answer is $n\le4$ , achieved by $4$ , $33$ , $217$ , $1384$ . First observe that

$a_{k-1}$ odd and $a_k$ even imply $a_{k+1}$ does not exist;
$a_{k-1}$ odd and $a_k$ odd imply $a_{k+1}$ even;
$a_{k-1}$ even and $a_k$ odd imply $a_{k+1}$ odd.
$a_{k-1}$ even and $a_k$ even imply $a_{k+1}$ even.

Hence unless the sequence is forever even, its maximum length is four.

Lemma: If $a$ , $b$ are even, then $a+1\mid b^2+1$ and $b+1\mid a^2+1$ cannot simultaneously hold.

Proof. The proof is Vieta jumping: take the minimal pair $(a,b)$ , and let $\frac{b^2+1}{a+1}=m+1\quad\text{and}\quad\frac{a^2+1}{b+1}=n+1.$ We cannot simultaneously have $m\ge a$ and $n\ge b$ , so without loss of generality $m<a$ .

Note $\gcd(a,b+1)=\gcd(a+1,b+1)=1$ since $b+1\mid a^2+1$ , $a\mid a^2$ , $a+1\mid a^2-1$ . By design, $m+1\mid b^2+1$ and $m^2+1\equiv\left(\frac{b^2+1}{a+1}-1\right)^2+1\equiv\left(\frac{1-a}{1+a}\right)^2+1\equiv\frac{-2a}{2a}+1\equiv0\pmod{b+1},$ so $(m,b)$ is a smaller pair that works. $\blacksquare$

But if the sequence is all even and has length at least four, then both $a_2+1\mid a_3^2+1$ and $a_3+1\mid a_2^2+1$ hold, contradiction.

Z K Y

The post below has been deleted. Click to close.

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

308 posts

#7 h Jul 28, 2020, 1:05 AM

Y by

The answer is $n=3$ and $n=4$ . Notice that by taking $(a_1,a_2,a_3,a_4)=(4,33,217,1384)$ , the condition is satisfied.
Now notice that if such sequence exists for $n$ then we can simply take its first $m(m<n)$ terms to form a sequence with $m$ terms. Hence it suffices to show that there does not exist such a sequence for $n=5$ . Suppose on the contrary that such a sequence exists for $n=5$ .

CLAIM 1. Both $a_1$ and $a_2$ are even
Proof. This is just simple case work. We call an integer $i$ bad if $a_i$ is odd and $a_{i+1}$ is even. Notice that if $1\leq i\leq 3$ is bad, then
$a_{i+2}=\frac{a_{i+1}^2+1}{a_i+1}-1$ can not be an integer since $a_{i+1}^2+1$ is odd while $a_i+1$ is even, contradiction.
Now
1. If $a_1$ is odd while $a_2$ is even then $1$ is bad, contradiction.
2. If both $a_1$ and $a_2$ is odd then $a_3$ is even, hence $2$ is bad, contradiction.
3. If $a_1$ is even while $a_2$ is odd then it is easy to see that $a_3$ is odd. Now notice that $a_4=\frac{a_3^2+1}{a_2+1}-1$ Notice that $a_3^2+1\equiv 2\pmod 4$ . Hence $a_4$ is even. This implies that $3$ is bad, contradiciton.
This justifies the claim.

CLAIM 2. $a_2+1|(a_1^2+1)$
Proof. Let $k=a_1+1$ . We first show that $(k,a_2+1)=1$ . Indeed if $p|k$ and $p|a_2+1$ , from $a_1+1|a_2^2+1$ we have
$0\equiv a_2^2+1\equiv (-1)^2+1\equiv 2\pmod p$ Hence $p=2$ . But from CLAIM 1 we show that $k$ is odd, contradiction.
Therefore, the inverse of $k$ modulo $a_2+1$ exists. Now using $a_3=\frac{a_2^2+1}{a_1+1}$ we obtain
$\begin{align*} 0&\equiv a_3^2+1\\ &\equiv ((-1)^2+1)k^{-1}-1)^2+1\\ &\equiv 4k^{-2}-4k^{-1}+2\\ &\equiv 4k^{-2}(1-k)+2\pmod{a_2+1} \end{align*}$ Hence
$\begin{align*} 4k^{-2}(k-1)&\equiv 2\pmod{a_2+1}\\ 4(k-1)&\equiv 2k^2\pmod{a_2+1}\\ 2((k-1)^2+1)&\equiv 0\pmod{a_2+1}\\ a_1^2+1&\equiv 0\pmod{a_2+1} \end{align*}$ since $a_2+1$ is odd.

Now let $x=a_1+1$ and $y=a_2+1$ . Then $(x,y)$ satisfies the system
$x|(y-1)^2+1$ $y|(x-1)^2+1$ Since $(x,y)=1$ we have
$\begin{align} xy|(x+y-1)^2+1 \end{align}$ CLAIM 3. The only positive integer solution to $(1)$ is $(1,1)$ .
Proof. We will use the infinite descent method. WLOG assume $x\geq y$ .Suppose that there exists another solution to $(1)$ other than $(1,1)$ . We pick the one such that $x$ is minimized.
Notice that
$(x+y-1)^2+1\equiv (x-1)^2+(y-1)^2\pmod xy$ Hence we have $kxy=(x-1)^2+(y-1)^2$ for some $k\in\mathbb N$ . Now since this is an quadratic equation in $x$ there exists another root $x'$ which satisfies
$\begin{align*} x+x'&=2+ky\\ xx'&=(y-1)^2+1\\ \end{align*}$ From these we see that $x'$ is a positive integer. Moreover
$x'=\frac{(y-1)^2+1}{x}\leq\frac{(x-1)^2+1}{x}<x$ From the minimality of $x$ we have $x'=1$ . Hence $y=1$ . From $(1)$ we have $x=1$ , contradiciton.

Therefore we must have $a_1=a_2=0$ , contradiction.

Z K Y

The post below has been deleted. Click to close.

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

804 posts

#9 h Jul 28, 2020, 2:50 AM

Y by

There are no $(m,n)\in (2\mathbb N)^2$ such that $m+1\mid n^2+1$ and $n+1\mid m^2+1$ .

Suppose there exists with $m+n$ minimal and $WLOG: m>n$ . Notice
$(m+1)(n+1)\mid m^2+n^2$ So indeed $m^2+n^2=kmn+km+kn+k$ for some positive integer $k$ . So
$m^2-(kn+k)m+n^2-kn-k=0$ Let $m_0$ be the other root. It follows $m+m_0=k(n+1)$ and $mm_0+k(n+1)=n^2<m^2\implies m_0<m$ . By $m+n$ minimal we get that if $m_0\in\mathbb N$ this implies $m_0$ is odd. But so $0\equiv n^2\equiv mm_0+m+m_0\mod 4$ indeed $mm_0\equiv -(m+m_0)\mod 4$ but we have an odd part in $RHS$ and even in $LHS$ contradiction indeed $m_0\in\mathbb Z^-$ . So it follows $mm_0+m+m_0=n^2>0$ so $mm_0>-(m+m_0)$ which is a clearly contradiction since $|mm_0|>|m+m_0|$ .

Note: This solution works if $\gcd(m+1,n+1)=1$ .

This post has been edited 1 time. Last edited by Al3jandro0000, Jul 28, 2020, 3:08 AM
Reason: Change > for <

Z K Y

The post below has been deleted. Click to close.

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

439 posts

#10 h Jul 1, 2022, 11:20 AM • 4 Y

Y by farhad.fritl, Mango247, Mango247, Mango247

I proved that $n\geq 5$ fails, and I got stuck on $n=4$ case. I tried to prove that "There is not odd $a,b$ such that $a+1\mid b^2+1$ and $b+1\mid a^2+1$ ". But I coldn't prove it, because it is not true. So I want to know the motivaton behind finiding example for $n=4$ , because to find it you need to check numbers, but there are a lot of numbers until valid one.

Z K Y

The post below has been deleted. Click to close.

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

1198 posts

#11 h Dec 9, 2023, 10:53 PM

Y by

Jalil_Huseynov wrote:

I proved that $n\geq 5$ fails, and I got stuck on $n=4$ case. I tried to prove that "There is not odd $a,b$ such that $a+1\mid b^2+1$ and $b+1\mid a^2+1$ ". But I coldn't prove it, because it is not true. So I want to know the motivaton behind finiding example for $n=4$ , because to find it you need to check numbers, but there are a lot of numbers until valid one.

https://www.imo-official.org/problems/IMO2009SL.pdf See Comment 1

Z K Y

The post below has been deleted. Click to close.

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

awesomeming327.

1668 posts

awesomeming327.

#12 h Jun 4, 2024, 6:58 PM

Y by

It is not possible for $n\ge 5$ . If it were possible then $(a_1+1)(a_3+1)=a^2+1$ , $(a_2+1)(a_4+1)=a^3+1$ , and $(a_3+1)(a_5+1)=a^4+1$ . Note that in the equation $(x+1)(z+1)=y^2+1$ , if $x$ and $z$ were both odd then $4\mid y^2+1$ which is impossible. Furthermore, if $x$ or $z$ were odd then $y$ is odd. If $x$ and $z$ are even then $y$ is even. We know that of $a_2$ or $a_4$ , one is even, so $a_3$ must be also even. WLOG, $a_2$ is even with $a_3$ . Then, we have $a_2+1\mid a_3^2+1$ and $a_3+1\mid a_2^2+1$ and both are even. We prove that no such pair $(a_2,a_3)$ can exist.

Suppose it does exist then select the minimal pair $(a,b)$ . If $a=b$ then $a+1\mid a^2+1$ which implies $a=1$ , so WLOG let $a>b$ . Let $(a+1)(c+1)=b^2+1$ . Since $a>b$ , we have $c<b$ . We already know that $c+1\mid b^2+1$ . We'll show that $(c,b)$ is a smaller pair by looking at $c^2+1\pmod {b+1}$ . Note that $b^2\equiv 1\pmod {b+1}$ . We have
$c^2+1=\left(\frac{b^2+1}{a+1}-1\right)^2+1\equiv\left(\frac{a-1}{a+1}\right)^2+1\equiv\frac{a^2-2a+1}{a^2+2a+1}+1\pmod{b+1}$ but since $a^2\equiv -1\pmod {b+1}$ we have that this is equivalent to $0$ so we constructed a smaller pair. Since $c$ must also be even, this is a contradiction.

For $n\le 4$ consider the sequence: $12,57,249,1068$ .

Z K Y

The post below has been deleted. Click to close.

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

3783 posts

vsamc

#13 h Jun 4, 2024, 8:54 PM

Y by

Solution

This post has been edited 1 time. Last edited by vsamc, Jun 4, 2024, 8:55 PM
Reason: a_4 = 1384 not 1385 oops forgot to subtract by 1

Z K Y

The post below has been deleted. Click to close.

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

7586 posts

#14 h Mar 19, 2025, 4:21 PM

Y by

not writing a solution i guess but okay these strange divisibility conditions should encourage me to brainstorm vieta jumping in the future i guess okay coolio

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a