1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Olympiad (integers)

  1. Sep 14, 2008 #1
    Determine all pairs (x, y) of integers such that
    1 + 2^x + 2^(2x+1) = y^2.

    ^=Exponent
     
  2. jcsd
  3. Sep 14, 2008 #2
    If you assume [tex]2^x=z[/tex] then the equation reduces to [tex]1+z+2z^2=y^2[/tex].
    Completing the square results in [tex](4z+1)^2+7=8y^2[/tex]. Substituting [tex]z=2^x[/tex] and taking log2 gives,

    [tex]x+2=log2(-1 +-\sqrt{8y^2-7})[/tex].

    For all integral values of x, LHS is an integer , say k.

    Now, this gives,

    [tex]2^k=-1+-\sqrt{8y^2-7}[/tex] which is also an integer (say k1) because 2k is also an integer. Which means that [tex]\sqrt{8y^2-7}[/tex] is also an integer (say k2).

    So thats the final condition you arrive at. For all integer values of y for which [tex]\sqrt(8y^2-7)[/tex] is an integer, x and y satisfy the above condition.
     
  4. Sep 14, 2008 #3
    Dont know how to get the latex code right, but -1+-\sqrt{8y^2-7} means the positive and negative root of 8y^2-7 subtracted by 1.
     
  5. Sep 14, 2008 #4
    By hand, y= 1,2,4 seems to satisfy the above condition, but analytically, maybe someone else could come up with a better solution. Dont know how to factor in the integer square condition.
     
  6. Sep 14, 2008 #5
    Here is an alternate (unfinished) route.

    A value of x = -1 will produce a LHS of 2, which is not a square; negative integers < -1 will not produce an integer LHS. Thus we need only be concerned with integers x >= 0.

    Trying out a few values by hand, we see that the pairs (0,2) and (4,23) are solutions, and x=1,2,3 are not. So now the question becomes, is there another solution for x > 4?

    With a little algebra (subtract 1 and expand the RHS) the equation becomes
    [tex]2^x (2^{x+1} + 1) = (y-1)(y+1)[/tex]​
    thus the RHS is the product of two consecutive evens, and y is odd. Let y = 2k+1; substituting, the RHS will become 2k(2k+1) = 4k(k+1). Dividing by 4 and replacing n = x-2 (with n > 2), we get
    [tex]2^n (2^{n+3} + 1) = k(k+1)[/tex]​
    Now one of k or k+1 is odd; the other will be divisible by 2^n (as a matter of fact, since 2^{n+3} + 1 is odd, 2^n is the greatest power of 2 that divides the RHS).

    If we could prove that no integer n > 2 satisfies the above, we would be done. The requirement of exactly n 2's among the prime factors of the RHS only sieves candidates, but does not provide a bound for k.

    My hunch is that something has to become broken when the powers of two get bigger, i.e. that the LHS cannot be expressed as a product of two consecutive integers (for n=2 it can, though).
     
  7. Sep 15, 2008 #6
    Ok, I will attempt to finish Dodo's solution. Just to recap, he subtracted 1 from both sides of the equation to factor the difference of squares. Since the LHS is even, it's not hard to see that y must be odd so he set y = 2k + 1 to arrive at

    [tex]2^x(2^{x+1} + 1) = 2k(2k+2) \Rightarrow 2^{x-2}(2^{x+1}+1) = k(k+1)[/tex].

    Furthermore, he set [tex]n = x - 2[/tex] but this time I'm going to put a different condition on n so that [tex]n \geq -2[/tex] because we want to find solutions for [tex]x \geq 0[/tex].

    So after applying the conditions, we have

    [tex]2^n(2^{n+3} + 1) = k(k+1), n \geq -2[/tex]

    Now consecutive integers are relatively prime and therefore, [tex]2^n | k[/tex] or [tex]2^n | k+1[/tex].

    Case 1: [tex]2^n | k \Rightarrow k = a2^n[/tex] for some integer [tex]a > 0[/tex]. Plugging this back into our last equation, we get [tex]2^n(2^{n+3}+1) = a2^n(a2^n + 1) \Rightarrow a^22^n + a = 2^{n+3} + 1 \Rightarrow 2^n(a^2 - 2^3) = 1 - a \Rightarrow 2^n = \frac{1-a}{a^2 - 8}[/tex]. For [tex]a > 2[/tex], the RHS is negative, which is a contradiction. [tex]a[/tex] cannot be 1 either, but for [tex]a = 2[/tex], we have [tex]2^n = \frac{1}{4} \Rightarrow n = -2 \Rightarrow x = 0[/tex]. Hence (0,2) and (0, -2) are solutions.

    Case 2: [tex]2^n | k + 1 \Rightarrow k = b2^n - 1[/tex] for some integer [tex] b > 0[/tex]. Applying the same technique as in the first case, we have [tex]2^n(2^{n+3} + 1) = (b2^n - 1)(b2^n) \Rightarrow b^22^n - b = 2^{n+3} + 1 \Rightarrow 2^n(b^2 - 8) = 1 + b \Rightarrow 2^n = \frac{1+b}{b^2 - 8}[/tex]. For [tex]b > 3[/tex], it's easy to see we won't find any solutions for n. Similarly, we won't find any solutions for [tex]b < 3[/tex] since the RHS will be negative (except our trivial solution which occurs when [tex]b = -2[/tex], but we assumed allowably [tex]b > 0[/tex]). Thus, we find that [tex]b = 3 \Rightarrow n = 2 \Rightarrow x = 4[/tex] gives us our other pair of solutions, (4, 23) and (4, -23)

    Note that we find our solutions in pairs because of the [tex]y^2[/tex] term in the original equation so (x, -y) is a solution whenever (x, y) is. Thus our solutions are (0, 2), (0, -2), (4, 23), and (4, -23)
     
  8. Sep 15, 2008 #7
    There is a small mistake in Dodo, where he says: the RHS will become 2k(2k+1) = 4k(k+1), since he really means 2k(2k+2) = 4k(k+1).

    I dont understand this use of RHS, or is it LHS? Oh! From reading snipez90, I see it means nothing more than left or right side of the equation.
     
    Last edited: Sep 15, 2008
  9. Sep 15, 2008 #8
    Thanks for answer(and for solution)
    CORRECT ANSWER :(x, y)- (0, 2), (0,−2), (4, 23), (4,−23)
     
  10. Sep 15, 2008 #9
    Thats it? Just 4 solutions? Shouldnt there be a general formula or something?
     
  11. Sep 17, 2008 #10
    chaoseverlasting: Thats it? Just 4 solutions? Shouldnt there be a general formula or something?

    Snipez90 did good work on that problem, I don't find any errors. So I guess we just have to accept it.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Olympiad (integers)
  1. Mathematics olympiad (Replies: 4)

  2. Olympiad geometry (Replies: 1)

  3. Olympiad Question: (Replies: 1)

  4. Math Olympiad (Replies: 11)

Loading...