Maths Olympiad Prep

Library / /175 of 264

Number theory Difficulty 6.1 National Olympiad Prove it Romania

Find the smallest integer nn for which the set A={n,n+1,n+2,,2n}A = \{n, n+1, n+2, \dots, 2n\} contains five elements a<b<c<d<ea < b < c < d < e so that
ac=bd=ce. \frac{a}{c} = \frac{b}{d} = \frac{c}{e}.

Solution

Let p,qNp, q \in \mathbb{N}^*, (p,q)=1(p, q) = 1 so that ac=bd=ce=pq\frac{a}{c} = \frac{b}{d} = \frac{c}{e} = \frac{p}{q}. Obviously, p<qp < q. Since a,ba, b and cc are divisible by pp and c,d,ec, d, e are divisible by qq, there exists mNm \in \mathbb{N}^* so that c=mpqc = mpq.
Let us find the minimal value of the difference eae - a, for given p,qp, q. This is obtained when a,b,ca, b, c are consecutive multiples of pp and c,d,ec, d, e are consecutive multiples of qq, that is a=mpq2pa = mpq - 2p and e=mpq+2qe = mpq + 2q. From ce=mpqmpq+2q=pq\frac{c}{e} = \frac{mpq}{mpq+2q} = \frac{p}{q} follows m(qp)=2m(q-p) = 2, hence m{1,2}m \in \{1, 2\}.
Condition na<e2n2an \le a < e \le 2n \le 2a implies 2ae2a \ge e, that is 2mpq4pmpq+2q2mpq - 4p \ge mpq + 2q, or mpq4p+2qmpq \ge 4p + 2q. (*)
If m=1m = 1, then qp=2q - p = 2, hence q=p+2q = p + 2. Relation (*) yields (p2)28(p-2)^2 \ge 8, whence p5p \ge 5. For p=5p = 5 and q=7q = 7 we get a=25a = 25, b=30b = 30, c=35c = 35, d=42d = 42, e=49e = 49 and, since na<e2nn \le a < e \le 2n, n=25n = 25.
If m=2m = 2, then qp=1q - p = 1, so q=p+1q = p + 1. Relation (*) yields (p1)22(p-1)^2 \ge 2, whence p3p \ge 3. For p=3p = 3 and q=4q = 4 we get a=18a = 18, b=21b = 21, c=24c = 24, d=28d = 28, e=32e = 32 and, since na<e2nn \le a < e \le 2n, n{16,17,18}n \in \{16, 17, 18\}. Therefore, nmin=16n_{\min} = 16.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.