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

Difference between revisions of "1975 IMO Problems/Problem 4"

(Added solution)
 
Line 4: Line 4:
  
 
==Solution==
 
==Solution==
−
Let <math>N=4444^{4444}</math>. We now take the base-10 logarithm of <math>N</math>:
+
Note that
 +
<cmath>4444^{4444}<10000^{4444}=\left(10^4\right)^{4444}=10^{17776}</cmath>
  
−
<math>\log N=4444\log 4444<4444\cdot 4=17776</math>
+
Therefore <math>4444^{4444}</math> has less than 17776 digits. This shows that <math>A<9\cdot 17775=159975</math>. The sum of the digits of <math>A</math> is then maximized when <math>A=99999</math>, so <math>B\leq 45</math>. Note that out of all of the positive integers less than or equal to 45, the maximal sum of the digits is 12.
  
−
Therefore <math>N</math> has less than 17776 digits. This shows that <math>A<9\cdot 17775=159975</math>. The sum of the digits of <math>A</math> is then maximized when <math>A=99999</math>, so <math>B\leq 45</math>. Note that out of all of the positive integers less than or equal to 45, the maximal sum of the digits is 12.
+
It's not hard to prove that any base-10 number is equivalent to the sum of its digits modulo 9. Therefore <math>4444^{4444}\equiv A\equiv B\bmod{9}</math>. This motivates us to compute <math>4444^{4444}\bmod{9}</math>. The easiest way to do this is by searching for a pattern. Note that
  
−
It's not hard to provethat any base-10 number is equivalent to the sum of its digits modulo 9. Therefore <math>N\equiv A\equiv B\bmod{9}</math>. We now compute <math>N\bmod{9}</math>:
+
<cmath>4444^1\equiv 7\bmod 9, 4444^2\equiv 4\bmod 9, 4444^3\equiv 1\bmod 9</cmath>
  
−
<cmath>N\equiv 4444^{4444}\equiv (4437+7)^{4444}\equiv (9\cdot 493 +7)^{4444}\bmod{9}</cmath>
+
and since <math>4444=3\times 1481+1</math>,
  
−
After expanding, every term except <math>7^{4444}</math> is divisible by 9, so they all cancel out. This shows that <math>N\equiv 7^{4444}\bmod{9}</math>. Note that <math>7^3=343=9\cdot 36+1</math>. Therefore
+
<cmath>4444^{4444}\equiv 4444^{(3\times1481+1)}\equiv \left(4444^3\right)^{1481}\times 4444\equiv 1\times 4444\equiv 7\bmod{9}</cmath>
  
−
<cmath>N\equiv 7^{4444}\equiv 7^{3\cdot 1481 +1}\equiv 7\cdot (7^3)^{1481}\equiv 7\cdot (9\cdot 36+1)^{1481}\bmod{9}</cmath>
+
This proves that the sum of the digits of <math>B</math> is <math>\boxed{7}</math>.
−
 
 
−
After expanding, every term except <math>7</math> is divisible by 9, so they all cancel out. This shows that <math>N\equiv 7\bmod{9}</math>. Therefore <math>A\equiv B\equiv 7\bmod{9}</math>, and the sum of the digits of <math>B</math> is also <math>7\bmod{9}</math>. However, we established that the sum of the digits of <math>B</math> is at most 12. This proves that the sum of the digits of <math>B</math> is <math>\boxed{7}</math>.
 
  
 
{{alternate solutions}}
 
{{alternate solutions}}

Revision as of 23:14, 22 July 2013

Problem

When $4444^{4444}$ is written in decimal notation, the sum of its digits is $A$. Let $B$ be the sum of the digits of $A$. Find the sum of the digits of $B$. ($A$ and $B$ are written in decimal notation.)

Solution

Note that \[4444^{4444}<10000^{4444}=\left(10^4\right)^{4444}=10^{17776}\]

Therefore $4444^{4444}$ has less than 17776 digits. This shows that $A<9\cdot 17775=159975$. The sum of the digits of $A$ is then maximized when $A=99999$, so $B\leq 45$. Note that out of all of the positive integers less than or equal to 45, the maximal sum of the digits is 12.

It's not hard to prove that any base-10 number is equivalent to the sum of its digits modulo 9. Therefore $4444^{4444}\equiv A\equiv B\bmod{9}$. This motivates us to compute $4444^{4444}\bmod{9}$. The easiest way to do this is by searching for a pattern. Note that

\[4444^1\equiv 7\bmod 9, 4444^2\equiv 4\bmod 9, 4444^3\equiv 1\bmod 9\]

and since $4444=3\times 1481+1$,

\[4444^{4444}\equiv 4444^{(3\times1481+1)}\equiv \left(4444^3\right)^{1481}\times 4444\equiv 1\times 4444\equiv 7\bmod{9}\]

This proves that the sum of the digits of $B$ is $\boxed{7}$.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

1975 IMO (Problems) • Resources
Preceded by
Problem 3 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 5
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1975_IMO_Problems/Problem_4&oldid=56699"