Maths Olympiad Prep

Library / /6 of 7

Algebra Difficulty 6.0 AIME, harder Find the answer United States

Let x1x2x100x_1 \le x_2 \le \dots \le x_{100} be real numbers such that x1+x2++x100=1|x_1| + |x_2| + \dots + |x_{100}| = 1 and x1+x2++x100=0x_1 + x_2 + \dots + x_{100} = 0. Among all such 100-tuples of numbers, the greatest value that x76x16x_{76} - x_{16} can achieve is mn\frac{m}{n}, where mm and nn are relatively prime positive integers. Find m+nm+n.

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

Solution

Let x1x2x100x_1 \le x_2 \le \dots \le x_{100}, S=x1+x2++x100=0S = x_1 + x_2 + \dots + x_{100} = 0, and T=x1+x2++x100=1T = |x_1| + |x_2| + \dots + |x_{100}| = 1.

We want to maximize x76x16x_{76} - x_{16}.

Let kk be the number of negative xix_i's, and 100k100-k the number of nonnegative xix_i's. Since the sum is 00, the sum of the negative numbers equals the sum of the positive numbers in magnitude.

Let x1=x2==xk=ax_1 = x_2 = \dots = x_k = -a and xk+1=xk+2==x100=bx_{k+1} = x_{k+2} = \dots = x_{100} = b, with a,b0a, b \ge 0.

Then:

k(a)+(100k)b=0    (100k)b=ka    b=k100kak(-a) + (100-k)b = 0 \implies (100-k)b = ka \implies b = \frac{k}{100-k}a

Also,

ka+(100k)b=ka+(100k)b=1k|{-a}| + (100-k)|b| = ka + (100-k)b = 1

Substitute bb:

ka+(100k)(k100ka)=1ka + (100-k)\left(\frac{k}{100-k}a\right) = 1

ka+ka=1ka + k a = 1

2ka=1    a=12k2ka = 1 \implies a = \frac{1}{2k}

Then b=k100ka=k100k12k=12(100k)b = \frac{k}{100-k}a = \frac{k}{100-k} \cdot \frac{1}{2k} = \frac{1}{2(100-k)}

Now, x76x16x_{76} - x_{16}:

Since x1==xk=ax_1 = \dots = x_k = -a, xk+1==x100=bx_{k+1} = \dots = x_{100} = b.

The first kk entries are a-a, the next 100k100-k are bb.

x16x_{16} is a-a if k16k \ge 16, otherwise bb.

x76x_{76} is a-a if k76k \ge 76, otherwise bb.

We want to maximize x76x16x_{76} - x_{16}.

Case 1: k<16k < 16

Then x16=bx_{16} = b, x76=bx_{76} = b, so x76x16=0x_{76} - x_{16} = 0.

Case 2: 16k<7616 \le k < 76

Then x16=ax_{16} = -a, x76=bx_{76} = b, so x76x16=b(a)=a+bx_{76} - x_{16} = b - (-a) = a + b

Case 3: k76k \ge 76

Then x16=ax_{16} = -a, x76=ax_{76} = -a, so x76x16=0x_{76} - x_{16} = 0

So, the maximum occurs for 16k<7616 \le k < 76, and x76x16=a+b=12k+12(100k)x_{76} - x_{16} = a + b = \frac{1}{2k} + \frac{1}{2(100-k)}

Let f(k)=12k+12(100k)f(k) = \frac{1}{2k} + \frac{1}{2(100-k)} for 16k<7616 \le k < 76.

We want to maximize f(k)f(k).

Let’s write f(k)=100k+k2k(100k)=1002k(100k)f(k) = \frac{100 - k + k}{2k(100 - k)} = \frac{100}{2k(100 - k)}

So f(k)f(k) is maximized when k(100k)k(100 - k) is minimized for 16k<7616 \le k < 76.

k(100k)k(100 - k) is minimized at the endpoints, i.e., k=16k = 16 or k=75k = 75.

For k=16k = 16:

f(16)=10021684=10021344=1002688=25672f(16) = \frac{100}{2 \cdot 16 \cdot 84} = \frac{100}{2 \cdot 1344} = \frac{100}{2688} = \frac{25}{672}

For k=75k = 75:

f(75)=10027525=10021875=1003750=275f(75) = \frac{100}{2 \cdot 75 \cdot 25} = \frac{100}{2 \cdot 1875} = \frac{100}{3750} = \frac{2}{75}

Now, 256720.0372\frac{25}{672} \approx 0.0372, 2750.0267\frac{2}{75} \approx 0.0267, so 25672\frac{25}{672} is larger.

Therefore, the maximum is 25672\frac{25}{672}, so m=25m = 25, n=672n = 672, m+n=697m+n = 697.

Answer: 697697.

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.