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.

In this question, the problem is to find the amount of four-digit numbers that have the following characteristics:

All digits are unique.

Does not contain the digits 3 and/or 4.

The number is divisible by 3.

I was going to use inclusion/exclusion for this, which states:

$$N(A\cap{B})=N(A)+N(B)-N(A\cup{B})$$

Take $A$ to be the first two properties, and $B$ to be the third. It must be a $4$ digit number, and cannot contain $3$ or $4$:

$$7\cdot{7}\cdot{6}\cdot{5}$$

Now consider the number of $4$ digit numbers divisible by $3$. The amount of numbers divisible by $3$ between $1$ and $10000$ is $3333$. The amount of numbers divisible by $3$ between $1$ and $1000$ is $333$. Subtract one from the other, and the amount of numbers divisible by $3$ between $1000$ and $10000$ is $3000$.

$$N(A)=7\cdot7\cdot6\cdot5\\ N(B)=3000\\ N(A\cup{B})=9000$$

This comes out to a negative number, which tells me I'm setting up my cases incorrectly. Can anyone tell me what I'm doing wrong?

share|improve this question
1  
When you are counting numbers divisible by $3$, you are counting (i) those that have $3$ and/or $4$ and (ii) those with repeated digits. I think the problem you are trying to solve may be somewhat ugly. –  André Nicolas Aug 3 '13 at 5:45
    
How did you get $N(A\cup{B})=9000$? Obviously you can't have $N(A\cup{B}) > N(A) + N(B)$, so there's something very wrong with your calculation of $N(A\cup{B})$. But in fact I can't think of a way here to calculate $N(A\cup{B})$ without also calculating $N(A\cap{B})$. –  ShreevatsaR Aug 3 '13 at 5:47
    
@Shreevatsa I just took $N(A\cup{B})$ to be the total amount of 4 digit numbers, but I guess that's incorrect... –  Ataraxia Aug 3 '13 at 5:52
2  
@Ataraxia: $A\cup{B}$ is the set of 4-digit numbers that either have all digits distinct and different from 3/4, or are divisible by 3 (or both). For instance, a number like 1337 is not in the set $A\cup{B}$, because it neither has distinct digits, nor is it divisible by 3 (i.e. it's neither in $A$ nor in $B$, so it's not in $A\cup{B}$). –  ShreevatsaR Aug 3 '13 at 6:08
    
This question is asking about why their inclusion/exclusion argument didn't work, it is not just asking for the solution. This shouldn't be marked as a duplicate. –  Jim Aug 7 '13 at 16:40

2 Answers 2

up vote 1 down vote accepted

These comments by @ShreevatsaR pretty much nail it. I'll "answerify":

It's not working because $N(A\cup B)\neq 9000$. The OP assumed that $A\cup B$ covers all the numbers between $1000$ and $9999$ (inclusive). However, 1337 is neither in $A$ nor $B$, so it's not in the union.

The question then becomes, how do we count $N(A\cup B)$? I for one don't see a better answer than… count $N(A\cap B)$ directly and use inclusion-exclusion as:

$$ N(A\cup B) = N(A) + N(B) - N(A\cap B) $$

which AFAIK is the more common statement of the principle.

In general, given two properties it is often more straightforward to count how many elements have both properties at the same time than how many elements have at least one of the properties, precisely because one has to consider the cases in which they overlap. Sometimes one can count the union "directly" with De Morgan's law $\overline{A\cup B} = \overline{A}\cap\overline{B}$, which again reduces the problem to counting an intersection instead of a union.

share|improve this answer

I'm not sure whether inclusion/exclusion is the simplest way to deal with this problem. I'd rather enumerate the cases directly.

The set of available digits can be partitioned according to the remainder modulo $3$ as follows: $$A=\{0,6,9\}, \quad B=\{1,7\},\quad C=\{2,5,8\}\ .$$ Denoting the number of digits chosen from $A$ by $x_A$, and similarly for the other two, we have $$x_A+x_B+x_C=4, \qquad x_B=x_C\ ({\rm mod}\ 3)\ .$$ As $x_A\leq 3$ and $x_B\leq2$ this leaves the possibilities $$\eqalign{{\rm (i)}\quad &x_A=2, \quad x_B=x_C=1,\cr {\rm (ii)}\quad &x_A=1, \quad x_B=0,\quad x_C=3,\cr {\rm (iii)} \quad &x_A=0, \quad x_B=x_C=2\ .\cr}$$ In case (i) the digits can be chosen in ${3\choose 2}\cdot 2\cdot 3=18$ ways, and one can then arrange them in $18\cdot4!=432$ ways. $12$ of the $18$ choices of the digits contain $0$, so that $12\cdot 3!=72$ of these $432$ arrangements begin with $0$, which is not admissible. This leaves $432-72=360$ admissible arrangements of type (i).

In case (ii) the digits can be chosen in $3\cdot 1=3$ and arranged in $3\cdot 4!=72$ ways. $6$ of these arrangements begin with $0$ and are not admissible, so that we obtain $66$ arrangements of type (ii).

In case (iii) the digits can be chosen in $1\cdot{3\choose 2}=3$ and then be arranged in $3\cdot 4!=72$ ways.

Therefore we obtain a total of $360+66+72=498$ admissible four digit numbers.

share|improve this answer

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.