Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The number $2^{29}$ has exactly $9$ distinct digits. Which digit is missing?

I came across this question in a math competition and I am looking for how to solve this question without working it out manually. Thanks.

share|improve this question
1  
The accepted answer only works for numbers in which every digit is distinct. Is that supposed to be implied by "exactly 9 distinct digits"? I interpret that as also allowing a 10-digit number with one duplicate. –  Brilliand Jun 3 at 18:33
    
"Has exactly 9 digits, all of which are distinct" might be more accurate. –  dan08 Jun 3 at 19:32
    
@Brilliand: if we start with $2^{10}=1024$, it is not too hard to see that $2^{29}\approx500,000,000$. So, $2^{29}$ has $9$ digits. –  robjohn Jun 3 at 19:54
    
I see how we know it has 9digits, $29\log 2=8.73$ but how does one know the digits are distinct ? –  Rene Schipperus Jun 3 at 22:38
    
Just asking: Is it (the competition) SMO? –  user148697 Jun 27 at 13:42

4 Answers 4

up vote 27 down vote accepted

Oh its so easy, now that we follow the hint (thanks !)

$$\sum k_n 10^n \equiv \sum k_n \mod 9$$ the sum of all the digits is $\frac{9(9+1)}{2}\equiv 0 \mod 9$ so the sum of all but one $x$ is $\equiv -x \mod 9$

Now $$2^{29}\equiv -4 \mod 9$$ so $4$ is the missing digit.

share|improve this answer
    
Thanks for the fix. What is the latex notation for making the "mod" sign ? –  Rene Schipperus Jun 3 at 16:44
    
You use \pmod {modulus}, which puts parentheses around the modulus. So \pmod {12} gives $\pmod {12}$. You don't need the braces for a single digit. –  Ross Millikan Jun 3 at 17:05
    
Thanks. Ill use that. –  Rene Schipperus Jun 3 at 17:23
1  
@ReneSchipperus: You can click 'edit' on any question to see the underlying $\LaTeX$ markup. –  Py42 Jun 3 at 18:08
7  
@ReneSchipperus Or even easier, right-click the formula and select "Show Math As"->"TeX Commands". –  Ruslan Jun 3 at 19:53

A hint: Think about the remainder modulo $9$.

share|improve this answer
    
Oh its so easy, now that we follow the hint (thanks !) –  Rene Schipperus Jun 3 at 16:32

$2^{29}$ is not that big. You can just compute it. A fast launch point is to know that $2^{10}=1024$. So you just need to multiply $1024\cdot1024\cdot512$, which can be done by hand quickly in a competition.

share|improve this answer
5  
It's about creative solution not answering it –  Karo Jun 3 at 16:08
14  
Why would someone waste their time looking for a "creative solution" in a competition when computing it is not only fast but assured to work? –  Jorge Fernández Jun 3 at 16:11
    
whats should we do? don't think on other methods to solve it? –  Karo Jun 3 at 16:22
    
@Karo If it is a competition and your goal is to finish and win, then yes. If you can identify an approach that will get you the answer quickly, what extra points do you get for being clever? –  alex.jordan Jun 3 at 16:38
1  
It's just beautiful to me that I prove that it should be digit x that is missing instead of computing the answer with calculator and finding out that digit x is missing. it's just personal feeling and I like mathematics to be like this. –  Karo Jun 3 at 17:36

Let the number $N$ be represented by $9$ digits $d_i$ for $i=0,\dots,8$ so that $$N = \sum_{i=0}^{8} d_i 10^i$$ We first notice that $$\sum_{i=0}^{8} d_i 10^i \equiv \sum_i d_i \pmod{9}$$

Since only one digit is missing, this sum must be between 36 (with 9 missing) and 45 (with 0 missing). There are two cases to consider. Either $\sum d_i \equiv 0 \pmod{9}$ or it is not. In the first case, either 0 or 9 is the missing digit, since those are the only missing values for which $\sum_i d_i \equiv 0 \pmod{9}$, making the sum either 36 or 45. We can determine which is the value by looking at the sum $\pmod{8} = N \pmod{8}$: if this value is 4 then the sum is 36 and 9 is the missing digit. If $N \equiv 5 \pmod{8}$, then the sum is 45 and 0 is the missing digit.

In the second case, we note that the sum of all but one digit $x$ is congruent to $-x \pmod{9}$. Solving this congruence for $x$ gives the missing digit.

This addresses the case of an arbitrary $N$ for which $N \equiv 0 \pmod{9}$ which the accepted answer does not handle correctly. Since I'm not yet allowed to comment or improve other answers by censors, I just constructed a new, complete answer. Vote it up so in the future I can do this the right way.

share|improve this answer
1  
This looks eerily similar to Rene Schipperus' answer. –  robjohn Jun 3 at 20:00
    
It's not obvious how you can "look at the sum of digits mod 8", if all you know is that the number is $2^{29}$... –  user21820 Jun 4 at 11:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.