Maths Olympiad Prep

Library / /53 of 82

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 1i<j20141 \le i < j \le 2014? (USSR 1965)

Solution

First note that the double sum of all the products xixjx_i x_j for 1i<j20141 \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, A0A \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++x2014212++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 (1i<j20141 \le i < j \le 2014) is AB2=1007\frac{A-B}{2} = -1007.

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.