Maths Olympiad Prep

Library / Irish Mathematical Olympiad /27 of 236

Irish Mathematical Olympiad

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:x≠y,x,y∈S} T = \{x + y : x \neq y, x, y \in S\}
has exactly 2n−32n - 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 2n−32n-3 elements
x1+x2<⋯<x1+xn<x2+xn<x3+xn<⋯<xn−1+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+xn−1x_2 + x_{n-1} lies between x1+xn−1x_1 + x_{n-1} and x2+xnx_2 + x_n, so it must be x1+xnx_1 + x_n. So x2−x1=xn−xn−1=dx_2 - x_1 = x_n - x_{n-1} = d, say. Proceeding by induction, having shown that xi−xi−1=dx_i - x_{i-1} = d, for some 2≤i<n−12 \le i < n-1, observe that xi+1+xn−1x_{i+1} + x_{n-1} lies between xi+xn−1=xi−1+xnx_i + x_{n-1} = x_{i-1} + x_n and xi+1+xnx_{i+1} + x_n, so xi+1+xn−1=xi+xnx_{i+1} + x_{n-1} = x_i + x_n, giving xi+1−xi=dx_{i+1} - x_i = d.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.