Maths Olympiad Prep

Library / Croatian Mathematical Competitions /73 of 114

Croatian Mathematical Competitions

Algebra Difficulty 5.8 AIME, harder Prove it Croatia

Each of the numbers x1,x2,…,x2014x_1, x_2, \dots, x_{2014} is 11, 00, or −1-1. What is the minimal possible value of the sum of products of all the pairs of those numbers, i.e. the sum of all xixjx_i x_j for 1≤i<j≤20141 \le i < j \le 2014? (USSR 1965)

Solution

First note that the double sum of all the products xixjx_i x_j for 1≤i<j≤20141 \le i < j \le 2014 equals
(x1+⋯+x2014)2−(x12+⋯+x20142). (x_1 + \cdots + x_{2014})^2 - (x_1^2 + \cdots + x_{2014}^2).
Denote A=(x1+⋯+x2014)2A = (x_1 + \cdots + x_{2014})^2 and B=x12+⋯+x20142B = x_1^2 + \cdots + x_{2014}^2.
We want to minimize AA and maximize BB at the same time.
Obviously, A≥0A \ge 0. The minimum A=0A = 0 is attained when among xix_i there is an equal number of 11's and of −1-1's, e.g. when x1=x2=⋯=x1007=1x_1 = x_2 = \cdots = x_{1007} = 1, x1008=x1009=⋯=x2014=−1x_{1008} = x_{1009} = \cdots = x_{2014} = -1.
Clearly, B=x12+⋯+x20142≤12+⋯+12=2014B = x_1^2 + \cdots + x_{2014}^2 \le 1^2 + \cdots + 1^2 = 2014. The maximal value B=2014B = 2014 is attained if none of the xix_i is 00, e.g. x1=x2=⋯=x1007=1x_1 = x_2 = \cdots = x_{1007} = 1, while x1008=x1009=⋯=x2014=−1x_{1008} = x_{1009} = \cdots = x_{2014} = -1.
Since the minimum of AA and the maximum of BB can be attained for the same values of x1,…,x2014x_1, \dots, x_{2014}, we conclude that the minimal possible value of the sum of all products of pairs xixjx_i x_j (1≤i<j≤20141 \le i < j \le 2014) is A−B2=−1007\frac{A-B}{2} = -1007.

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.