Maths Olympiad Prep

Library / /29 of 43

Number theory Difficulty 6.1 National Olympiad Prove it JBMO

Problem:
Find the least positive integer such that the sum of its digits is 20112011 and the product of its digits is a power of 66.

Solution

Solution:
Denote this number by NN. Then NN can not contain the digits 0,5,70, 5, 7 and its digits must be written in increasing order. Suppose that NN has x1x_{1} ones, x2x_{2} twos, x3x_{3} threes, x4x_{4} fours, x6x_{6} sixes, x8x_{8} eights and x9x_{9} nines, then
x1+2x2+3x3+4x4+6x6+8x8+9x9=2011. x_{1} + 2x_{2} + 3x_{3} + 4x_{4} + 6x_{6} + 8x_{8} + 9x_{9} = 2011.
(1)

The product of digits of the number NN is a power of 66 when we have the relation
x2+2x4+x6+3x8=x3+x6+2x9, x_{2} + 2x_{4} + x_{6} + 3x_{8} = x_{3} + x_{6} + 2x_{9},
hence
x2x3+2x4+3x82x9=0. x_{2} - x_{3} + 2x_{4} + 3x_{8} - 2x_{9} = 0.
Denote by SS the number of digits of NN (S=x1+x2++x9S = x_{1} + x_{2} + \ldots + x_{9}). In order to make the coefficients of x8x_{8} and x9x_{9} equal, we multiply relation (1) by 55, then we add relation (2). We get
43x9+43x8+30x6+22x4+14x3+11x2+5x1=10055 43x_{9} + 43x_{8} + 30x_{6} + 22x_{4} + 14x_{3} + 11x_{2} + 5x_{1} = 10055
which gives
43S=10055+13x6+21x4+29x3+32x2+38x1. 43S = 10055 + 13x_{6} + 21x_{4} + 29x_{3} + 32x_{2} + 38x_{1}.
Then 10055+13x6+21x4+29x3+32x2+38x110055 + 13x_{6} + 21x_{4} + 29x_{3} + 32x_{2} + 38x_{1} is a multiple of 4343 not less than 1005510055. The least such number is 1006210062, but the relation 10062=10055+13x6+21x4+29x3+32x2+38x110062 = 10055 + 13x_{6} + 21x_{4} + 29x_{3} + 32x_{2} + 38x_{1} means that among x1,x2,,x6x_{1}, x_{2}, \ldots, x_{6} there is at least one positive, so
10062=10055+13x6+21x4+29x3+32x2+38x110055+13=10068 10062 = 10055 + 13x_{6} + 21x_{4} + 29x_{3} + 32x_{2} + 38x_{1} \geq 10055 + 13 = 10068
which is obviously false. The next multiple of 4343 is 1010510105 and from relation
10105=10055+13x6+21x4+29x3+32x2+38x1 10105 = 10055 + 13x_{6} + 21x_{4} + 29x_{3} + 32x_{2} + 38x_{1}
we get
50=13x6+21x4+29x3+32x2+38x1. 50 = 13x_{6} + 21x_{4} + 29x_{3} + 32x_{2} + 38x_{1}.
By writing as
13x6+21(x41)+29(x31)+32x2+38x1=0, 13x_{6} + 21(x_{4} - 1) + 29(x_{3} - 1) + 32x_{2} + 38x_{1} = 0,
we can easily see that the only possibility is x1=x2=x6=0x_{1} = x_{2} = x_{6} = 0 and x3=x4=1x_{3} = x_{4} = 1. Then S=235S = 235, x8=93x_{8} = 93, x9=140x_{9} = 140. Since SS is strictly minimal, we conclude that
N=3488893999140. N = 34\underbrace{88 \ldots 8}_{93}\underbrace{99 \ldots 9}_{140}.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.