Maths Olympiad Prep

Library / /48 of 82

Number theory Difficulty 5.7 AIME, harder Prove it Croatia

Find all positive integers nn such that
a!+b!+c!=2n a! + b! + c! = 2^n
for some positive integers a,b,ca, b, c.

Solution

Without loss of generality, assume abca \leq b \leq c.

If c6c \geq 6, then c!c! is divisible by 24=162^4 = 16, and a!a! and b!b! are also divisible by 22 for a,b2a, b \geq 2. Thus, a!+b!+c!a! + b! + c! is divisible by 22, but for c6c \geq 6, c!c! is divisible by 88 and higher powers of 22.

Let us check small values of cc:

If c=1c = 1:
a!+b!+1!=2na! + b! + 1! = 2^n
But a,b1a, b \leq 1, so a=b=1a = b = 1.
1!+1!+1!=1+1+1=31! + 1! + 1! = 1 + 1 + 1 = 3, which is not a power of 22.

If c=2c = 2:
a!+b!+2!=a!+b!+2=2na! + b! + 2! = a! + b! + 2 = 2^n
a,b2a, b \leq 2
Try a=1,b=1a = 1, b = 1: 1+1+2=4=221 + 1 + 2 = 4 = 2^2
So n=2n = 2 is a solution with (a,b,c)=(1,1,2)(a, b, c) = (1, 1, 2) (and permutations).

Try a=1,b=2a = 1, b = 2: 1+2+2=51 + 2 + 2 = 5
a=2,b=2a = 2, b = 2: 2+2+2=62 + 2 + 2 = 6
No other powers of 22.

If c=3c = 3:
a!+b!+6=2na! + b! + 6 = 2^n, a,b3a, b \leq 3
a=1,b=1a = 1, b = 1: 1+1+6=8=231 + 1 + 6 = 8 = 2^3
So n=3n = 3 is a solution with (a,b,c)=(1,1,3)(a, b, c) = (1, 1, 3) (and permutations).

a=1,b=2a = 1, b = 2: 1+2+6=91 + 2 + 6 = 9
a=1,b=3a = 1, b = 3: 1+6+6=131 + 6 + 6 = 13
a=2,b=2a = 2, b = 2: 2+2+6=102 + 2 + 6 = 10
a=2,b=3a = 2, b = 3: 2+6+6=142 + 6 + 6 = 14
a=3,b=3a = 3, b = 3: 6+6+6=186 + 6 + 6 = 18
No other powers of 22.

If c=4c = 4:
4!=244! = 24
a,b4a, b \leq 4
a=1,b=1a = 1, b = 1: 1+1+24=261 + 1 + 24 = 26
a=1,b=2a = 1, b = 2: 1+2+24=271 + 2 + 24 = 27
a=1,b=3a = 1, b = 3: 1+6+24=311 + 6 + 24 = 31
a=1,b=4a = 1, b = 4: 1+24+24=491 + 24 + 24 = 49
a=2,b=2a = 2, b = 2: 2+2+24=282 + 2 + 24 = 28
a=2,b=3a = 2, b = 3: 2+6+24=32=252 + 6 + 24 = 32 = 2^5
So n=5n = 5 is a solution with (a,b,c)=(2,3,4)(a, b, c) = (2, 3, 4) (and permutations).

a=2,b=4a = 2, b = 4: 2+24+24=502 + 24 + 24 = 50
a=3,b=3a = 3, b = 3: 6+6+24=366 + 6 + 24 = 36
a=3,b=4a = 3, b = 4: 6+24+24=546 + 24 + 24 = 54
a=4,b=4a = 4, b = 4: 24+24+24=7224 + 24 + 24 = 72

If c=5c = 5:
5!=1205! = 120
a,b5a, b \leq 5
a=1,b=1a = 1, b = 1: 1+1+120=1221 + 1 + 120 = 122
a=1,b=2a = 1, b = 2: 1+2+120=1231 + 2 + 120 = 123
a=1,b=3a = 1, b = 3: 1+6+120=1271 + 6 + 120 = 127
a=1,b=4a = 1, b = 4: 1+24+120=1451 + 24 + 120 = 145
a=1,b=5a = 1, b = 5: 1+120+120=2411 + 120 + 120 = 241
a=2,b=2a = 2, b = 2: 2+2+120=1242 + 2 + 120 = 124
a=2,b=3a = 2, b = 3: 2+6+120=128=272 + 6 + 120 = 128 = 2^7
So n=7n = 7 is a solution with (a,b,c)=(2,3,5)(a, b, c) = (2, 3, 5) (and permutations).

a=2,b=4a = 2, b = 4: 2+24+120=1462 + 24 + 120 = 146
a=2,b=5a = 2, b = 5: 2+120+120=2422 + 120 + 120 = 242
a=3,b=3a = 3, b = 3: 6+6+120=1326 + 6 + 120 = 132
a=3,b=4a = 3, b = 4: 6+24+120=1506 + 24 + 120 = 150
a=3,b=5a = 3, b = 5: 6+120+120=2466 + 120 + 120 = 246
a=4,b=4a = 4, b = 4: 24+24+120=16824 + 24 + 120 = 168
a=4,b=5a = 4, b = 5: 24+120+120=26424 + 120 + 120 = 264
a=5,b=5a = 5, b = 5: 120+120+120=360120 + 120 + 120 = 360

For c6c \geq 6, c!c! is divisible by 1616, and a!+b!a! + b! is much smaller than c!c!, so a!+b!+c!a! + b! + c! cannot be a power of 22.

Therefore, the possible values of nn are 2,3,5,72, 3, 5, 7.

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.