Maths Olympiad Prep

Library / /11 of 18

Number theory Difficulty 6.6 National Olympiad Prove it Argentina

Let aa, bb, cc, dd be distinct positive integers such that aba^b divides bcb^c, bcb^c divides cdc^d and cdc^d divides dad^a.

a) Is it possible to determine which is the least one of the numbers aa, bb, cc, dd?

b) Is it possible to determine which is the greatest one of the numbers aa, bb, cc, dd?

Solution

a) The answer is yes, even under the weaker assumptions ab≤bca^b \le b^c, bc≤cdb^c \le c^d, cd≤dac^d \le d^a. The least number is bb.

We need the inequality nn>n+1n+1\sqrt[n]{n} > \sqrt[n+1]{n+1} which holds for all n≥3n \ge 3.
It is equivalent to (1+1n)n<n(1+\frac{1}{n})^n < n and can be obtained by standard induction. The base n=3n=3 is clear, and if (1+1n)n<n(1+\frac{1}{n})^n < n for some nn then
(1+1n+1)n+1<(1+1n)n(1+1n+1)<n(1+1n+1)<n+1. \left(1 + \frac{1}{n+1}\right)^{n+1} < \left(1 + \frac{1}{n}\right)^n \left(1 + \frac{1}{n+1}\right) < n \left(1 + \frac{1}{n+1}\right) < n + 1.
In particular m>n≥3m > n \ge 3 implies mn<nn\sqrt[n]{m} < \sqrt[n]{n}. We use this general inequality to prove the following claim:
If uu, vv, w∈Nw \in \mathbb{N} satisfy uv≤vwu^v \le v^w then w≥uw \ge u or w≥vw \ge v.
Suppose on the contrary that w<uw < u, w<vw < v and write uv≤vwu^v \le v^w as vv≥uw\sqrt[v]{v} \ge \sqrt[w]{u}. Now w<uw < u implies vv≥uw>ww\sqrt[v]{v} \ge \sqrt[w]{u} > \sqrt[w]{w}, which can hold only if w∈{1,2}w \in \{1,2\}. Indeed if w≥3w \ge 3 then v>w≥3v > w \ge 3, so the general inequality leads to the impossible vv<ww\sqrt[v]{v} < \sqrt[w]{w}. For w=2w = 2 the condition is uv≤v2u^v \le v^2. Because v>w=2v > w = 2, this gives v>u≥3v > u \ge 3. Therefore vv<uw\sqrt[v]{v} < \sqrt[w]{u} by the general inequality. On the other hand uw<2\sqrt[w]{u} < \sqrt{2}, so that vv<uw<u\sqrt[v]{v} < \sqrt[w]{u} < \sqrt{u}. However vv<u\sqrt[v]{v} < \sqrt{u} contradicts uv≤v2u^v \le v^2. Finally if w=1w = 1 then uv≤vu^v \le v. On the other hand u>1u > 1, hence uv≥2v>vu^v \ge 2^v > v for all v∈Nv \in \mathbb{N}. The claim is proven.
Given ab≤bca^b \le b^c, bc≤cdb^c \le c^d, cd≤dac^d \le d^a, we apply the claim to the triples (a,b,c)(a, b, c), (b,c,d)(b, c, d), (c,d,a)(c, d, a). Because aa, bb, cc, dd are distinct, the conclusion is that none of cc, dd and aa can be the least one among aa, bb, cc, dd. Therefore the least number is bb.

b) The answer is no. Both quadruples a=28a = 2^8, b=2b = 2, c=24c = 2^4, d=22d = 2^2 and a=28a = 2^8, b=2b = 2, c=24c = 2^4, d=29d = 2^9 satisfy the condition. The greatest number in the first is a=28a = 2^8; the greatest number in the second is d=29d = 2^9.

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.