Maths Olympiad Prep

Library / Saudi Arabia booklet /1 of 13

Saudi Arabia booklet, 2024

Combinatorics Difficulty 4.6 AIME Prove it Saudi Arabia

With positive integer n>1n > 1, let 4n−34n - 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 nn times.

Solution

Let dd be the number of distinct values appear on the table, let them be
a1<a2<⋯<ad. a_1 < a_2 < \dots < a_d.
Assuming by contradiction that no value appears at least nn times, then each value appears at most n−1n-1 times. So we can count the amount of numbers on the board to get
4n−3≤d(n−1)  ⟹  d≥4n−3n−1  ⟹  d≥5. 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<ea < b < c < d < e. According to the assumption, (a,b,c,d)(a, b, c, d) and (a,b,c,e)(a, b, c, e) both form arithmetic progressions. Then, we have b−a=d−c=e−cb - a = d - c = e - c, implies that d=ed = e, which is clearly a contradiction. □\square

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.