Maths Olympiad Prep

Track / Stage 6 / 301 of 400 #1781 of 2444

Problem 1781

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 abbca^b \le b^c, bccdb^c \le c^d, cddac^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 n3n \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>n3m > 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, wNw \in \mathbb{N} satisfy uvvwu^v \le v^w then wuw \ge u or wvw \ge v.
Suppose on the contrary that w<uw < u, w<vw < v and write uvvwu^v \le v^w as vvuw\sqrt[v]{v} \ge \sqrt[w]{u}. Now w<uw < u implies vvuw>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 w3w \ge 3 then v>w3v > 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 uvv2u^v \le v^2. Because v>w=2v > w = 2, this gives v>u3v > 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 uvv2u^v \le v^2. Finally if w=1w = 1 then uvvu^v \le v. On the other hand u>1u > 1, hence uv2v>vu^v \ge 2^v > v for all vNv \in \mathbb{N}. The claim is proven.
Given abbca^b \le b^c, bccdb^c \le c^d, cddac^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.