Library / /1 of 16

, 2024

Combinatorics Difficulty 4.6 AIME Prove it Saudi Arabia

With positive integer $n > 1$ , let $4n - 3$ positive numbers are written on the board (not necessarily all different). It is known that any 4 pairwise different numbers from that list form an arithmetic progression. Prove that some number is written on the board at least $n$ times.

Solution

Let $d$ be the number of distinct values appear on the table, let them be
$a_1 < a_2 < \dots < a_d.$
Assuming by contradiction that no value appears at least $n$ times, then each value appears at most $n-1$ times. So we can count the amount of numbers on the board to get
$4n - 3 \le d(n - 1) \implies d \ge \frac{4n - 3}{n - 1} \implies d \ge 5.$
Consider the 5 arbitrary distinct values among them, denoted by $a < b < c < d < e$ . According to the assumption, $(a, b, c, d)$ and $(a, b, c, e)$ both form arithmetic progressions. Then, we have $b - a = d - c = e - c$ , implies that $d = e$ , which is clearly a contradiction. $\square$

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.