Math Olympiad Problems

Some basic math olympiad problems:

Divisible by 289?

For how many integers x, x^2 - 3x - 19 is divisible by 289?

Perfect square?

For how many positive integral values of n, the expression n(4n + 1) is a perfect square?

Update (23/01/10)(05/02/10): Solution: Posted by Aaditya Ramdas (CSE IITB Alumnus & Tower Research), Piyush Sao (Senior Undergrad, EE, IITM) and Nikhil Garg (Sophomore, IITD) in comments!!  Thanx.

Comments

  1. NG4:39 PM, January 22, 2010

    f(x)=x^2-3^x-19
    =x^2-3x-70 +51
    = ( x-10) (x+7 ) + 51

    Now as f(x) is divisible by 289 => it is divisile by 17.
    => (x-10) (x+7) is divisible by 17
    => either (x-10) is divisible by 17 or/and ( x+7) is divisible by 17

    Even if one of them is divisible by 17 , other is too. ( 10 +7 =0(mod 17) )

    => (x-10)(x+7) is divisble by 17*17

    => f(x) is always 51(mod 289 )

    => no solution

    ReplyDelete
  2. Piyush10:05 PM, January 22, 2010

    FIRST one no solution: my solution in a way isomorphic to above solution.

    n(4n+1) can't be perfect square as gcd(n,4n+1)=1 hence both should be sqaure so if n=k^2 then trivially 4k^2+1 can't be square.

    ReplyDelete
  3. Pratik Poddar12:35 AM, January 23, 2010

    Nice solutions.. Thanx

    I was not expecting quick answers. First one was really tough. For the second, I didn't have elegant solution like you do.

    For the second question:
    Let n(4n+1) = k^2; (We can see that k>2n)
    k^2 - 4n^2 = n;
    (k-2n)(k+2n) = n;
    The difference between two positive factors is 4n, which is not possible as the factors of n are all less than n. :)

    Hence proved that no perfect square. :)

    But sure, Piyush's solution is far better than mine.

    ReplyDelete
  4. Aytidaa Madras12:17 AM, February 05, 2010

    i didnt get the first one. the second one was pretty trivial - just note this - the expression u gave was 4n^2 + n. But (2n)^2 is 4n^2 and (2n+1)^2 is 4n^2 + 4n +1. So obviously there is no perfect square 4n^2 + n. chamka? :P

    ReplyDelete
  5. Pratik Poddar9:57 PM, February 05, 2010

    @Ramdas.. of course.. that was "too" simple.. I could not think in this direction.. instead did it the way piyush sao did :P

    For the first part, reposting Nikhil's solution:
    Find values of integers x such that x^2 - 3x-19 is divisible by 289. We will prove that no such x exists.

    x^2 - 3*x - 19 = (x-10)(x+7) + 51

    For (x-10)(x+7) + 51 to be divisible by 289, (x-10)(x+7) has to be divisible by 17.

    So, atleast one of (x-10) or (x+7) is divisible by 17.

    Note that (x+7) - (x-10) = 17. So, if at all there exists an x, at that x, both are divisible by 17.

    So, the function is 17*17*(...) + 51. So, the function x^2-3x-19 is of the form 289*(..) + 51
    So, for no x, x^2-3x-19 is divisible by 289 :)

    ReplyDelete
  6. sac4:59 PM, June 08, 2018

    I did the first one with the use of quadratic equations and the answer is zero.

    The second one has a simpler solution in :-
    For any number n, the minimum difference between n^2 and the next square is 2*n - 1. In this case, n(4n+1) can be written as 4n^2 + n => (2n)^2 + n. The minimum difference between the next square in this case would be 2* (2n) - 1 i.e. 4n - 1. And since 4n-1 is always greater than n, there isn't a solution.

    ReplyDelete

Post a Comment

Popular posts from this blog

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more