2

I'm just wondering, what is the total number of $4$ digit positive integers that have the following properties:

All digits are unique.

Does not contain the digits $3$ and/or $4.$

The number is divisible by $3.$

Thoughts: All digits are unique is $9\times9\times8\times7,$ as I have learned, and I don't know how to do the second and third ones, to eliminate the ones that doesn't have this property.

Thanks!

Sujaan Kunalan
  • 10,944
Commander Shepard
  • 1,804

3 Answers3

3

First, we ignore the condition that it must be a 4 digit number, i.e. we allow the leading digit to be 0.

Observe that out of the possible digits (not 3 or 4), there are 3, 2, 3 digits that are 0, 1, 2 mod 3 respectively. For the 4 digit string to be a multiple of 3, we have the following cases:
1. 4 0's. This is not possible.
2. 2 0's, 1 1's, 1 2's. There are $ {3 \choose 2 } \times {2 \choose 1 } \times {3 \choose 1} \times 4 P 2 \times 2 P 1 \times 1 P 1$ ways.
3. 1 0's, 3 1's. This is not possible.
4. 1 0's, 3 2's. There are $ { 3 \choose 1 } \times { 3 \choose 3 } \times 4 P 1 \times 3 P 3 $ ways.
5. 2 1's, 2 2's. There are $ { 2 \choose 2 } \times { 3 \choose 2} \times 4 P 2 \times 2 P 2$ ways.

Now, we deal with the number of cases where the leading digit is 0. It can be done in a similar manner as the above, and I'd leave it to you to finish this.

Calvin Lin
  • 68,864
  • You are missing a lot of numbers here. For instance, your fourth product evaluates to 12. I make it: 3 (for choice of 0, 6, or 9) $\times$ 4 (for position of 0, 6, or 9) $\times$ 3! (for order of 2, 5, 8) which equals 72. – TonyK Aug 03 '13 at 07:43
  • @TonyK Yes, some of them should be Permutations instead of combinations. Let me edit. – Calvin Lin Aug 03 '13 at 08:04
1

Let $A_0=\{6,9\}$, $A_1=\{1,7\}$, and $A_2=\{2,5,8\}$.

1) If 0 is not a digit in the number, then the digits mod 3 are equal to $\{0,0,1,2\}$, $\{0,2,2,2\}$, or $\{1,1,2,2\}$ since an integer is divisible by 3 iff the sum of its digits is divisible by 3.

Therefore there are $\binom{2}{2}\binom{2}{1}\binom{3}{1}+\binom{2}{1}\binom{3}{3}+\binom{2}{2}\binom{3}{2}$ ways to choose the digits, and there are 4! ways to arrange them.

2) If 0 is a digit in the number, then the other three digits mod 3 are equal to $\{0,1,2\}$ or $\{2,2,2\}$.

Therefore there are $\binom{2}{1}\binom{2}{1}\binom{3}{1}+\binom{3}{3}$ ways to choose the digits, and $3(3!)$ ways to arrange them.

Thus there are $11\cdot24+13\cdot18=498$ such numbers.

user84413
  • 27,211
0

There is always the brute-force method ... Even if one is seeking a theoretical solution, this is always good for checking one's work (here, using Mathematica). Given integers divisible by 3:

lis = IntegerDigits[ Table[3 i, {i, 3333}] ];

... the answer is:

Count[lis, x_ /; (Length[Union[x]] == 4 && FreeQ[x, 3|4])]

498

Here, the first valid 4-digit integer produced is: 1026.

Padded zeroes

If you also wanted to include the leading 0 as a valid entry... e.g. to include the number 0126 as a valid entry, we can pad in the zeroes by replacing the first line with:

lis = IntegerDigits[Table[3 i, {i, 3333}], 10, 4];

The answer is then:

576

wolfies
  • 5,174