2

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?

Community
  • 1
rurouniwallace
  • 6,266
  • 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 03 '13 at 05: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 03 '13 at 05:47
  • @Shreevatsa I just took $N(A\cup{B})$ to be the total amount of 4 digit numbers, but I guess that's incorrect... – rurouniwallace Aug 03 '13 at 05: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 03 '13 at 06: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 07 '13 at 16:40
  • Yes, Jim is correct. None of those in the linked question answer my question at all... – rurouniwallace Aug 08 '13 at 04:39
  • @ShreevatsaR I think your comments pretty much answer the question. Do you mind if I turn them into an answer? – askyle May 27 '14 at 11:11
  • @askyle: Sure, feel free. – ShreevatsaR May 27 '14 at 11:16
  • There is nothing in the statement of the question here that says we're dealing with a 4-digit number. If that's part of the question, please edit it in. – Gerry Myerson May 27 '14 at 12:32
  • @Ataraxia Is your question answered now? It'd be nice to get this one out of the queue :) – askyle Jun 24 '14 at 00:30

2 Answers2

1

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.

Community
  • 1
askyle
  • 486
0

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.

Christian Blatter
  • 226,825