Maths Olympiad Prep

Library / /103 of 120

Combinatorics Difficulty 6.1 National olympiad Prove it Saudi Arabia

For each positive integer nn let the set AnA_{n} consist of all numbers ±1±2±±n\pm 1 \pm 2 \pm \ldots \pm n. For example,
A1={1,1},A2={3,1,1,3}A3={6,4,2,0,2,4,6} \begin{gathered} A_{1}=\{-1,1\}, \quad A_{2}=\{-3,-1,1,3\} \\ A_{3}=\{-6,-4,-2,0,2,4,6\} \end{gathered}
Find the number of elements in AnA_{n}.

Solution

The greatest element of set AnA_{n} is
1+2++n=n(n+1)2 1+2+\ldots+n=\frac{n(n+1)}{2}
and the smallest element of AnA_{n} is
12n=n(n+1)2. -1-2-\ldots-n=-\frac{n(n+1)}{2} .
Also, the difference of any two elements of AnA_{n} is even, hence all elements of AnA_{n} are of the same parity.
Let us prove that all integers between n(n+1)2-\frac{n(n+1)}{2} and n(n+1)2\frac{n(n+1)}{2}, and of the same parity with n(n+1)2\frac{n(n+1)}{2}, belong to AnA_{n}, and these are all the elements of AnA_{n}. Indeed, let xAnx \in A_{n} be an element such that n(n+1)2x<n(n+1)2-\frac{n(n+1)}{2} \leq x<\frac{n(n+1)}{2}.
Case 1. If the writing of xx begins with -1 , then by changing -1 by +1 , we get x+2Anx+2 \in A_{n}.
Case 2. If the writing of xx begins with +1 , then consider the first term with sign -. A such term exists, otherwise
x=1+2++n=n(n+1)2. x=1+2+\ldots+n=\frac{n(n+1)}{2} .
In this case we have
x=+1+2++(k1)k±±n, x=+1+2+\ldots+(k-1)-k \pm \ldots \pm n,
where k-k is the considered term. By changing the signs of terms k1k-1 and kk, it follows x+2Anx+2 \in A_{n}.
We obtain
An={n(n+1)2,n(n+1)2+2,,n(n+1)22,n(n+1)2}A_{n}=\left\{-\frac{n(n+1)}{2},-\frac{n(n+1)}{2}+2, \ldots, \frac{n(n+1)}{2}-2, \frac{n(n+1)}{2}\right\}, that is the number of elements in AnA_{n} is n(n+1)2+1\frac{n(n+1)}{2}+1.

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.