PERMUTATION AND COMBINATION PROBLEM - PLEASE HELP

[anugraha.santhanam]

How many 3 digit numbers can be formed using the digits 0,1,2,3,4,5,6 without repetition and that are divisible by 3?
Please help me out. I am not able to solve this problem.

[tim]

this one is tough because there are so many cases to consider and the inclusion of 0 throws off the symmetry of the problem. one way you might approach this one is to figure out which number combinations will add up to a multiple of 3:

0 1 2
0 1 5
0 2 4
0 3 6
0 4 5
1 2 3
1 2 6
1 3 5
1 5 6
2 3 4
2 4 6
3 4 5
4 5 6

each of the 8 combinations without a 0 can be arranged in 6 ways, for a total of 48. each of the 5 combinations with a 0 can only be arranged in 4 ways, for a total of 20. 48 + 20 = 68.

you could also use some insight from combinatorics and modular arithmetic and split into two cases. note that the following method is VERY complicated, so if you don't understand it just use the first method:

NO ZERO
six choices for the first number, and for each of those there are only four choices for the second number that are different from the first number mod 3. then there are two choices for the third number that are different from the first two mod 3. note that we need to have three different residues mod 3 because the only other possibility is for them all to be congruent mod 3, which cannot happen with these numbers. 6*4*2 = 48

WITH A ZERO
the two nonzero digits must add to 3, 6, or 9, which gives us the following pairs: 1-2, 1-5, 2-4, 3-6, 4-5. for each of these, there are two choices for which order they can occur in, and then the zero must be inserted as the second or third digit, for a total of 4 arrangements for each of the 5 pairs. 4*5 = 20

a final note: it is always a good idea to learn multiple methods for doing these problems. i use it to check my work. i initially made two mistakes when i listed out the combinations, but i caught them when i used the combinatorics/modular arithmetic approach..

[anugraha.santhanam]

Thank you!

[jlucero]

Glad it helped.