1991 OIM Problems/Problem 5
Problem
Let . We will say that an integer is a value of if there exist integers and such that .
i. Determine how many elements of {1, 2, 3, ... ,100} are values of .
ii. Prove that the product of values of is a value of .
~translated into English by Tomas Diaz. ~orders@tomasdiaz.com
Solution
Part i.
Let , , be integers
, then solving for using the quadratic equation we have:
Let be an integer and . Therefore, Since , then , because
Since we can look at the combinations of with for non-negative values. So, we can use: to find the values of
Since , , then to get integers and , both expressions and need to be even. This happens when either and are both odd, or both even. Thus we will try both cases:
Case 1: Both and are even.
Let , where integers and with and
Now we try the possible combinations of and :
Case 2: Both and are odd.
Let , where integers and with and
Now we try the possible combinations of and :
Combining all of the YES results cases on both cases above we have the possible elements of {1, 2, 3, ... ,100} that are values of and are not repeated as:
{1, 2,4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25, 26, 29, 32, 34, 36, 37, 40, 41, 45, 49, 50, 52, 53, 58, 61, 64, 65, 68, 72, 73, 74, 80, 81, 82, 85, 89, 90, 97, 98, 100}
Which give a total of elements.
NOTE: There is probably a better method than grinding the results. for all combinations of odds and evens on the values and finding the combinatorial equations. However, since some of the combinations repeat values, then I couldn't find a proper way to find how many elements without actually finding all of the elements.
Part ii.
Therefore we can re-write as where and and are both integers.
Thus we can now pick two integers and , thus .
We now find their products:
Let and then the product of two values of is which is also a value of because it is also written as the sum of two squares.
- Note. I actually competed at this event in Argentina when I was in High School representing Puerto Rico. I have no idea what I did on this one nor how many points they gave me. Probably close to zero on this one.
~Tomas Diaz. ~orders@tomasdiaz.com
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.