Maths Olympiad Prep

Library / /14 of 27

Number theory Difficulty 5.6 AIME, harder Prove it Austria

Determine all triples (x,y,z)(x, y, z) of positive integers satisfying
x(y+1),y(z+1)andz(x+1). x \mid (y+1), \quad y \mid (z+1) \quad \text{and} \quad z \mid (x+1).

Solution

Answer. There are ten triples satisfying the three conditions. They are given by (1,1,1)(1, 1, 1), (1,1,2)(1, 1, 2), (1,3,2)(1, 3, 2), (3,5,4)(3, 5, 4) and their cyclic permutations.

Without loss of generality, let xx be the smallest of the three numbers (or one of the smallest), i.e. xyx \le y and xzx \le z. From zx+1z \mid x + 1 we obtain xzx+1x \le z \le x + 1. Thus we have to consider two cases.

* Case 1. Let z=xz = x. Then z=xx+1z = x \mid x + 1 leads to x=z=1x = z = 1 and yz+1=2y \mid z + 1 = 2. Therefore y=1y = 1 or y=2y = 2, and we get the two solutions (1,1,1)(1, 1, 1) and (1,2,1)(1, 2, 1).

* Case 2. Let z=x+1z = x + 1. Then the two conditions xy+1x \mid y + 1 and yx+2y \mid x + 2 must be fulfilled. In particular, we obtain xy+1x \le y + 1 and yx+2y \le x + 2. This yields x1yx+2x - 1 \le y \le x + 2 and we have to examine the following cases for yy.

* Case 2a. Let 0<y=x0 < y = x. The conditions xx+1x \mid x + 1 and xx+2x \mid x + 2 can only hold simultaneously for x=1x = 1, giving the solution (1,1,2)(1, 1, 2).

* Case 2b. Let y=x+1y = x + 1. Then the two conditions are xx+2x \mid x + 2 and x+1x+2x + 1 \mid x + 2. They cannot hold simultaneously.

* Case 2c. Let y=x+2y = x + 2. The condition y=x+2x+2=z+1y = x + 2 \mid x + 2 = z + 1 is trivially fulfilled. The requirement xy+1=x+3x \mid y + 1 = x + 3 can only hold for x3x \mid 3. And, indeed, for either x=1x = 1 or x=3x = 3 the condition is fulfilled and we obtain the solutions (1,3,2)(1, 3, 2) and (3,5,4)(3, 5, 4).

Summing up, the triples (1,1,1)(1, 1, 1), (1,2,1)(1, 2, 1), (1,1,2)(1, 1, 2), (1,3,2)(1, 3, 2) and (3,5,4)(3, 5, 4) fulfill all three conditions. As each of the three numbers can be the minimum, every cyclic permutation of these triples is a solution as well.

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.