Each of the numbers x1,x2,…,x2014 is 1, 0, or −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 xixj for 1≤i<j≤2014? (USSR 1965)
Solution
First note that the double sum of all the products xixj for 1≤i<j≤2014 equals (x1+⋯+x2014)2−(x12+⋯+x20142). Denote A=(x1+⋯+x2014)2 and B=x12+⋯+x20142. We want to minimize A and maximize B at the same time. Obviously, A≥0. The minimum A=0 is attained when among xi there is an equal number of 1's and of −1's, e.g. when x1=x2=⋯=x1007=1, x1008=x1009=⋯=x2014=−1. Clearly, B=x12+⋯+x20142≤12+⋯+12=2014. The maximal value B=2014 is attained if none of the xi is 0, e.g. x1=x2=⋯=x1007=1, while x1008=x1009=⋯=x2014=−1. Since the minimum of A and the maximum of B can be attained for the same values of x1,…,x2014, we conclude that the minimal possible value of the sum of all products of pairs xixj (1≤i<j≤2014) is 2A−B=−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.