Given any 51 integers, prove that there exist two integers a, b such that a^2 - b^2 is divisible by 100
Solution: Start thinking by why only 51? If we divide any number by 50 it will give 50 possible remainders, which means there are two integers a, b which give the same remainder. So, a = 50q1+r and b = 50q2+r where 0<= r < 50.
a^2 - b^2 = (a-b)*(a+b) = 50(q1-q2) * 2(25(q1+q2)+r), hence divisibility by 100
Source: Manish asked me this problem, who was in turn asked by Rustam, who read it in Mathematical circles: the russian experience
Solution: Start thinking by why only 51? If we divide any number by 50 it will give 50 possible remainders, which means there are two integers a, b which give the same remainder. So, a = 50q1+r and b = 50q2+r where 0<= r < 50.
a^2 - b^2 = (a-b)*(a+b) = 50(q1-q2) * 2(25(q1+q2)+r), hence divisibility by 100
Source: Manish asked me this problem, who was in turn asked by Rustam, who read it in Mathematical circles: the russian experience
No comments:
Post a Comment