Maths Olympiad Prep

Library / /19 of 69

Algebra Difficulty 5.6 AIME, harder Prove it Mongolia

Some natural numbers can be written as a sum of 2 or more consecutive natural numbers. For instance 24=7+8+924 = 7+8+9, 51=25+2651 = 25+26 etc. Find all such numbers which do not exceed 2014.

Solution

First we shall prove that a number which can be represented as sum of consecutive natural numbers can not be represented in the form n=2kn = 2^k.
n=m+(m+1)+(m+2)++(m+k)=(k+1)(2m+k)2 n = m + (m + 1) + (m + 2) + \dots + (m + k) = \frac{(k + 1)(2m + k)}{2}
Note that the numbers k+1k+1 and 2m+k2m+k are different by (mod 2). Hence one of these numbers is odd. Now let's prove that any number of the form n2kn \ne 2^k can be represented as sum of consecutive natural numbers.

Thus, n=2hln = 2^h \cdot l, l>1l > 1 is odd. If 2h+12^{h+1} then it is sufficient to take k=2h+11k = 2^{h+1} - 1 and m=lk2=l+12h+12=l+12h2m = \frac{l-k}{2} = \frac{l+1-2^{h+1}}{2} = \frac{l+1-2^h}{2}.

If 2h+1<l2^{h+1} < l then setting k=l1k = l - 1 and m=2h+1k2=2h+1l+12m = \frac{2^{h+1}-k}{2} = \frac{2^{h+1}-l+1}{2} we have done. Finally, we concluded desired numbers are 1,2,4,8,16,64,128,256,512,10241, 2, 4, 8, 16, 64, 128, 256, 512, 1024.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.