Maths Olympiad Prep

Library / Mongolian Mathematical Olympiad 46 /2 of 5

Mongolian Mathematical Olympiad 46

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.
+1−2−3+4=0,−1+2−3+4=2,+1+2−3+4=4,+1−2+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+⋯+(k−1)−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+⋯+(l−1)−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 m≤2n(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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.