Maths Olympiad Prep

Library / /30 of 144

Algebra Difficulty 7.8 National olympiad, round 2 Find the answer

Let nn be a fixed positive integer. Find the maximum possible value of 1r<s2n(srn)xrxs, \sum_{1 \le r < s \le 2n} (s-r-n)x_rx_s, where 1xi1-1 \le x_i \le 1 for all i=1,,2ni = 1, \cdots , 2n.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let n n be a fixed positive integer. We are tasked with maximizing the following expression:

1r<s2n(srn)xrxs, \sum_{1 \le r < s \le 2n} (s-r-n)x_rx_s,

where 1xi1 -1 \le x_i \le 1 for all i=1,,2n i = 1, \cdots, 2n .

To find the maximum value of the sum, let us first analyze the term (srn)xrxs (s - r - n)x_rx_s . Notice that:

- If sr>n s - r > n , then srn>0 s - r - n > 0 .
- If sr<n s - r < n , then srn<0 s - r - n < 0 .

To maximize the sum, set xr x_r and xs x_s such that xr=xs=1 x_r = x_s = 1 if (srn)>0 (s-r-n) > 0 and xr=xs=1 x_r = x_s = -1 if (srn)<0 (s-r-n) < 0 . This assignment utilizes the maximum contribution (in terms of absolute value) provided by each pair where xrxs=1 x_r x_s = 1 .

### Analysis of (srn) (s - r - n)

The expression srn=kn s - r - n = k - n , where k=sr k = s - r , ranges from 1 1 to 2n1 2n-1 .

- When k=n+1,n+2,,2n1 k = n+1, n+2, \ldots, 2n-1 , the term srn>0 s-r-n > 0 , and hence, the optimal choice for maximizing the sum would be to set both xr=1 x_r = 1 and xs=1 x_s = 1 .
- When k=1,2,,n1 k = 1, 2, \ldots, n-1 , the term srn<0 s-r-n < 0 , and hence, xr=1 x_r = -1 and xs=1 x_s = -1 should maximize the contribution as well.

For k=n k = n , srn=0 s-r-n = 0 , contributing nothing to the sum, so any values of xr x_r and xs x_s could be used for such pairs.

### Calculating the Sum

The pairs where the sum sr s-r becomes important are those that improve beyond n n . These are combinations where:

- n+1sr2n1 n+1 \le s-r \le 2n-1 .

The number of such possible combinations can be determined by calculating the total contributions.

### Maximization

If we choose xi=1 x_i = 1 for the first n n indices and the last n n indices, calculate the contribution for all these combinations to observe the largest possible total, given our constraints. The maximum setting yields:

1r<sn0+n+1r<s2npositive contributions (equal number of terms) \sum_{1 \le r < s \le n} 0 + \sum_{n+1 \le r < s \le 2n} \text{positive contributions (equal number of terms)}
Assigning these values generates the structure to arrive at the final sum, and through careful allocation and calculation:

n(n1) \boxed{n(n-1)}

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.