Maths Olympiad Prep

Library / /3 of 4

Number theory Difficulty 7.1 National olympiad, round 2 Prove it Vietnam

Find all triples of natural numbers (x,y,n)(x, y, n) satisfying the relation
x!+y!n!=3n \frac{x! + y!}{n!} = 3^n
(with the convention 0!=10! = 1).

Solution

The relation in the problem can be written in the form
x!+y!=3nn!(1) x! + y! = 3^n n! \quad (1)
Suppose that (x,y,n)(x, y, n) is a triple of natural numbers satisfying (1).
It is easily seen that n1n \ge 1 and w.l.g. we can suppose that xyx \le y. We must now consider the following cases.

1) 1st case: xnx \le n
It is clear that (1)1+y!x!=3nn!x!.(2) \text{It is clear that } (1) \Leftrightarrow 1 + \frac{y!}{x!} = 3^n \frac{n!}{x!}. \qquad (2)
(2) implies that 1+y!x!0(mod3)1 + \frac{y!}{x!} \equiv 0 \pmod{3}. Since the product of three consecutive integers is divisible by 3 and since n1n \ge 1, we have: x<yx+2x < y \le x + 2.

a) If y=x+2y = x + 2, (2) implies
1+(x+1)(x+2)=3nn!x!(3) 1 + (x + 1)(x + 2) = 3^n \frac{n!}{x!} \qquad (3)
Since the product of two consecutive integers is divisible by 2, from (3), we deduce that nx+1n \le x + 1.
- If n=xn = x, (3) implies
1+(x+1)(x+2)=3x,i.e. x2+3x+3=3x(4) 1 + (x + 1)(x + 2) = 3^x, \quad \text{i.e. } x^2 + 3x + 3 = 3^x \qquad (4)
Since x1x \ge 1, (4) shows that x0(mod3)x \equiv 0 \pmod{3}, therefore x3x \ge 3 and we get a contradiction
3=x2+3x3x0(mod9) 3 = x^2 + 3x - 3^x \equiv 0 \pmod{9}
which proves that nxn \ne x.
- If n=x+1n = x + 1, (3) implies that
1+(x+1)(x+2)=3n(x+1) 1 + (x + 1)(x + 2) = 3^n(x + 1)
hence x+1x + 1 is a positive divisor of 1. Therefore x=0x = 0 and consequently y=2,n=1y = 2, n = 1.

b) If y=x+1y = x + 1, (2) implies
x+2=3nn!x!(5) x + 2 = 3^n \frac{n!}{x!} \qquad (5)
Since x1x \ge 1, (5) shows that x1x \ge 1 and then x=nx = n and
x+2=3x.(6) x + 2 = 3^x. \qquad (6)
x=1x = 1 is the unique natural number satisfying (6) therefore, in this case, if the triples (x,y,n)(x, y, n) satisfy (1) then (x,y,n)=(0,2,1)(x, y, n) = (0, 2, 1) or (x,y,n)=(1,2,1)(x, y, n) = (1, 2, 1).

2) 2nd case: x>nx > n.
It is clear that
(1)x!n!+y!n!=3n.(7) (1) \Leftrightarrow \frac{x!}{n!} + \frac{y!}{n!} = 3^n. \qquad (7)
Since n+1n + 1 and n+2n + 2 can not be simultaneously the powers of 3, from (7), we deduce that x=n+1x = n + 1. Then (2) implies that
n+1+y!n!=3n.(8) n + 1 + \frac{y!}{n!} = 3^n. \qquad (8)
Since yxy \ge x, we see that yn+1y \ge n + 1. By putting A=y!(n+1)!A = \frac{y!}{(n+1)!}, we can write (8) in the form
(n+1)(1+A)=3n.(9) (n + 1)(1 + A) = 3^n. \qquad (9)
It is clear that if yn+4y \ge n + 4 then A0mod3A \equiv 0 \mod 3, and A+1A + 1 can not be a power of 3. Hence (9) shows that yn+3y \le n + 3.
So n+1yn+3n + 1 \le y \le n + 3.

a) If y=n+3y = n + 3 then A=(n+2)(n+3)A = (n + 2)(n + 3), and from (9) we get
(n+1)(1+(n+2)(n+3))=3n i.e. (n+2)31=3n.(10) (n + 1)(1 + (n + 2)(n + 3)) = 3^n \text{ i.e. } (n + 2)^3 - 1 = 3^n. \qquad (10)
It follows that n>2n > 2 and n+2=1mod3n + 2 = 1 \mod 3. By putting n+2=3k+1,k>2n + 2 = 3k + 1, k > 2, we can write (10) in the form
9k(3k2+3k+1)=33k1. 9k(3k^2 + 3k + 1) = 3^{3k-1}.
It implies that 3k2+3k+13k^2 + 3k + 1 is a power of 3. This contradiction proves that yn+3y \ne n + 3.

b) If y=n+2y = n + 2 then A=n+2A = n + 2 and from (9) we get
(n+1)(n+3)=3n.(11) (n + 1)(n + 3) = 3^n. \qquad (11)

c) If y=n+1y = n + 1 then A=1A = 1 and from (9) we get
2(n+1)=3n. 2(n + 1) = 3^n.
It is clear that there exist no nn satisfying this relation. So yn+1y \ne n + 1.

Thus, if the triple (x,y,n)(x, y, n), with xyx \le y, satisfies (1) then nxn \ge x.
Consequently, if (x,y,n)(x, y, n) is a triple of natural numbers satisfying (1) then (x,y,n)=(0,2,1)(x, y, n) = (0, 2, 1) or (x,y,n)=(2,0,1)(x, y, n) = (2, 0, 1), or (x,y,n)=(2,1,0)(x, y, n) = (2, 1, 0), or (x,y,n)=(2,1,1)(x, y, n) = (2, 1, 1).
By direct verification, we see that the four mentioned triples satisfy (1). So these triples are all triples satisfying the conditions of the problem.

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.