Maths Olympiad Prep

Library / /79 of 136

Algebra Difficulty 8.0 National Olympiad, round 2 Prove it Hong Kong

Let n≥3n \ge 3 be an integer and x1,x2,…,xn−1x_1, x_2, \dots, x_{n-1} be nonnegative integers such that
(i) x1+x2+⋯+xn−1=nx_1 + x_2 + \dots + x_{n-1} = n,
(ii) x1+2x2+⋯+(n−1)xn−1=2n−2x_1 + 2x_2 + \dots + (n-1)x_{n-1} = 2n - 2.
Find the minimum of the sum ∑k=1n−1kxk(2n−k)\sum_{k=1}^{n-1} kx_k(2n-k). Justify your answer.

Solution

The minimum value is 3n2−3n3n^2 - 3n.
We have
∑k=1n−1kxk(2n−k)=2n(2n−2)−∑k=1n−1k2xk=2n(2n−2)−∑k=1n−1xk−∑k=1n−1(k−1)(k+1)xk≥2n(2n−2)−n−∑k=1n−1(k−1)nxk=2n(2n−2)−n−n∑k=1n−1kxk+n∑k=1n−1xk=2n(2n−2)−n−n(2n−2)+n2=3n2−3n. \begin{align*} \sum_{k=1}^{n-1} kx_k(2n-k) &= 2n(2n-2) - \sum_{k=1}^{n-1} k^2 x_k \\ &= 2n(2n-2) - \sum_{k=1}^{n-1} x_k - \sum_{k=1}^{n-1} (k-1)(k+1)x_k \\ &\ge 2n(2n-2) - n - \sum_{k=1}^{n-1} (k-1)nx_k \\ &= 2n(2n-2) - n - n \sum_{k=1}^{n-1} kx_k + n \sum_{k=1}^{n-1} x_k \\ &= 2n(2n-2) - n - n(2n-2) + n^2 \\ &= 3n^2 - 3n. \end{align*}
Equality holds when x1=n−1x_1 = n-1, x2=x3=⋯=xn−2=0x_2 = x_3 = \dots = x_{n-2} = 0 and xn−1=1x_{n-1} = 1. Therefore, the minimum value is 3n2−3n3n^2 - 3n.

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.