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 "2006 IMO Problems/Problem 4"

(→‎Solution)
(→‎Solution: Replaced bogus solution with official solution from 2006 shortlist)
Line 6: Line 6:
 
Bogus Solution
 
Bogus Solution
  
−
<math>x < 0</math>: LHS integer iff <math>x =-1</math>, but then <math>LHS = 2 \neq y^{2}</math>.
+
If <math>(x,y)</math> is a solution then obviously <math>x\geq 0</math> and <math>(x,-y)</math> is a solution too. For <math>x=0</math> we get the two solutions <math>(0,2)</math> and <math>(0,-2)</math>.
−
<math>(x,y) = (0,2)</math> is a solution.
 
−
for <math>x = 1,2</math> no solution.
 
−
so assume <math>x > 2</math>. LHS is odd, so writing <math>y = 2n+1</math> gives us <math>2^{x-2}(1+2^{x+1}) = n(n+1)</math>. <math>n,n+1</math> are coprime, and so are <math>2^{x-2}, 1+2^{x+1}</math>. so <math>n = 2^{x-2}, n+1=1+2^{x+1}</math> or vice versa, but both lead to a contradiction
 
  
−
NOTE: This solution does not seem to be correct. Take e.g. <math>x=4</math>. Then <math>LHS=529</math> and <math>y=\pm23</math>. The argument of the solution is promising, but the following is ''not'' true: Let <math>a</math>, <math>b</math> be co-prime and let <math>c</math>, <math>d</math> be also coprime and additionally let <math>ab = cd</math>. Then it must either be <math>(a,b) = (c,d)</math> or <math>(b,a) = (c,d)</math>.
+
Now let <math>(x,y)</math> be a solution with <math>x > 0</math>; without loss of generality confine attention to <math>y > 0</math>.  The equation rewritten as <cmath>2^x(1+2^{x+1}) = (y-1)(y+1)</cmath> shows that the factors <math>y-1</math> and <math>y+1</math> are even, exactly one of them divisible by <math>4</math>.  Hence <math>x\geq 3</math> and one  of these factors is divisible by <math>2^{x-1}</math> but not by <math>2^x</math>.  So
 +
<cmath>y = 2^{x-1}m + \varepsilon, \qquad m\text{ odd},\qquad \varepsilon = \pm 1.\qquad\qquad(*)</cmath>
 +
Plugging this into the original equation we obtain
 +
<cmath>2^x(1+2^{x+1}) = (2^{x+1}m + \varepsilon)^2 - 1 = 2^{2x-2}m^2 + 2^xm\varepsilon,</cmath>
 +
or, equivalently <cmath>1 + 2^{x+1} = 2^{x-2}m^2 + m\varepsilon.</cmath> Therefore <cmath>1 - \varepsilon m = 2^{x-2}(m^2 - 8).\qquad(\dagger) </cmath> For <math>\varepsilon = 1</math> this yields <math>m^2 - 8 < 0</math>, i.e. <math>m=1</math>, which fails to satisfy <math>(\dagger)</math>. For <math>\varepsilon = -1</math> equation <math>(\dagger)</math> gives us <cmath>1 + m = 2^{x-2}(m^2 - 8) \geq 2(m^2 - 8),</cmath> implying <math>2m^2 - m - 17 \leq 0</math>. Hence <math>m\leq 3</math>; on the other hand <math>m</math> cannot be <math>1</math> by <math>(\dagger)</math>.  Because <math>m</math> is odd, we obtain <math>m=3</math>, leading to <math>x=4</math>.  From <math>(*)</math> we get <math>y=23</math>.  These values indeed satisfy the given equation.  Recall that then <math>y = -23</math> is also good. Thus we have the complete list of solutions <math>(x,y)</math>: <math>(0,2)</math>, <math>(0,-2)</math>, <math>(4,23)</math>, <math>(4,-23)</math>.

Revision as of 12:59, 31 July 2019

Problem

Determine all pairs $(x, y)$ of integers such that \[1+2^{x}+2^{2x+1}= y^{2}.\]


Solution

Bogus Solution

If $(x,y)$ is a solution then obviously $x\geq 0$ and $(x,-y)$ is a solution too. For $x=0$ we get the two solutions $(0,2)$ and $(0,-2)$.

Now let $(x,y)$ be a solution with $x > 0$; without loss of generality confine attention to $y > 0$. The equation rewritten as \[2^x(1+2^{x+1}) = (y-1)(y+1)\] shows that the factors $y-1$ and $y+1$ are even, exactly one of them divisible by $4$. Hence $x\geq 3$ and one of these factors is divisible by $2^{x-1}$ but not by $2^x$. So \[y = 2^{x-1}m + \varepsilon, \qquad m\text{ odd},\qquad \varepsilon = \pm 1.\qquad\qquad(*)\] Plugging this into the original equation we obtain \[2^x(1+2^{x+1}) = (2^{x+1}m + \varepsilon)^2 - 1 = 2^{2x-2}m^2 + 2^xm\varepsilon,\] or, equivalently \[1 + 2^{x+1} = 2^{x-2}m^2 + m\varepsilon.\] Therefore \[1 - \varepsilon m = 2^{x-2}(m^2 - 8).\qquad(\dagger)\] For $\varepsilon = 1$ this yields $m^2 - 8 < 0$, i.e. $m=1$, which fails to satisfy $(\dagger)$. For $\varepsilon = -1$ equation $(\dagger)$ gives us \[1 + m = 2^{x-2}(m^2 - 8) \geq 2(m^2 - 8),\] implying $2m^2 - m - 17 \leq 0$. Hence $m\leq 3$; on the other hand $m$ cannot be $1$ by $(\dagger)$. Because $m$ is odd, we obtain $m=3$, leading to $x=4$. From $(*)$ we get $y=23$. These values indeed satisfy the given equation. Recall that then $y = -23$ is also good. Thus we have the complete list of solutions $(x,y)$: $(0,2)$, $(0,-2)$, $(4,23)$, $(4,-23)$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_IMO_Problems/Problem_4&oldid=108092"