2009 COMC: Problem 4B

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 n, define f(n) to be the smallest positive integer s for which 1 + 2 + 3 + \cdots + (s-1) + s is divisible by n. For example, f(5) = 4 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 f(n) 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 1 + 2 + 3 + \cdots + N. 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:

Lemma 0: T_n = \frac{n(n+1)}{2}

If we apply the arithmetic sum formula (\frac{(a+b)n}{2}) we can see that any triangular number can be written as \frac{n(n+1)}{2} and that any number of that form is a triangular number. Also, let’s call T_n the n^{th} triangular number. For example, T_5 = 15 because \frac{5(5+1)}{2} = 15.

Also, A | B, when A and B are positive integers, means that A is a factor of B, or conversely that B is a multiple of A.

I’ll rewrite the definition of f(n) for clarity:

f n = first (\x -> T_x divides n) $ [1..]

In plain English that means f(n) is the first triangular number that’s a multiple of n.

Let’s move on to the first problem:

(a) Determine all positive integers a such that f(a) = 8.

I think this problem is rather straightforward. What we need to do is find all of the numbers where f(a) = 8. If f(a) = 8, then the smallest triangular number that evenly divides a is T_8 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 a is divisible by any of these numbers, then f(A) \neq 8.

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 f(a) = 8 are a = 9,12,18,36.

The next problem is a bit harder:

(b) Prove that there are infinitely many odd positive integers b such that f(b+1) - f(b) > 2009.

Let’s start by defining a few lemmas.

Lemma 1: If w | T_z then f(w) \leq z.

Why is this?

If T_z is a multiple of w, then T_z evenly divides w. Therefore from our definition, the first triangular number that evenly divides w is at most T_z. From that, it’s obvious that f(w) is at most T_z.

This doesn’t necessarily mean that f(w) = z, as there might still be a smaller triangular number that also divides w.

Lemma 1a: If f(w) = z, then w | T_z.

This goes the other way as well. If f(w) = z, w must be a factor of T_z. Notice that this is pretty much just a redefinition of f(x), but it’s important to realize this.

Lemma 1b: For all odd integers y, f(y) = y-1.

Now we just have to prove that this is true for all values of a. Assume for now that f(y) = y-1. Using Lemma 1a, we know that y must be a factor of T_{y-1}.

There is another way of proving this:

We mentioned before that the formula for the n^{th} triangular number is \frac{n(n+1)}{2}. From this, the formula for T_{y-1} would be \frac{y(y-1)}{2} or y \frac{y-1}{2}.

We know that y is an odd number. Then y-1 must be even and \frac{y-1}{2} is an integer. From that we can conclude that y must be a factor of T_{y-1}.

Again, there might be a triangular number less than T_{y-1} which fits our statements but the smallest cannot be greater than T_{y-1}.

Lemma 2: f(2^a) = 2^{a+1} - 1 for all positive integers a.

Now let’s prove this.

Let m = f(2^a). From Lemma 1a, 2^a must be a factor of T_m. We can also write that as q 2^a = T_m for some integer q.

Substiting the triangular number formula, q 2^a = \frac{m(m+1)}{2}. Mutiplying by 2, q 2^{a+1} = m(m+1). Of (m,m+1), 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 2^{a+1}.

The smallest m for which this is possible is where m is the odd number and m+1 is the even number, and m = 2^{a+1}-1. Then m+1 = 2^{a+1}.

So now we have a lower bound for f(2^a). m can’t be any smaller than 2^{a+1}-1 so f(2^a) \geq 2^{a+1}-1. Now we just have to prove that this is true for all values of a.

Using Lemma 1b this time, if we can prove that 2^a is a factor of T_{2^{a+1}-1}, then f(2^a) \leq 2^{a+1}-1. This effectively produces an upper bound. We already have a lower bound, so this reduces f(2^a) to only one value.

It’s easy to show that 2^a is a factor of T_{2^{a+1}-1}. T_{2^{a+1}-1} = 2^{a+1} \frac{2^{a+1}-1}{2} = 2^a (2^{a+1}-1) which is a multiple of 2^a.

Now that we’ve proven our lemmas, we can apply them to solve the problem. Let b = 2^a-1 for some positive integer a in f(b+1) - f(b). Notice that b is odd, and that b+1 is a power of 2.

f(b+1)-f(b) = f(2^a)-f(2^a-1) = 2^{a+1}-1-f(2^a-1) \leq 2^{a+1}-1-(2^a-2) = 2^a+1

In short:

f(b+1)-f(b) \leq 2^a+1.

For any number a that is greater or equal to 11, 2^a+1 > 2009.

There are infinitely many integers a \geq 11, so there are infinitely many numbers b that satisfy f(b+1)-f(b)>2009, solving the problem.

This problem is tricky because although it’s easy enough to find an upper limit for f(y) where y is an odd integer, it’s not so easy when y is even. The ‘trick’ is not to find it for even integers, but to find the solution for the case where b = 2^a. 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 k for which the equation f(c) = f(c+k) has an odd positive integer solution for c.

Notice that there is a solution for k = 3 where f(9) = 8 and f(12) = 8.

After the contest I in fact ran a program to make sure that there is indeed no solution for k = 1 and k = 2. 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 f(c) = f(c+1) and f(c) = f(c+2), where c is an odd positive integer.

First case: Prove that f(c) = f(c+1) has no solution for c, where c is an odd integer.

If such a solution exists, there should be m where m = f(c) = f(c+1). By lemma 1, c is a factor of T_m and T_m = \frac{m(m+1)}{2} so qc = \frac{m(m+1)}{2} for some integer q.

By lemma 1b, because c is odd, m \leq c-1. Substituting, qc \leq \frac{c(c-1)}{2} so q \leq \frac{c-1}{2}.

But f(c+1) = m as well, so c+1 is also a factor of T_m. We can also write that as qc so both c+1 and c are factors of qc.

The numbers c and c+1 are consecutive integers, so lcm(c,c+1) = c(c+1). Then the minimum possible value for qc is c(c+1) and q \geq c+1.

At the same time, q \leq \frac{c-1}{2}. Obviously it is impossible for both to be true. This concludes our case by proof of contradiction.

Second case: Prove also that f(c) = f(c+2) has no solution for c.

The proof for this case is nearly identical for the previous case. Remember that c is an odd integer, so lcm(c,c+2) = c(c+2).

If we follow through on this the same way as the previous case, we should arrive with the contradicting inequalities q \geq c+2 and q \leq \frac{c-1}{2}.

We have an example for k=3 and we have shown that it is impossible for k=1 and k=2, leaving the answer as 3.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s