Number of different integers between $1,000$ and $10,000$

How many integers are there between $1,000$ and $10,000$ divisible by $60$ and all with distinct digits?

I know that there are $8,999$ integers in total, and $\lfloor\frac{8999}{60}\rfloor=149$. So there are $149$ integers between $1,000$ and $10,000$ divisible by $60$.

For the first digit we have $8$ choices, for the second $9$ choices, for the third $8$ choices and for the last $7$ choices. So there are $4,032$ different integers between $1,000$ and $10,000$. How to combine these results to an answer on the above question?

• Simplify things a little first. The last digit must be $0$ and the next to last must be $2$, $4$, $6$, or $8$. – André Nicolas May 12 '15 at 14:52
• Next-to-last digit may be $0$, too. – ajotatxe May 12 '15 at 15:00
• @ajotatxe it cannot if we are using all distinct numbers. The zero must take the last space – JMoravitz May 12 '15 at 15:01
• Oops, sorry. I shall fix my answer then. – ajotatxe May 12 '15 at 15:24
• There are actually $150$ numbers (not $149$) between $1000$ and $10000$ that are divisible by $60$. The smallest is $1020$ and the largest is $9960$. A correct formula to count these numbers is $\left\lfloor\frac{10000}{60}\right\rfloor - \left\lfloor\frac{1000}{60}\right\rfloor$. – David K May 12 '15 at 15:59

As Andre points out, this problem is perhaps better approached directly than with inclusion-exclusion. We know a few things:

• The number will be four digits long. (because it is between 1000 and 10000)
• The number is divisible by $60 = 2^2\cdot 3\cdot 5$
• Since it is divisible by 60, it is divisible by 10 and the last digit must be a zero
• Since it is divisible by 60, it is divisible by 4 and the last two digits must be divisible by 4, i.e. the second to last digit is either a 2, 4, 6, or 8
• Since it is divisible by 60, it is divisible by 3 and the sum of the digits must be a multiple of three

In order to have the sum of digits be a multiple of three, if the second to last digit is a 2 or 8, among the first two digits one of three things will happen:

• Both are equivalent to $2$ mod 3
• The first is equivalent to $1$ mod 3 and the other is equivalent to $0$ mod 3
• The first is equivalent to $0$ mod 3 and the second is equivalent to $1$ mod 3

If the second to last digit is a 6, then one of three things will happen:

• Both are equivalent to $0$ mod 3
• The first is equivalent to $1$ mod 3 and the other is equivalent to $2$ mod 3
• The first is equivalent to $2$ mod 3 and the other is equivalent to $1$ mod 3

If the second to last digit is a 4, then one of three things will happen:

• Both are equivalent to $1$ mod 3
• The first is equivalent to $2$ mod 3 and the other is equivalent to $0$ mod 3
• The first is equivalent to $0$ mod 3 and the other is equivalent to $2$ mod 3

You can now fill out a table (same idea as a tree diagram) to see how many possibilities total there are. Going vertically, I will place the choice of the second to last digit (either 2,4,6, or 8), and going horizontally I will place which case we are in for the first two digits (as they were described above). In the respective spaces inside the table I place how many results there are for each.

choice for second to last digit$\begin{array}{c|c|c} &\text{first case}&\text{second case}&\text{third case}\\ \hline 2& 2\cdot 1&3\cdot3&3\cdot3\\ \hline \color{red}{4}&\color{red}{2\cdot 1} & \color{red}{3\cdot 3} & \color{red}{3\cdot 3} \\ \hline 6& 2\cdot 1 & 3\cdot 3 & 3\cdot 3\\ \hline 8& 2\cdot 1 & 3\cdot 3 & 3\cdot 3 \end{array}$

Let us look a bit more closely at one of these rows in particular to understand where the numbers came from. In the case that the second to last digit is a $4$ we have our number looking like this:

$$\underline{x}~\underline{y}~\underline{4}~\underline{0}$$

In the case that both $x$ and $y$ are 1mod3, they could be one of $\{1,4,7\}$, except that $4$ is already in use, so really there are only the choices $\{1,7\}$. By picking what $x$ is, $y$ has one option left, for a total of $2$ possibilities for this case. (for example the number $1740$)

In the case that $x$ is 2mod3 and $y$ is 0mod3, $x$ could be one of $\{2,5,8\}$ and $y$ can be any of $\{0,3,6,9\}$ except that $0$ is already in use by the last digit, so it could really have only been one of $\{3,6,9\}$. With $3$ choices for $x$ and $3$ choices for $y$, there are then a total of $9$ possibilities for this case. (for example $5340$)

The case that $x$ is 0mod3 and $y$ is 2mod3 is an identical argument to the previous, replacing the roles of $x$ and $y$.

As we have covered all possibilities with no overlap, the total is the sum of the entries in the table for a total of 80 such numbers.

Afterthought, looking at the symmetry of the table, one might think a more appropriate way of approaching the problem is:

Pick the second to last digit. There are four such choices.

Either all three of the first three digits are then the same modulo 3 or all three are different modulo 3.

In the first case, there are 2 ways to assign the first two digits

In the second case, pick which modulo class the first digit is assigned to for two such choices.

Assign digits to the first two digits (notice there are 3 choices available to each since zero is in use) for a total of 9 such choices.

As a result there are $4\cdot (2+2\cdot 9) = 80$ such numbers.

Last digit is $0$.

Next-to-last is even. Call it $a$.

If $a=2$ the two first digits' sum is 1, 4, 7, 10, 13 or 16. Count how many possibilities there are for each. For example, for 10 there are $7$ possibilities (order matters, and don't forget that repeated digits are not allowed).

Make the same thing for $a=4$, $6$ and $8$. Note that, since $8-2$ is a multiple of three, there are as many possibilities for $a=8$ as for $a=2$.

Sum all this up.

To produce divisibility by $60$, we need divisibility by $3, 4$ and $5$. The final digit $0$ takes cares of $5$ and one factor of $2$, and choosing an even digit (from $\{2,4,6,8\}$) before that takes care of the second factor of $2$. Then for the digits before that, we have a free choice from the remaining $8$ digits but we need to choose them such that the whole number is divisible by $3$. That part is complicated to state as a simple digit selection, mostly because of the already-chosen digits, but we know that if we allow a free choice (of $8$) on one of those digits there can't be more than $3$ possibilities for the other (and can't be less than $1$ possibility either). So the answer lies somewhere between $32$ and $96$ possibilities.

I would enumerate the multiples of $6$ not divisible by $10$ to finalize the count, with an expectation that the answer is somewhere a little above $64$ different combinations.