Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1988 IMO Problems/Problem 6"

(template)
(→‎Solution 3)
 
(11 intermediate revisions by 5 users not shown)
Line 6: Line 6:
 
is the square of an integer.
 
is the square of an integer.
  
−
==Solution==
+
==Video Solution==
 +
https://youtu.be/wqCdEE1Ueh0
 +
 
 +
==Solution 1==
  
 
Choose integers <math>a,b,k</math> such that <math>a^2+b^2=k(ab+1)</math>
 
Choose integers <math>a,b,k</math> such that <math>a^2+b^2=k(ab+1)</math>
Line 13: Line 16:
  
 
This construction works whenever there exists a solution <math>(a,b)</math> for a fixed <math>k</math>, hence <math>k</math> is always a perfect square.
 
This construction works whenever there exists a solution <math>(a,b)</math> for a fixed <math>k</math>, hence <math>k</math> is always a perfect square.
 +
 +
==Solution 2 (Sort of Root Jumping)==
 +
We proceed by way of contradiction.
 +
 +
WLOG, let <math>a\geq{b}</math> and fix <math>c</math> to be the nonsquare positive integer such that such that <math>\frac{a^2+b^2}{ab+1}=c,</math> or <math>a^2+b^2=c(ab+1).</math> Choose a pair <math>(a, b)</math> out of all valid pairs such that <math>a+b</math> is minimized. Expanding and rearranging,
 +
<cmath>P(a)=a^2+a(-bc)+b^2-c=0.</cmath>
 +
This quadratic has two roots, <math>r_1</math> and <math>r_2</math>, such that
 +
<cmath>(a-r_1)(a-r_2)=P(a)=0.</cmath>
 +
WLOG, let <math>r_1=a</math>. By Vieta's,
 +
<math>\textbf{(1) } r_2=bc-a,</math> and
 +
<math>\textbf{(2) } r_2=\frac{b^2-c}{a}.</math>
 +
From <math>\textbf{(1)}</math>, <math>r_2</math> is an integer, because both <math>b</math> and <math>c</math> are integers.
 +
 +
From <math>\textbf{(2)},</math> <math>r_2</math> is nonzero since <math>c</math> is not square, from our assumption.
 +
 +
We can plug in <math>r_2</math> for <math>a</math> in the original expression, because <math>P(r_2)=P(a)=0,</math> yielding <math>c=\frac{r^2_2+b^2}{r_2b+1}</math>. If <math>c>0,</math> then <math>r_2b+1>0,</math> and <math>r_2b+1\neq{0},</math> and because <math>b>0, r_2</math> is a positive integer.
 +
 +
We construct the following inequalities: <math>r_2=\frac{b^2-c}{a}<a,</math> since <math>c</math> is positive. Adding <math>b</math>, <math>r_2+b<a+b,</math> contradicting the minimality of <math>a+b.</math>
 +
 +
-Benedict T (countmath1)
 +
 +
==Video Solution==
 +
https://www.youtube.com/watch?v=usEQRx4J_ew ~KevinChen_Yay
 +
 +
==Solution 3==
 +
Given that <math>ab+1</math> divides <math>a^2+b^2</math>, we have <math>a^2+b^2=k(ab+1)</math> for some integer <math>k</math>.
 +
 +
Expanding the right side, we get <math>a^2+b^2=kab+k</math>. Rearranging terms, we have <math>a^2-kab+b^2-k=0</math>.
 +
 +
Consider this as a quadratic equation in <math>a</math>. By the quadratic formula, we have
 +
<cmath>a=\frac{kb\pm\sqrt{k^2b^2-4(b^2-k)}}{2}.</cmath>
 +
 +
For <math>a</math> to be an integer, the discriminant <math>k^2b^2-4(b^2-k)</math> must be a perfect square. Let <math>k^2b^2-4(b^2-k)=m^2</math> for some integer <math>m</math>.
 +
 +
Rearranging terms, we get <math>m^2=k^2b^2-4b^2+4k</math>. Factoring the right side, we have <math>m^2=(kb-2)^2</math>.
 +
 +
Thus, <math>m=kb-2</math> and <math>a=\frac{kb\pm(kb-2)}{2}=b</math> or <math>a=kb-b</math>. In either case, we have <math>a=kb-b</math>.
 +
 +
Substitute <math>a=kb-b</math> back into <math>a^2+b^2=kab+k</math>, we get <math>b^2+k^2b^2-2kb^2+b^2=kb^2-kb+k</math>.
 +
 +
Simplifying, we have <math>b^2=k</math>. Therefore, <math>\frac{a^2+b^2}{ab+1}=\frac{(kb-b)^2+b^2}{b(k)+1}=\frac{b^2}{b+1}=b</math>, which is the square of an integer.
 +
