Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2006 Indonesia MO Problems/Problem 8

Problem

Find the largest 85-digit integer which has property: the sum of its digits equals to the product of its digits.

Solution

Let $a_n$ be the $n^\text{th}$ digit from the left, where $1 \le n \le 85$. Because we want to maximize the number, we let $a_n \ge a_{n+1}$ for $1 \le n \le 84$.


First we'll prove that $a_8 = 1$. Afterward, we'll find the largest value of $a_1$ and use it to find the 85-digit integer.


Lemma 1: $a_8 = 1$
The sum of the digits of the 85-digit number is at most $85 \cdot 9 = 765$. If we let $a_10 = 2$, then the product of the digits is at least $1024$, which is more than $765$. That means $a_{10} = 1$.


Since $a_{10}, a_{11}, \cdots a_{85}$ are all equal to 1, the sum of the digits of the wanted 85-digit number is at most $76 + 9 \cdot 9 = 157$. If we let $a_8 = 2$, then the product of the digits is at least $256$, which is more than $157$. That means $a_8 = 1. \blacktriangleright$


Now we'll consider the largest possible values for $a_1$. From the Lemma, there are at least $78$ ones, so the sum (and product) is at least $85$ and at most $78 + 9 \cdot 7 = 141.$


Case: $a_1 = 9$
If $a_1 = 9$, then the possible products are $90, 108, 126, 135$ since the prime factorization only consists of prime numbers less than 10.

  • If the product of the digits is 90, then $a_2 = 5$ and $a_3 = 2$. However, the sum of the digits would be $82 + 9 + 5 + 2 = 98$, so the product can not be 90.
  • If the product of the digits is 108, then $\prod_{i=2}^7 a_i = 12$. This can be achieved if $a_2 = 6$ and $a_3 = 2$, $a_2 = 4$ and $a_3 = 3$, or $a_2 = 3$ and $a_3 = a_4 = 2$. The first case results in a sum of $82 + 9 + 6 + 2 = 99$, the second case results in a sum of $82 + 9 + 4 + 3 = 98$, and the third case results in a sum of $81 + 9 + 3 + 2 + 2 = 97$. Thus, the product can not be 108.
  • If the product of the digits is 126, then $a_2 = 7$ and $a_3 = 2$. However, the sum of the digits would be $82 + 9 + 7 + 2 = 100$, so the product can not be 126.
  • If the product of the digits is 135, then $a_2 = 5$ and $a_3 = 3$. However, the sum of the digits would be $82 + 9 + 5 + 3 = 99$, so the product can not be 135.

From all the cases, $a_1$ can not equal 9.


Case: $a_1 = 8$
If $a_1 = 8$, then the possible products are $96, 112, 120, 128$ since the prime factorization only consists of prime numbers less than 10.

  • If the product of the digits is $96$, then $\prod_{i=2}^7 a_i = 12$. This can be achieved if $a_2 = 6$ and $a_3 = 2$, $a_2 = 4$ and $a_3 = 3$, or $a_2 = 3$ and $a_3 = a_4 = 2$. The first case results in $82 + 8 + 6 + 2 = 98$ and the second case results in $82 + 8 + 4 + 3 = 97$. However, the third case results in $81 + 8 + 3 + 2 + 2 = 96$, which works.
  • If the product of the digits is $112$, then $a_2 = 7$ and $a_3 = 2$. However, the sum of the digits is $82 + 8 + 7 + 2 = 99$, so the product can not equal 112.
  • If the product of the digits is $120$, then $a_2 = 5$ and $a_3 = 3$. However, the sum of the digits is $82 + 8 + 5 + 3 = 98$, so the product can not equal 120.
  • If the product of the digits is $128$, then $\prod_{i=2}^7 a_i = 16$. This can be achieved if $a_2 = 8$ and $a_3 = 2$, $a_2 = a_3 = 4$, $a_2 = 4$ and $a_3 = a_4 = 2$, or $a_2 = a_3 = a_4 = a_5 = 2$. The first case results in a sum of $82 + 8 + 8 + 2 = 100$, the second case results in a sum of $82 + 8 + 4 \cdot 2 = 98$, the third case results in a sum of $81 + 8 + 4 \cdot 3 = 101$, and the fourth case results in $80 + 8 + 2 \cdot 4 = 96$. Thus, the product can not be 128.

We found one working case where $a_1 = 8$. If $a_1 \le 7$, then the numbers are smaller, so the largest 85-digit number where the sum of the digits equals the product of the digits is $\boxed{8322\underbrace{111 \cdots 1}_{81\text{ ones}}}$.

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 $a_n = 1$ for $8 \le n \le 85$. 

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 $\boxed{8322\underbrace{111 \cdots 1}_{81\text{ ones}}}$.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_Indonesia_MO_Problems/Problem_8&oldid=97913"