This is the final (and probably hardest) problem of this year’s COMC (Canadian Open Mathematics Challenge). This is a 2.5 hour contest for high school students. I wrote this contest a few months ago in November, and I didn’t get this question. Looking at the results, the average mark for this question is a mere 0.2/10.
4. For each positive integer , define to be the smallest positive integer for which is divisible by . For example, because 1 + 2 + 3 + 4 is divisible by 5 and none of 1, 1 + 2, or 1 + 2 + 3 are divisible by 5.
It seems that the first problem is understanding what the function actually means. I find it easier to define it in Haskell:
f n = head . filter (\x -> sum [1..x] `mod` n == 0) $ [1..]
Let’s use the term triangular number to define a number that can be written as . The first few triangular numbers are 1, 3, 6, and 10. The term triangular number comes from the fact that numbers like that can be arranged to form an equalateral triangle:
If we apply the arithmetic sum formula () we can see that any triangular number can be written as and that any number of that form is a triangular number. Also, let’s call the triangular number. For example, because .
Also, , when and are positive integers, means that is a factor of , or conversely that is a multiple of .
I’ll rewrite the definition of for clarity:
f n = first (\x -> T_x divides n) $ [1..]
In plain English that means is the first triangular number that’s a multiple of .
Let’s move on to the first problem:
(a) Determine all positive integers such that .
I think this problem is rather straightforward. What we need to do is find all of the numbers where . If , then the smallest triangular number that evenly divides is or 36. What numbers does 36 evenly divide? Well, the divisors of 36 are [1,2,3,4,6,9,18,36].
But wait. The problem asks for the smallest triangular number that divides it. The triangular numbers smaller than 36 are [1,3,6,10,15,21,28], so if is divisible by any of these numbers, then .
So we filter out the numbers that are divisible by a smaller triangular number: 1 (divisible by 1), 2 (divisible by 6), 3 (divisible by 6), 4 (divisible by 28), and 6 (divisible by 6); we’re left with [9,12,18,36].
Therefore the solution for are .
The next problem is a bit harder:
(b) Prove that there are infinitely many odd positive integers such that .
Let’s start by defining a few lemmas.
Lemma 1: If then .
Why is this?
If is a multiple of , then evenly divides . Therefore from our definition, the first triangular number that evenly divides is at most . From that, it’s obvious that is at most .
This doesn’t necessarily mean that , as there might still be a smaller triangular number that also divides .
Lemma 1a: If , then .
This goes the other way as well. If , must be a factor of . Notice that this is pretty much just a redefinition of , but it’s important to realize this.
Lemma 1b: For all odd integers , .
Now we just have to prove that this is true for all values of . Assume for now that . Using Lemma 1a, we know that must be a factor of .
There is another way of proving this:
We mentioned before that the formula for the triangular number is . From this, the formula for would be or .
We know that is an odd number. Then must be even and is an integer. From that we can conclude that must be a factor of .
Again, there might be a triangular number less than which fits our statements but the smallest cannot be greater than .
Lemma 2: for all positive integers .
Now let’s prove this.
Let . From Lemma 1a, must be a factor of . We can also write that as for some integer .
Substiting the triangular number formula, . Mutiplying by 2, . Of , one of them is even and the other odd. The odd one could not possibly be divisible by any exponent of 2, so the even one of the two must be divisible by .
The smallest for which this is possible is where is the odd number and is the even number, and . Then .
So now we have a lower bound for . can’t be any smaller than so . Now we just have to prove that this is true for all values of .
Using Lemma 1b this time, if we can prove that is a factor of , then . This effectively produces an upper bound. We already have a lower bound, so this reduces to only one value.
It’s easy to show that is a factor of . which is a multiple of .
Now that we’ve proven our lemmas, we can apply them to solve the problem. Let for some positive integer in . Notice that is odd, and that is a power of 2.
= = =
For any number that is greater or equal to 11, .
There are infinitely many integers , so there are infinitely many numbers that satisfy , solving the problem.
This problem is tricky because although it’s easy enough to find an upper limit for where is an odd integer, it’s not so easy when is even. The ‘trick’ is not to find it for even integers, but to find the solution for the case where . Even then, this problem still requires a good grasp of number theory.
I’ll move on to the final problem.
(c) Determine, with proof, the smallest integer for which the equation has an odd positive integer solution for .
Notice that there is a solution for where and .
After the contest I in fact ran a program to make sure that there is indeed no solution for and . I didn’t know how to prove it at the time however. Also this contest did not permit the use of computers or calculators.
In this case the answer is in fact 3, but to prove that we’ll need to prove that there is no solution for and , where is an odd positive integer.
First case: Prove that has no solution for , where is an odd integer.
If such a solution exists, there should be where . By lemma 1, is a factor of and so for some integer .
By lemma 1b, because is odd, . Substituting, so .
But as well, so is also a factor of . We can also write that as so both and are factors of .
The numbers and are consecutive integers, so . Then the minimum possible value for is and .
At the same time, . Obviously it is impossible for both to be true. This concludes our case by proof of contradiction.
Second case: Prove also that has no solution for .
The proof for this case is nearly identical for the previous case. Remember that is an odd integer, so .
If we follow through on this the same way as the previous case, we should arrive with the contradicting inequalities and .
We have an example for and we have shown that it is impossible for and , leaving the answer as 3.