Maths Olympiad Prep

Library / /668 of 860

Combinatorics Difficulty 5.3 AIME, harder Find the answer

Find the number of positive integers j32013j \leq 3^{2013} such that j=k=0m((1)k3ak)j=\sum_{k=0}^{m}\left((-1)^{k} \cdot 3^{a_{k}}\right) for some strictly increasing sequence of nonnegative integers {ak}\left\{a_{k}\right\}. For example, we may write 3=313=3^{1} and 55=3033+3455=3^{0}-3^{3}+3^{4}, but 4 cannot be written in this form.

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

Solution

Clearly mm must be even, or the sum would be negative. Furthermore, if am2013a_{m} \leq 2013, the sum cannot exceed 320133^{2013} since j=3am+k=0m1((1)k3ak)3amj=3^{a_{m}}+\sum_{k=0}^{m-1}\left((-1)^{k} \cdot 3^{a_{k}}\right) \leq 3^{a_{m}}. Likewise, if am>2013a_{m}>2013, then the sum necessarily exceeds 320133^{2013}, which is not hard to see by applying the Triangle Inequality and summing a geometric series. Hence, the elements of {ak}\left\{a_{k}\right\} can be any subset of {0,1,,2013}\{0,1, \ldots, 2013\} with an odd number of elements. Since the number of even-sized subsets is equal to the number of odd-sized elements, there are 220142=22013\frac{2^{2014}}{2}=2^{2013} such subsets. Now, it suffices to show that given such an {ak}\left\{a_{k}\right\}, the value of jj can only be obtained in this way. Suppose for the sake of contradiction that there exist two such sequences {ak}0kma\left\{a_{k}\right\}_{0 \leq k \leq m_{a}} and {bk}0kmb\left\{b_{k}\right\}_{0 \leq k \leq m_{b}} which produce the same value of jj for jj positive or negative, where we choose {ak},{bk}\left\{a_{k}\right\},\left\{b_{k}\right\} such that min(ma,mb)\min \left(m_{a}, m_{b}\right) is as small as possible. Then, we note that since 3a0+3a1++3(ama1)30+31++3(ama1)<2(3(ama1))3^{a_{0}}+3^{a_{1}}+\ldots+3^{\left(a_{m_{a}}-1\right)} \leq 3^{0}+3^{1}+\ldots+3^{\left(a_{m_{a}-1}\right)}<2\left(3^{\left(a_{m_{a}}-1\right)}\right), we have that k=0ma((1)k3ak)>3(ama1)\sum_{k=0}^{m_{a}}\left((-1)^{k} \cdot 3^{a_{k}}\right)>3^{\left(a_{m_{a}}-1\right)}. Similarly, we get that 3(amb1)k=0mb((1)k3ak)>3(mb1)3^{\left(a_{m_{b}}-1\right)} \geq \sum_{k=0}^{m_{b}}\left((-1)^{k} \cdot 3^{a_{k}}\right)>3^{\left(m_{b}-1\right)}; for the two to be equal, we must have ma=mbm_{a}=m_{b}. However, this means that the sequences obtained by removing amaa_{m_{a}} and amba_{m_{b}} from {ak}{bk}\left\{a_{k}\right\}\left\{b_{k}\right\} have smaller maximum value but still produce the same alternating sum, contradicting our original assumption.

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.