23
$\begingroup$

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.

$\endgroup$

closed as off-topic by TheSimpliFire, ℋolo, Namaste, Xander Henderson, Gibbs Oct 21 '18 at 20:59

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – TheSimpliFire, ℋolo, Namaste, Xander Henderson, Gibbs
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ 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. $\endgroup$ – Brilliand Jun 3 '14 at 18:33
  • $\begingroup$ "Has exactly 9 digits, all of which are distinct" might be more accurate. $\endgroup$ – Dan Jun 3 '14 at 19:32
  • 2
    $\begingroup$ @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. $\endgroup$ – robjohn Jun 3 '14 at 19:54
  • $\begingroup$ I see how we know it has 9digits, $29\log 2=8.73$ but how does one know the digits are distinct ? $\endgroup$ – Rene Schipperus Jun 3 '14 at 22:38
  • $\begingroup$ Just asking: Is it (the competition) SMO? $\endgroup$ – user148697 Jun 27 '14 at 13:42
40
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't know what I'm missing out here, but will you be able to elaborate how to calculate $2^{29} \pmod 9$. Any hint will also suffice! Thanks for the answer, by the way! $\endgroup$ – puru Jun 28 '14 at 2:51
  • $\begingroup$ You find the power of two mod 9, that is $2^n\equiv 1\pmod 9$ I forget what it is but then you divide it into 29. $\endgroup$ – Rene Schipperus Jun 28 '14 at 2:58
  • 2
    $\begingroup$ Thanks, I got it. In fact, $2^{29}=2^{27} \times 4=(9-1)^9 \times 4$ which implies that $2^{29} \pmod 9= -4$ $\endgroup$ – puru Jun 28 '14 at 9:29
32
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Oh its so easy, now that we follow the hint (thanks !) $\endgroup$ – Rene Schipperus Jun 3 '14 at 16:32
12
$\begingroup$

$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.

$\endgroup$
  • 7
    $\begingroup$ It's about creative solution not answering it $\endgroup$ – Karo Jun 3 '14 at 16:08
  • 19
    $\begingroup$ 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? $\endgroup$ – Jorge Fernández Hidalgo Jun 3 '14 at 16:11
  • $\begingroup$ whats should we do? don't think on other methods to solve it? $\endgroup$ – Karo Jun 3 '14 at 16:22
  • $\begingroup$ @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? $\endgroup$ – alex.jordan Jun 3 '14 at 16:38
  • 2
    $\begingroup$ 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. $\endgroup$ – Karo Jun 3 '14 at 17:36
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This looks eerily similar to Rene Schipperus' answer. $\endgroup$ – robjohn Jun 3 '14 at 20:00
  • $\begingroup$ 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}$... $\endgroup$ – user21820 Jun 4 '14 at 11:58

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