Competition problem — Combinatorics

Library / /1 of 18

Combinatorics Difficulty 4.7 AIME Prove it China

Given two integers $m, n$ greater than $1$ , and integers $a_1 < a_2 < \cdots < a_m$ , prove that there exists a set $T$ of integers with $|T| \le 1 + \frac{a_m - a_1}{2n + 1}$ such that each $a_i$ can be written as $a_i = t + s$ for some $t \in T$ , and $s \in [-n, n]$ . (Posed by Leng Gangsong)

Solution

Write $a_1 = a$ , $a_m = b$ , $b - a = (2n + 1)q + r$ , where $q, r \in \mathbb{Z}$ and $0 \le r \le 2n$ . Take

$T = \{a + n + (2n + 1)k \mid k = 0, 1, \dots, q\}.$

Then $|T| = q + 1 \le 1 + \frac{b - a}{2n + 1}$ . We have the set

$B = \{t + s \mid t \in T, s = -n, -n + 1, \dots, n\} = \{a, a + 1, \dots, a + (2n + 1)q + 2n\}.$

Note that $a + (2n + 1)q + 2n \ge a + (2n + 1)q + r = b$ , so each $a_i$ belongs to $B$ .

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.