Maths Olympiad Prep

Track / Stage 6 / 301 of 400 #1941 of 2604

Problem 1941

National Olympiad, first round
Number theory Difficulty 6.6 Prove it Mathematical Olympiad Rioplatense · 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?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official 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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.