Maths Olympiad Prep

Library / /2 of 6

Combinatorics Difficulty 5.1 AIME, harder Prove it Mongolia

Prove that every even number not exceeding 2n(4n+1)2n(4n + 1) can be written as ±1±2±3±±4n\pm 1 \pm 2 \pm 3 \pm \cdots \pm 4n, here we choose ++ or -.

Solution

Let us prove by induction. For n=1n = 1, we have to construct even numbers not exceeding 2(4+1)=102 \cdot (4 + 1) = 10.
+123+4=0,1+23+4=2,+1+23+4=4,+12+3+4=6,1+2+3+4=8,+1+2+3+4=10 \begin{aligned} +1 - 2 - 3 + 4 &= 0, \quad -1 + 2 - 3 + 4 &= 2, \quad +1 + 2 - 3 + 4 = 4, \\ +1 - 2 + 3 + 4 &= 6, \quad -1 + 2 + 3 + 4 = 8, \quad +1 + 2 + 3 + 4 = 10 \end{aligned}
By induction hypothesis assume that we've constructed all even numbers not exceeding 2n(4n+1)2n(4n + 1) by ±1±2±±4n\pm 1 \pm 2 \pm \cdots \pm 4n.
Now let mm be even number, such that 2n(4n+1)<m(2n+2)(4n+5)2n(4n+1) < m \le (2n+2)(4n+5).
1+2++(4n+4)=(2n+2)(4n+5) 1 + 2 + \cdots + (4n + 4) = (2n + 2)(4n + 5)
1+2++(k1)k+(k+1)++(4n+4)=(2n+2)(4n+5)2k1+2+\cdots+(k-1)-k+(k+1)+\cdots+(4n+4) = (2n+2)(4n+5)-2k, for k=1,4n+4k = 1, 4n + 4. The above expression gives us even numbers between (2n+2)(4n+1)(2n + 2)(4n + 1) and (2n+2)(4n+5)(2n + 2)(4n + 5).
Then +1+2++(l1)l+(l+1)++(4n+3)(4n+4)=(2n+2)(4n+1)2l+1 + 2 + \cdots + (l - 1) - l + (l + 1) + \cdots + (4n + 3) - (4n + 4) = (2n + 2)(4n + 1) - 2l for l=1,4nl = 1, 4n. The above expression gives us even numbers between 2n(4n+1)2n(4n + 1) and (2n+2)(4n+1)(2n + 2)(4n + 1).
For m2n(4n+1)m \le 2n(4n+1), we use (4n+1)(4n+2)(4n+3)+(4n+4)=0(4n+1)-(4n+2)-(4n+3)+(4n+4) = 0 and induction hypothesis. By this the induction is complete.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.