[Soln] 2015 IMC Day 1 Problem 2

2015 IMC 1.2. For a positive integer n, let f(n) be the number obtained by writing n in binary and replacing every 0 with 1 and vice versa. For example, n = 23 is 10111 in binary, so f(n) is 1000 in binary, therefore f(23) = 8. Prove that

\displaystyle\sum_{k=1}^n f(k) \leq \displaystyle\frac{n^2}{4}.

When does equality hold?

(The solution to this problem involves a fair bit of straightforward but messy algebra, so I will skip some of the manipulations in an effort to make the key points clear.)

Let’s list out some small values:

IMC_2015_2_01

Immediately a couple of things jump out at us:

  1. In base 2, n + f(n) consists of all 1s.
  2. Looking at each “power of 2” group from 2^k to 2^{k+1} - 1, the value of f(n) decreases by 1 from 2^k - 1 to 0.
  3. Equality holds at 2, 4 and 10. The fact that 8 is not on the list means that equality doesn’t necessarily hold when n is a power of 2, and the fact that 10 is on the list means that it is not as simple as equality holding for some small values.

Observations 1 and 2 can be formalised in the following claim:

Claim 1: Let 2^a \leq n < 2^{a+1}. Then n + f(n) = 2^{a+1} - 1.

Now that we have a relatively closed-form formula for f(n), we can try to substitute it directly into the summation and simplify it. However, from observation 2, a slightly better way would be to start with n such that the summation consists of complete “power of 2” groups.

The following claim gives the closed-form formula for a “power of 2” group (and is easily proved by summing up Claim 1 for various values of n:

Claim 2: \displaystyle\sum_{k = 2^a}^{2^{a+1} - 1} f(k) = 2^{a-1}(2^a - 1).

We can then use Claim 2 repeated to calculate the given summation for n of the form 2^a - 1. When n = 2^a - 1,

\begin{aligned} \sum_{k = 1}^n f(k) &= \sum_{i = 0}^{a-1} \sum_{k=2^i}^{2^{i+1} - 1} f(k) \\  &= \sum_{i = 0}^{a-1} 2^{i-1}(2^i - 1) \\  &= ... \\  &= \frac{2}{3}(2^a + 1)(2^{a-2} - 1) + 1. \end{aligned}

Getting to the general case is just a matter of adding the incomplete “power of 2” group:

Claim 3: Let n = 2^a + r with 0 \leq r < 2^a. Then

\displaystyle\sum_{k=1}^n f(k) = \frac{2}{3}(2^a + 1)(2^{a-2} - 1) + 1 + (r+1)(2^a-1) - \frac{r(r+1)}{2}.

To complete the proof, it remains to show that

\displaystyle\frac{2}{3}(2^a + 1)(2^{a-2} - 1) + 1 + (r+1)(2^a-1) - \frac{r(r+1)}{2} \leq \frac{(2^a + r)^2}{4}

for all possible a and 0 \geq r < 2^a. After multiplying by 12 and canceling terms, the above is equivalent to proving that

2^{2a} - 3\cdot 2^{a+1}r - 3 \cdot 2^{a+1} + 9r^2 + 18r + 8 \geq 0.

The 2^{2a} and 9r^2 terms should make one think about completing the square. In fact, it turns out that the above is equivalent to

\begin{aligned} [2^a - 3(r+1)]^2 - 1 &\geq 0, \\  [2^a - 3(r+1)]^2 &\geq 1. \end{aligned}

Can 2^a - 3(r+1) ever be zero? Well, it can’t because 2^a is never a multiple of 3 while 3(r+1) always is. Hence, [2^a - 3(r+1)]^2 can only take on positive square values, and so the inequality above is obvious.

When does equality hold? It holds when

\begin{aligned} [2^a - 3(r+1)]^2 &= 1, \text{ or} \\  2^a &= 3(r+1) \pm 1. \end{aligned}

Done!

Advertisements
This entry was posted in Intl/Regional, Undergraduate and tagged , , . Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

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