Difference between revisions of "2006 Indonesia MO Problems/Problem 8"
Rockmanex3 (talk | contribs) (Solution to Problem 8 (credit to Rust) -- 85 digit number problem) |
Rockmanex3 (talk | contribs) m |
||
| Line 38: | Line 38: | ||
We found one working case where <math>a_1 = 8</math>. If <math>a_1 \le 7</math>, then the numbers are smaller, so the largest 85-digit number where the sum of the digits equals the product of the digits is <math>\boxed{8322\underbrace{111 \cdots 1}_{81\text{ ones}}}</math>. | We found one working case where <math>a_1 = 8</math>. If <math>a_1 \le 7</math>, then the numbers are smaller, so the largest 85-digit number where the sum of the digits equals the product of the digits is <math>\boxed{8322\underbrace{111 \cdots 1}_{81\text{ ones}}}</math>. | ||
| − | ==Python Code== | + | ===Python Code=== |
| − | Although Python programs are not allowed in the [[Indonesia Mathematical Olympiad|Indonesia MO]], we can run a computer program that prints out the first 7 digits of all numbers where <math>a_n = 1</math> for <math>8 \le n \le 85</math>. | + | Although Python programs are not allowed in the [[Indonesia Mathematical Olympiad|Indonesia MO]], we can run a computer program that prints out the first 7 digits of all numbers where the product of the digits equals the sum of the digits and <math>a_n = 1</math> for <math>8 \le n \le 85</math>. |
number = [1,1,1,1,1,1,1] | number = [1,1,1,1,1,1,1] | ||
Latest revision as of 21:48, 23 September 2018
Contents
Problem
Find the largest 85-digit integer which has property: the sum of its digits equals to the product of its digits.
Solution
Let 
be the 
digit from the left, where 
. Because we want to maximize the number, we let 
for 
.
First we'll prove that 
. Afterward, we'll find the largest value of 
and use it to find the 85-digit integer.
Lemma 1:
The sum of the digits of the 85-digit number is at most 
. If we let 
, then the product of the digits is at least 
, which is more than 
. That means 
.
Since 
are all equal to 1, the sum of the digits of the wanted 85-digit number is at most 
. If we let 
, then the product of the digits is at least 
, which is more than 
. That means 
Now we'll consider the largest possible values for . From the Lemma, there are at least 
ones, so the sum (and product) is at least 
and at most 
Case: 
If , then the possible products are 
since the prime factorization only consists of prime numbers less than 10.
- If the product of the digits is 90, then
and 
. However, the sum of the digits would be 
, so the product can not be 90. - If the product of the digits is 108, then
. This can be achieved if 
and , 
and 
, or 
and 
. The first case results in a sum of 
, the second case results in a sum of 
, and the third case results in a sum of 
. Thus, the product can not be 108. - If the product of the digits is 126, then
and . However, the sum of the digits would be 
, so the product can not be 126. - If the product of the digits is 135, then and . However, the sum of the digits would be
, so the product can not be 135.
and 
. However, the sum of the digits would be 
, so the product can not be 90.
. This can be achieved if 
and 
and 
, or 
and 
. The first case results in a sum of 
, the second case results in a sum of 
, and the third case results in a sum of 
. Thus, the product can not be 108.
and 
, so the product can not be 126.
, so the product can not be 135.From all the cases, can not equal 9.
Case: 
If , then the possible products are 
since the prime factorization only consists of prime numbers less than 10.
- If the product of the digits is
, then . This can be achieved if and , and , or and . The first case results in 
and the second case results in 
. However, the third case results in 
, which works. - If the product of the digits is
, then and . However, the sum of the digits is 
, so the product can not equal 112. - If the product of the digits is
, then and . However, the sum of the digits is 
, so the product can not equal 120. - If the product of the digits is
, then 
. This can be achieved if 
and , 
, and , or 
. The first case results in a sum of 
, the second case results in a sum of 
, the third case results in a sum of 
, and the fourth case results in 
. Thus, the product can not be 128.
, then 
and the second case results in 
. However, the third case results in 
, which works.
, then 
, so the product can not equal 112.
, then 
, so the product can not equal 120.
, then 
. This can be achieved if 
and 
, 
. The first case results in a sum of 
, the second case results in a sum of 
, the third case results in a sum of 
, and the fourth case results in 
. Thus, the product can not be 128.We found one working case where . If 
, then the numbers are smaller, so the largest 85-digit number where the sum of the digits equals the product of the digits is 
.
Python Code
Although Python programs are not allowed in the Indonesia MO, we can run a computer program that prints out the first 7 digits of all numbers where the product of the digits equals the sum of the digits and 
for 
.
number = [1,1,1,1,1,1,1]
for i in range(0,8888889): #Number of iterations
number[6] += 1 #Adds one to a_7
for j in range(0,6): #Regroups if necessary
if number[6-j] == 10:
number[6-j] = 0
number[5-j] += 1
s = 78 #Sum of numbers from a_8 to a_85
for k in number: #Calculate sum
s += k
product = 1 #Product of numbers from a_8 to a_85
for n in number: #Calculate product
product *= n
if s == product: #Checks if sum equals product
print(number)
The computer program verifies that the largest 85-digit number that meets the criteria is .
See Also
| 2006 Indonesia MO (Problems) | ||
| Preceded by Problem 7 |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 | Followed by Last Problem |
| All Indonesia MO Problems and Solutions | ||