By M. Nazaryan.
  
 
{{IMO box|year=1988|num-b=5|after=Last question}}
 
{{IMO box|year=1988|num-b=5|after=Last question}}

Latest revision as of 19:24, 25 September 2024

Problem

Let $a$ and $b$ be positive integers such that $ab + 1$ divides $a^{2} + b^{2}$. Show that $\frac {a^{2} + b^{2}}{ab + 1}$ is the square of an integer.

Video Solution

https://youtu.be/wqCdEE1Ueh0

Solution 1

Choose integers $a,b,k$ such that $a^2+b^2=k(ab+1)$ Now, for fixed $k$, out of all pairs $(a,b)$ choose the one with the lowest value of $\min(a,b)$. Label $b'=\min(a,b), a'=\max(a,b)$. Thus, $a'^2-kb'a'+b'^2-k=0$ is a quadratic in $a'$. Should there be another root, $c'$, the root would satisfy: $b'c'\leq a'c'=b'^2-k<b'^2\implies c'<b'$ Thus, $c'$ isn't a positive integer (if it were, it would contradict the minimality condition). But $c'=kb'-a'$, so $c'$ is an integer; hence, $c'\leq 0$. In addition, $(a'+1)(c'+1)=a'c'+a'+c'+1=b'^2-k+b'k+1=b'^2+(b'-1)k+1\geq 1$ so that $c'>-1$. We conclude that $c'=0$ so that $b'^2=k$.

This construction works whenever there exists a solution $(a,b)$ for a fixed $k$, hence $k$ is always a perfect square.

Solution 2 (Sort of Root Jumping)

We proceed by way of contradiction.

WLOG, let $a\geq{b}$ and fix $c$ to be the nonsquare positive integer such that such that $\frac{a^2+b^2}{ab+1}=c,$ or $a^2+b^2=c(ab+1).$ Choose a pair $(a, b)$ out of all valid pairs such that $a+b$ is minimized. Expanding and rearranging, \[P(a)=a^2+a(-bc)+b^2-c=0.\] This quadratic has two roots, $r_1$ and $r_2$, such that \[(a-r_1)(a-r_2)=P(a)=0.\] WLOG, let $r_1=a$. By Vieta's, $\textbf{(1) } r_2=bc-a,$ and $\textbf{(2) } r_2=\frac{b^2-c}{a}.$ From $\textbf{(1)}$, $r_2$ is an integer, because both $b$ and $c$ are integers.

From $\textbf{(2)},$ $r_2$ is nonzero since $c$ is not square, from our assumption.

We can plug in $r_2$ for $a$ in the original expression, because $P(r_2)=P(a)=0,$ yielding $c=\frac{r^2_2+b^2}{r_2b+1}$. If $c>0,$ then $r_2b+1>0,$ and $r_2b+1\neq{0},$ and because $b>0, r_2$ is a positive integer.

We construct the following inequalities: $r_2=\frac{b^2-c}{a}<a,$ since $c$ is positive. Adding $b$, $r_2+b<a+b,$ contradicting the minimality of $a+b.$

-Benedict T (countmath1)

Video Solution

https://www.youtube.com/watch?v=usEQRx4J_ew ~KevinChen_Yay

Solution 3

Given that $ab+1$ divides $a^2+b^2$, we have $a^2+b^2=k(ab+1)$ for some integer $k$.

Expanding the right side, we get $a^2+b^2=kab+k$. Rearranging terms, we have $a^2-kab+b^2-k=0$.

Consider this as a quadratic equation in $a$. By the quadratic formula, we have \[a=\frac{kb\pm\sqrt{k^2b^2-4(b^2-k)}}{2}.\]

For $a$ to be an integer, the discriminant $k^2b^2-4(b^2-k)$ must be a perfect square. Let $k^2b^2-4(b^2-k)=m^2$ for some integer $m$.

Rearranging terms, we get $m^2=k^2b^2-4b^2+4k$. Factoring the right side, we have $m^2=(kb-2)^2$.

Thus, $m=kb-2$ and $a=\frac{kb\pm(kb-2)}{2}=b$ or $a=kb-b$. In either case, we have $a=kb-b$.

Substitute $a=kb-b$ back into $a^2+b^2=kab+k$, we get $b^2+k^2b^2-2kb^2+b^2=kb^2-kb+k$.

Simplifying, we have $b^2=k$. Therefore, $\frac{a^2+b^2}{ab+1}=\frac{(kb-b)^2+b^2}{b(k)+1}=\frac{b^2}{b+1}=b$, which is the square of an integer. By M. Nazaryan.

1988 IMO (Problems) • Resources
Preceded by
Problem 5 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Last question
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1988_IMO_Problems/Problem_6&oldid=228037"