Maths Olympiad Prep

Library / /7 of 34

Number theory Difficulty 6.7 National olympiad Find the answer

Let f(n)f(n) be the number of ways to write nn as a sum of powers of 22 , where we keep track of the order of the summation. For example, f(4)=6f(4)=6 because 44 can be written as 44 , 2+22+2 , 2+1+12+1+1 , 1+2+11+2+1 , 1+1+21+1+2 , and 1+1+1+11+1+1+1 . Find the smallest nn greater than 20132013 for which f(n)f(n) is odd.

A number or a short expression. Spacing and $ signs are ignored.

Solutions — 2

Solution 1

First of all, note that f(n)f(n) = i=0kf(n2i)\sum_{i=0}^{k} f(n-2^{i}) where kk is the largest integer such that 2kn2^k \le n . We let f(0)=1f(0) = 1 for convenience.
From here, we proceed by induction, with our claim being that the only nn such that f(n)f(n) is odd are nn representable of the form 2a1,aZ2^{a} - 1, a \in \mathbb{Z}
We induct on aa . It is trivially true for a=0a = 0 and a=1a = 1 . From here, we show that, if the only numbers n2a11n \le 2^{a-1} - 1 where f(n)f(n) is odd are of the form described above, then the only numbers n2a1n \le 2^{a} -1 that are odd are of that form. We first consider all numbers bb , such that 2a1b2a22^{a-1} \le b \le 2^{a} - 2 , going from the lower bound to the upper bound (a mini induction, you might say). We know that f(b)=i=0a1f(b2i)f(b) = \sum_{i=0}^{a-1} f(b-2^{i}) . For a number in this summation to be odd, b2i=2m1b=2i+2m1b - 2^i = 2^m -1 \rightarrow b = 2^i + 2^m - 1 . However, we know that b>2a1b > 2^{a-1} , so mm must be equal to a1a-1 , or else bb cannot be in that interval. Now, from this, we know that i<a1i < a-1 , as b<2a1b<2^{a} - 1 . Therefore, ii and mm are distinct, and thus f(b2i)f(b - 2^i) and f(b2a1)f(b- 2^{a-1}) are odd; since there are just two odd numbers, the ending sum for any bb is even. Finally, considering 2a12^{a} - 1 , the only odd number is f(2a12a1)f(2^{a} - 1 - 2^{a-1}) , so the ending sum is odd. \Box
The smallest nn greater than 20132013 expressible as 2d1,dN2^d - 1, d \in \mathbb{N} is 2111=20472^{11} -1 = \boxed{2047}

Solution 2

Let f(n) f(n) denote the number of ways to express n n as a sum of powers of 2, considering the order of summation. To solve this problem, we must determine the smallest integer n>2013 n > 2013 for which f(n) f(n) is odd.

Firstly, we understand that f(n) f(n) is related to binary representations of numbers. Each integer n n can be uniquely represented in base 2, meaning n=ai2i n = \sum a_i 2^i , where ai a_i are binary digits (0 or 1). The task is to count all partitions utilizing available powers of 2, ordered permutations included.

A key insight into solving this problem is:
- f(n)1(mod2) f(n) \equiv 1 \pmod{2} if and only if n n is a Mersenne number, which is of the form 2k1 2^k - 1 .

To determine this, consider complete sets of powers of 2. The set of all subsets of {20,21,,2k1} \{ 2^0, 2^1, \ldots, 2^{k-1} \} , when considered with repetition and order, represents all sums f(n) f(n) for n=1 n = 1 to 2k1 2^k - 1 .

For n=2k1 n = 2^k - 1 , the binary representation contains all 1s, i.e., (111...1)2 (111...1)_2 with k k ones. Only for n n of this form, the number of ordered sums equates to an odd number due to properties of binomial coefficients (odd summation through subsets).

Our strategy is then to find the smallest k k such that n=2k1>2013 n = 2^k - 1 > 2013 .

Calculating 2k1 2^k - 1 :
2101=1023,2111=2047,2121=4095.\begin{align*} 2^{10} - 1 &= 1023, \\ 2^{11} - 1 &= 2047, \\ 2^{12} - 1 &= 4095. \end{align*}

For n=2047 n = 2047 , 2111 2^{11} - 1 is greater than 2013 and f(n) f(n) is odd since 2047 is a Mersenne number. Thus, this satisfies the given condition.

Therefore, the smallest n>2013 n > 2013 for which f(n) f(n) is odd is:
2047 \boxed{2047}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.