Skip to main content

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. 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. 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. 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. 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. @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. 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

Asking a girl out

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this article though :P

Most of my friends already read an article that I wrote more than an year back - "Speak Up"


Here, inspired by the movie, The Beautiful Mind, I give a mathematical analysis of asking a girl out. Nice time it is. Feb 10. No plans for Feb 14 and I am sure this article makes me look even more geekier and all the more reason for me to believe that I will be alone, yet again. But what the hell, lets do it!

Note: This is not an independent analysis. There are many "mathematics sites" which does "similar" analysis.

@Consultants, correct me if I am wrong in my estimates. :P

Why is there a need to be selective?

From the age of 15, I guess there are approximately 3,600 girls I have liked (On average days, I don't see new girls. But going outside, I like about 30 girls. Saying that I go out once every week right …

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)

f(0,0) = 1/4[f(…

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?