For solutions to the original problem from the Canadian Intermediate
Mathematics Contest, please refer to the solutions on our website.
We will start by presenting two general facts. It is worth spending
some time digesting them before reading the rest of the solution.
Suppose is a positive
integer. If is a positive integer
with , then , and so is not in Row . Therefore, we might as well assume
that as we look for the
largest such that is not in Row .
Assume now that is
not in Row . By Fact 1 with , there must be integers and such that and .
Because and are integers strictly between and , there must exist integers and with such that and . We are assuming that , so we can substitute to get
.
This can be simplified and rearranged to get . The integers and are both positive, so is positive, which implies that is positive so we can solve for
to get .
Now suppose and
consider the expression , which we can simplify as follows: Carefully
considering the components of the fraction above, we have that is a positive integer with , so the quantity must be negative, and since , the quantities and are both positive. Therefore, the
fraction at the end of the calculation above is negative, so we get that
which implies that .
We have shown that if , then the quantity can be made
larger by decreasing by
. A similar argument shows that if
, then the quantity gets
larger when is decreased by . Since and we seek the largest possible , we conclude that can always be made larger by decreasing
by , provided is larger than . Therefore, the maximum value of
must occur when .
Note: It is possible (and essentially assured) that
is not always an
integer. However, since it is maximized when , which makes the denominator
equal to , the maximum possible
value of given
the constraints on and happens to be an integer. Therefore,
the maximum possible integer value of is the maximum possible
value, which occurs when .
Substituting into , we get . Therefore, the task is to maximize
subject to the conditions and .
Substituting into , we get . Since is fixed, the expression is a quadratic in with a negative coefficient of . Therefore, it has a maximum value
and it occurs when .
We are looking for the maximum among integer values of , so if is an integer, the maximum
occurs exactly when . Since , this implies that as well.
Otherwise, the maximum will occur at the integer nearest . There is a tie between
and .
Notice that the sum of these two possible values of is , so one
of the values must be and the
other must be . Since , we have that and .
Now to summarize what we have so far: if we assume that is not in Row , then is no larger than when is odd and is no larger than when
is even. Note that when , we
get , which
agrees with the answer to part (c) of the original problem.
To finish the argument, we need to verify that
is not in Row when is odd and that is not in Row when is even. We will only include the
verification for when is odd
here. The verification when is
even is similar.
Expanding and simplifying, we have Now set
,
, and . It follows from the
calculation above that . If we
can show that , then we can apply Fact 2 to get that is not in Row . Note that by definition, so is automatically true. Expanding
gives and
, and it is
easily checked that for all . This means we can apply Fact 2 as
long as , which completes the
verification that the maximum value of is exactly when is odd and .
Finally, if , then . By the original contest
problem, is in Row for . Also, is in
Row when , but when , is not in Row . Therefore, when , the maximum value of for which is not in Row is . Notice that evaluates
to when , so the formula works even in this
case.
Suppose is a positive
integer with such that
is not in Row . By Fact 1, there exist positive
integers and such that and . The equation implies that is a multiple of , and since is a prime number, or must be a multiple of . (This is by a fact often known as
Euclid’s Lemma.) We also have that and are positive and both less than , so it is impossible for either of them
to be a multiple of because is prime.
We conclude that there are no positive integers with such that is not in
Row . In other words, is in Row for every positive integer with .
Since is not in any row and
is a multiple of ,
is the largest integer with the
property that and is not in Row . Thus, when is a prime number.
We will show that . To do this, we need to
establish two things:
We will assume that . If
not, then and the proof is
essentially identical.
To see that the first point is true, set , , , and and apply Fact 2. Note that
so or . We also have , which can be rearranged to get
, and so , which can be factored to
get or . Finally, , so . Putting these
inequalities together, we have . Since , the conditions of
Fact 2 are satisfied and we can conclude that is not in Row .
Now suppose is an integer such
that . We
wish to show that must be in
Row . To do this, we will assume
that it is not in Row and deduce
a contradiction.
To that end, assume that is
not in Row . By Fact 1, there
must be integers and with such that . If is a multiple of , then we would have , but by assumption, so this is
impossible. Therefore, is not a
multiple of . Similarly, is not a multiple of .
Since is a multiple of and and are prime, either is a multiple of and is a multiple of , or is a multiple of and is a multiple of . We will assume that is a multiple of and is a multiple of . The other situation is similar. This
implies the existence of integers
and such that and . Observe that since , we must have , and similarly . Since , , , and are integers, we conclude that and .
Since we are assuming that , we have However, we are also assuming that , so we can deduce that
which is
impossible because it implies . Therefore, our assumption that
is not in Row must be false, and we conclude that
is in Row .
Therefore, as
claimed earlier.
The value of depends
on whether is even or odd. If
for some integer , then . If for some integer , then .
Here we include a proof in the case where is even. The proof when is odd is a slight modification of the
proof given for when is even.
Assume for some positive
integer . As with part (c), we
need to show that
If we set , , and , then we will
have and
, so is not in Row
by Fact 2. This establishes
the first bullet point above.
For the second, suppose
is not in Row for some with .
By Fact 1, there must be integers
and with and .
The product must have at
least factors of the prime
number , meaning the two integers
and have at least a total of factors of between them. Therefore, there are
non-negative integers and such that , is a multiple of , and is a multiple of . By definition, there are positive
integers and such that and .
We are also assuming that , so and , which implies and . Since
, , , and are non-negative integers, we have
and . Multiplying these
inequalities, we obtain . We are also assuming that , so we can substitute to get
Thus, , so , which implies .
We can now conclude that . To finish the argument, we will show that , which would
imply that ,
which is clearly false.
To show that , we will show that if and are non-negative integers with , then the quantity is maximized when .
Suppose and are non-negative integers with and . Consider the quantity . We
can manipulate this difference as follows. We
are assuming that . Since
is even, it must also be true
that is even. Therefore, . As well, is a prime number so , which implies and . The quantity is positive, and so we conclude that
, which implies that . Rearranging this inequality, we get .
What we have shown is that if
and are non-negative integers
with and , we can increase the value of
by decreasing by and increasing by . It follows that is maximized when and are as close together as possible,
which happens when .
In general, can be
computed as follows: find the unique positive integers and with , , and as small as possible. Then .
For example, if is a prime
number, then the only positive factor pair is , so and . Indeed, from part (b), . If is a perfect square, then for some positive integer . Here, we must have because this gives , which is the smallest that the
difference between the factors in a factor pair could possibly be.
Indeed, agrees with
the case from part (d) where . As a final example, consider
. Its positive factor pairs are
, , , , , and . The pair with the smallest
difference between the factors is , so we have and , giving . Indeed, , so is not in Row . As well, you can check that is in Row for each from through , which shows that .
We will now justify that this "formula" always works.
Fix an integer and suppose
, , , and are positive integers with , , and .
If , then since
, we have , so we can conclude
that . Expanding
these expressions and adding to
both sides, we have and since and are both positive, we must have . Essentially the same
argument in reverse shows that if , then .
We have shown that
exactly when . This
implies that if we consider all positive factor pairs of , the one that has the smallest
difference is also the one that has the smallest sum. Therefore, we can
restate our "formula" as follows: Given a positive integer , let and be positive integers with and as small as possible. Then . We will assume that the
integers and satisfy . If not, then they can be
relabelled.
The overall structure of the argument will resemble the arguments for
parts (c) and (d). That is, we will show that is not in Row , but if , then is in Row . The solution presented will use,
without proof, a few well-known facts about divisibility and greatest
common divisors.
To see that is not
in Row , take , , and and apply Fact 2. That these
choices of , , , and satisfy the conditions of Fact 2 can be
verified in essentially the same way as they were in the solutions to
parts (c) and (d).
Now suppose is an integer with
such
that is not in Row . By Fact 1, there are integers and such that and . Let and then define and . Observe that the integers
and must satisfy since if they had a common
divisor larger than , then the
greatest common divisor of and
would need to be larger than
.
Dividing both sides of by
, we get , which shows that is a multiple of . We have already noted that and have no common divisors larger than
, so we are forced to conclude
that is a multiple of . That is, there must be some integer
such that .
To summarize, so far we have that , , , and . Consider the integers and and suppose . Multiplying both sides by gives or , but
this contradicts our assumption that , so we cannot have . Therefore, , and since both and are integers, we get . Similarly, if , then or , which contradicts our
assumption, so we conclude that and so .
We are assuming that , so we have the following which implies . Using that
, we cancel to get which can be
expanded to get , and since , this simplifies to . However, is the factorization of into a product of positive integers
that minimizes the sum of the factors. Since , the inequality is a contradiction of this
minimality.
We conclude that our assumption that is not in Row must be false, which means is in Row . This completes the proof.