Maths Olympiad Prep

Library / /28 of 48

Combinatorics Difficulty 6.0 National Olympiad Prove it Baltic Way

Let n4n \ge 4 be an even integer. In how many ways can one select four different positive integers kk, 1kn1 \le k \le n, so that the sum of two of the chosen numbers equals the sum of the other two?

Solution

Answer:
(n2)(2n25n)24 \frac{(n-2)(2n^2 - 5n)}{24}

Solution:
Letting aa be the smallest and bb the largest of the chosen numbers, the sum in the problem has to be a+ba+b. So given aa and bb, the other numbers cc and dd have to satisfy a<c,d<ba < c, d < b and c+d=a+bc+d = a+b. For the smaller of c,dc, d, say cc, one can take any number larger than aa but smaller than the average of aa and bb, and the choice cc uniquely determines dd. So if ba=2p+1b-a = 2p+1 or ba=2p+2b-a = 2p+2, there are pp possible choices of cc. Assume n=2mn=2m. Then the largest possible ba=2m1=2(m1)+1b-a = 2m-1 = 2(m-1)+1, and there is just one possible pair (a,b)=(1,2m)=(1,n)(a, b) = (1, 2m) = (1, n). For ba=nqb-a = n-q there are qq possible pairs (a,b)(a, b). The pp possible choices of cc thus appear when q=n2p2q = n-2p-2 and q=n2p1q = n-2p-1, or altogether in 2n4p32n-4p-3 cases. So the total number of choices is
p=1m2(2n4p3)p+m1=(2n3)p=1m2p4p=1m2p2+m1=12(2n3)(m2)(m1)46(m2)(m1)(2m3)+(m1). \begin{aligned} \sum_{p=1}^{m-2} (2n - 4p - 3)p + m - 1 &= (2n - 3) \sum_{p=1}^{m-2} p - 4 \sum_{p=1}^{m-2} p^2 + m - 1 \\ &= \frac{1}{2}(2n - 3)(m - 2)(m - 1) - \frac{4}{6}(m - 2)(m - 1)(2m - 3) + (m - 1). \end{aligned}
Using 2m=n2m=n, the last sum is easily simplified into
(n2)(2n25n)24 \frac{(n-2)(2n^2 - 5n)}{24}
The restriction "n even" can be removed, but then there are two essentially similar but slightly different sums to be done. "n odd" would be infinitesimally easier, because there would not be the single last term.

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.