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

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 and solution reproduced as published; topic and difficulty added by this site.