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 numbers 1-9 are drawn from a hat at random. Without repetition of numbers, how many numbers (with all digits drawn-- eg. 987654321) would be divisible by 11?

First I recalled that a number is divisible by 11 if the number's alternating digits minus the other digits are equal to a number divisible by 11.

Honestly, I did a bit of guess and check to follow and found that 948576321 was an answer divisible by 11. Therefore if I rearranged 9,8,7,3, and 1 (the leading alternating numbers) it would bring the same result. So I solved the permutation to receive 120 possible combinations. I then took the permutation of 4,5,6, and 2 and received a total of 24 combinations.

I multiplied these two answers together to get a grand total of 2880 combinations that would be divisible by 11.

Is this the correct answer? Please help, and thanks in advance! :)

share|improve this question
    
I ran a quick python program, and the answer is 31680. I'll try to prove it in a few minutes. –  Alfonso Fernandez Feb 20 '13 at 22:33
    
I would appreciate it :) –  Hannah Feb 20 '13 at 23:06
add comment

3 Answers 3

up vote 5 down vote accepted

The correct answer is 31680. Your combination of alternating numbers (9, 8, 7, 3, 1) is only one out of 11 possibilities:

  1. 1, 2, 3, 4, 7
  2. 1, 2, 3, 5, 6
  3. 1, 3, 7, 8, 9
  4. 1, 4, 6, 8, 9
  5. 1, 5, 6, 7, 9
  6. 2, 3, 6, 8, 9
  7. 2, 4, 5, 8, 9
  8. 2, 4, 6, 7, 9
  9. 2, 5, 6, 7, 8
  10. 3, 4, 5, 7, 9
  11. 3, 4, 6, 7, 8

So we end up with $11 \cdot 5! \cdot 4! = 11 \cdot 120 \cdot 24 = 31680$.

share|improve this answer
    
But how do you come up with these 11 without checking all $\binom{9}{4}=126$ possibilities? –  Alfonso Fernandez Feb 21 '13 at 0:21
    
@AlfonsoFernandez I did it by checking all of them with a script. Brian's approach is more rigorous in that regard. –  ralph Feb 23 '13 at 14:40
1  
(This kind of problem, finding a set of distinct numbers to add up to a certain number, is a key part of Kakuro puzzles. The list of valid combinations for this can be found in Kakuro tables such as brainbashers.com/combinations.asp under 5-digit combinations with a sum of either 17 or 28. Brian's answer proves why the sum must be 17 or 28.) –  ralph Feb 23 '13 at 14:47
add comment

Here’s a systematic approach; it’s still a bit tedious in spots, but not unreasonably so.

The sum of all $9$ digits is $45$. You need to split the digits into a set $A$ of $5$ digits, those in the odd-numbered positions, and a set $B$ of $4$ digits, those in the even-numbered positions, whose sums differ by a multiple of $11$. If $a$ is the sum of the digits in $A$ and $b$ the sum of the digits in $B$, then $a-b$ is a multiple of $11$, and $a+b=45$.

Clearly $b=45-a$, so $a-b=a-(45-a)=2a-45$. The smallest possible value of $a$ is $1+2+3+4+5=15$, and the largest is $9+8+7+6+5=35$, so $-15\le a-b\le25$. The multiples of $11$ in that range are $-11,0,11$, and $22$. However, $2a-45$ is clearly odd, so in fact the only possible values of $a-b$ are $-11$ and $11$.

  • If $a-b=2a-45=-11$, then $a=17$.
  • If $a-b=2a-45=11$, then $a=28$.

What sets of $5$ digits sum to $17$? Since $1+2+3+4+5=15$, we either increase $5$ by $2$ to get the set $\{1,2,3,4,7\}$ or increase $4$ and $5$ by $1$ each to get the set $\{1,2,3,5,6\}$; anything else produces either too big a sum or duplicated digits.

It’s a bit harder to enumerate the sets that sum to $28$, because there are more of them. A good starting point is the fact that $9+8+7+6+5=35$, which is $7$ too large. First note that we need to have at least one of $8$ and $9$: $7+6+5+4+3=25$ is too small. What can we do without the $9$? $8+7+6+5+4=30$, so, much as in the previous case, our only choices are to subtract $2$ from $4$ to get the set $\{8,7,6,5,2\}$ or subtract $1$ each from $4$ and $5$ to get $\{8,7,6,4,3\}$. Every other set will include the $9$.

Let’s try next for the ones that include $9$ but not $8$. $9+7+6+5+4=31$; we can subtract $3$ from the $4$, the $5$, or the $6$ to get the sets $\{9,7,6,5,1\}$, $\{9,7,6,4,2\}$, and $\{9,7,5,4,3\}$. A little experimentation shows that trying to reduce the sum by $3$ by subtracting $2$ from one digit and $1$ from another produces nothing new.

The last batch will be those containing both $9$ and $8$. If we keep the $7$ as well, we already have a total of $9+8+7=24$, and the only two digits that supply the missing $4$ are $1$ and $3$, giving us the set $\{9,8,7,3,1\}$. If we start with $9,8$, and $6$, we can get the missing $5$ from either $1$ and $4$ or $2$ and $3$, giving us the sets $\{9,8,6,4,1\}$ and $\{9,8,6,3,2\}$. If start with $9,8$, and $5$, the only way to get the missing $6$ is with $2$ and $4$, giving us the set $\{9,8,5,4,2\}$. And $9+8+4+3+2=26$ is too small, so we’ve found all of the possibilities for the set $A$.

As you already observed, we can permute $A$ and $B$ arbitrarily, so each choice of $A$ yields $5!4!$ numbers, and there are $11$ possibilities for $A$, for a grand total of $11\cdot5!4!=31,680$ numbers.

share|improve this answer
add comment

Every number of the form $x*11$ is divisible by 11. Now you must think about $x$.

$x$ must be such that $(x)*11$ is a number with 9 digits! If it is useful for you I can explain it more.

share|improve this answer
add comment

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.