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.