Maths Olympiad Prep

Library / /132 of 520

Number theory Difficulty 5.9 AIME, harder Find the answer

Find the least positive integer such that the sum of its digits is 2011 and the product of its digits is a power of 6.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solutions — 2

Solution 1

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=2011x_{1}+2 x_{2}+3 x_{3}+4 x_{4}+6 x_{6}+8 x_{8}+9 x_{9}=2011. (1) The product of digits of the number NN is a power of 6 when we have the relation x2+2x4+x6+3x8=x3+x6+2x9x_{2}+2 x_{4}+x_{6}+3 x_{8}=x_{3}+x_{6}+2 x_{9}, hence x2x3+2x4+3x82x9=0x_{2}-x_{3}+2 x_{4}+3 x_{8}-2 x_{9}=0.

Denote by SS the number of digits of N(S=x1+x2++x9)N\left(S=x_{1}+x_{2}+\ldots+x_{9}\right). In order to make the coefficients of x8x_{8} and x9x_{9} equal, we multiply relation (1) by 5, then we add relation (2). We get 43x9+43x8+30x6+22x4+14x3+11x2+5x1=1005543S=10055+13x6+43 x_{9}+43 x_{8}+30 x_{6}+22 x_{4}+14 x_{3}+11 x_{2}+5 x_{1}=10055 \Leftrightarrow 43 S=10055+13 x_{6}+ 21x4+29x3+32x2+38x121 x_{4}+29 x_{3}+32 x_{2}+38 x_{1}. Then 10055+13x6+21x4+29x3+32x2+38x110055+13 x_{6}+21 x_{4}+29 x_{3}+32 x_{2}+38 x_{1} is a multiple of 43 not less than 10055. The least such number is 10062, but the relation 10062=10062= 10055+13x6+21x4+29x3+32x2+38x110055+13 x_{6}+21 x_{4}+29 x_{3}+32 x_{2}+38 x_{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=1006810062=10055+13 x_{6}+21 x_{4}+29 x_{3}+32 x_{2}+38 x_{1} \geq 10055+13=10068 which is obviously false. The next multiple of 43 is 10105 and from relation 10105=10105= 10055+13x6+21x4+29x3+32x2+38x110055+13 x_{6}+21 x_{4}+29 x_{3}+32 x_{2}+38 x_{1} we get 50=13x6+21x4+29x3+32x2+38x150=13 x_{6}+21 x_{4}+29 x_{3}+32 x_{2}+38 x_{1}. By writing as 13x6+21(x41)+29(x31)+32x2+38x1=013 x_{6}+21\left(x_{4}-1\right)+29\left(x_{3}-1\right)+32 x_{2}+38 x_{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=235,x8=93,x9=140S=235, x_{8}=93, x_{9}=140. Since SS is strictly minimal, we conclude that N=3488893999140N=34 \underbrace{88 \ldots 8}_{93} \underbrace{99 \ldots 9}_{140}.

Solution 2

To 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, we need to follow these steps:

1. Understand the constraints:
- The sum of the digits must be 20112011.
- The product of the digits must be a power of 66.

2. **Express the product as a power of 66**:
- A power of 66 can be written as 6k6^k, where 6=2×36 = 2 \times 3.
- Therefore, the product of the digits must have the form 2k×3k2^k \times 3^k.

3. Maximize the digits to minimize the number of digits:
- Use the largest digits possible (i.e., 99 and 88) to minimize the number of digits.
- Note that 9=329 = 3^2 and 8=238 = 2^3.

4. **Balance the use of 99s and 88s**:
- Each 99 contributes 99 to the sum and 323^2 to the product.
- Each 88 contributes 88 to the sum and 232^3 to the product.
- To balance the powers of 22 and 33, we need 33 99s for every 22 88s, since 3×9=273 \times 9 = 27 and 2×8=162 \times 8 = 16, and 27×16=43227 \times 16 = 432, which is a power of 66.

5. **Calculate the number of 99s and 88s**:
- We need to find the number of 99s and 88s such that their sum is 20112011.
- Let xx be the number of 99s and yy be the number of 88s.
- We have the equation 9x+8y=20119x + 8y = 2011.

6. **Solve for xx and yy**:
- We need to find integer solutions for xx and yy such that xx and yy are minimized.
- Since 33 99s and 22 88s are used together, we can write x=3kx = 3k and y=2ky = 2k for some integer kk.
- Substituting into the sum equation: 9(3k)+8(2k)=20119(3k) + 8(2k) = 2011.
- Simplifying: 27k+16k=201127k + 16k = 2011.
- 43k=201143k = 2011.
- Solving for kk: k=201143=46+3343k = \frac{2011}{43} = 46 + \frac{33}{43}.

7. Adjust for the remainder:
- Since k=46k = 46 with a remainder of 3333, we need to adjust the digits to account for the remaining sum of 3333.
- The smallest number of digits that sum to 3333 and maintain the product as a power of 66 is 3489934899.

8. Construct the final number:
- The final number will have 46×2+1=9346 \times 2 + 1 = 93 88s and 46×3+2=14046 \times 3 + 2 = 140 99s.
- The number is 3488888888999999993488888\ldots8889999\ldots9999.

The final answer is 348888888899999999\boxed{3488888\ldots8889999\ldots9999}.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.