Maths Olympiad Prep

Library / /5 of 39

Algebra Difficulty 4.7 AIME Prove it Ireland

Let SS be a set of n>1n > 1 distinct integers and suppose that
T={x+y:xy,x,yS} T = \{x + y : x \neq y, x, y \in S\}
has exactly 2n32n - 3 distinct elements. Prove that, when arranged in increasing order, the elements of SS form an arithmetic progression.

Solution

Write S={x1,,xn}S = \{x_1, \dots, x_n\} where x1<<xnx_1 < \dots < x_n. The 2n32n-3 elements
x1+x2<<x1+xn<x2+xn<x3+xn<<xn1+xn x_1 + x_2 < \dots < x_1 + x_n < x_2 + x_n < x_3 + x_n < \dots < x_{n-1} + x_n
account for all the elements of TT. Now x2+xn1x_2 + x_{n-1} lies between x1+xn1x_1 + x_{n-1} and x2+xnx_2 + x_n, so it must be x1+xnx_1 + x_n. So x2x1=xnxn1=dx_2 - x_1 = x_n - x_{n-1} = d, say. Proceeding by induction, having shown that xixi1=dx_i - x_{i-1} = d, for some 2i<n12 \le i < n-1, observe that xi+1+xn1x_{i+1} + x_{n-1} lies between xi+xn1=xi1+xnx_i + x_{n-1} = x_{i-1} + x_n and xi+1+xnx_{i+1} + x_n, so xi+1+xn1=xi+xnx_{i+1} + x_{n-1} = x_i + x_n, giving xi+1xi=dx_{i+1} - x_i = d.

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.