Combinations and . . . Non-combinations – Part III

In my last post, we applied the Fundamental Counting Principle (FCP) to solve the following GRE-style question:

How many different 3-digit numbers are greater than 299 and do not contain the digits 1, 6, or 8?

(A) 180

(B) 245

(C) 291

(D) 315

(E) 343

In that post, we solved the question, by taking the task of building 3-digit numbers and breaking it into individual stages. From there, we determined the number of ways to accomplish each stage, and then we applied the FCP.  

During the course of that solution there was a very important step that I didn’t mention. Today, I’d like to spend some time discussing that missing step, because it is very important.

Once we break a required task into stages, we should always ask, “Does the outcome of each step differ from the outcomes of the other steps?”

If the answer to this question is NO, we cannot solve the question using the FCP.

To illustrate this, please consider a new question:

A manager must create a 2-person committee from a group of 4 employees. In how many different ways can this be accomplished?

(A) 2

(B) 6

(C) 8

(D) 12

(E) 16

First, we’ll take the required task and break it into individual stages as follows:

Stage 1: Choose one person to be on the committee

Stage 2: Choose another person to be on the committee

At this point, if we continue solving this question using the FCP, we’ll arrive at the wrong answer. But, don’t believe me just yet.  Let’s just continue with this approach to see where things go wrong.

Stage 1: There are 4 employees, so we can choose the first person in 4 ways

Stage 2: At this point there are 3 people remaining, so we can choose the other person in 3 ways

When we apply the FCP, we get 4 x 3 = 12, which suggests that we can create 12 different two-person committees.

However, when we examine all 12 committees, we should see a problem with this answer. To list the committees, let’s let A, B, C, D represent the four employees. This means that the 12 committees are:

AB      AC     AD     BA      BC     BD

CA     CB     CD     DA     DB     DC

Can you see the problem?  

Well, for one, we have counted AB and BA as two different committees, when they are clearly not different. Similarly, we have counted BC and CB as different committees, not to mention other pairs.

So, what’s the problem here? The problem is that we’re treating the outcome of Stage 1 (selecting the first person) as different from the outcome of Stage 2 (selecting the second person), when these two outcomes are the same. In each case, the selected person gets to be on the committee.

To apply the FCP, we need the outcomes to be different.

This is why we need to ask the question, “Does the outcome of each step differ from the outcomes of the other steps?”  If the answer is NO (which it is in this case), then we cannot solve the question using the FCP. We must find another approach. In this particular example, the approach will be to use combinations (a topic for another day).

Aside: When we use combinations to solve the question we see that the answer to the question is 6 (answer choice B)

BIG TAKEWAY: Although the FCP can be used to solve the majority of counting questions on the GRE, it won’t always work.

Okay, now let’s examine a question that looks very similar to the last question:

A manager must select 2 people from a group of 4 employees. One person will be the shop steward and the other person will be the treasurer. In how many different ways can this be accomplished?

(A) 2

(B) 6

(C) 8

(D) 12

(E) 16

First, we’ll take the required task and break it into individual stages:

Stage 1: Choose someone to be the shop steward

Stage 2: Choose someone to be the treasurer

Now we’ll ask the all-important question, “Does the outcome of each step differ from the outcomes of the other steps?”  Here the answer is YES. The outcomes are definitely different. The outcome of Stage 1 is getting to be the shop steward. The outcome of Stage 2 is getting to be the treasurer. Since the outcomes are different, we can continue solving the question using the FCP.

Stage 1: There are 4 employees, so we can choose the first person in 4 ways

Stage 2: At this point there are 3 people remaining, so we can choose the other person in 3 ways

When we apply the FCP, we get 4 x 3 = 12. So, there are 12 different ways to select a shop steward and treasurer, which means the answer is D.

Finally, let’s apply our latest step to the original question:

How many different 3-digit numbers are greater than 299 and do not contain the digits 1, 6, or 8?

(A) 222

(B) 245

(C) 291

(D) 315

(E) 343

First we’ll take this task and break it into individual stages as follows:

Stage 1: Choose a digit for the hundreds position

Stage 2: Choose a digit for the tens position

Stage 3: Choose a digit for the units position

Then, we’ll ask, “Does the outcome of each step differ from the outcomes of the other steps?”

Here the answer is YES. The outcomes are different. For example, selecting a 6 for Stage 1 is different from selecting a 6 for Stage 2. In one case, the 6 becomes the digit in the hundreds position, and in the other case, the 6 becomes the digit in the tens position – TOTALLY DIFFERENT OUTCOMES.

Since the outcomes of each stage are different, we can continue solving the question using the FCP.

Stage 1: In how many different ways can we choose a digit for the hundreds position? Well, since the 3-digit number must be greater than 299, the digit in the hundreds position cannot be 0, 1 or 2. The question also says that the digits 6 and 8 are forbidden. So, when we consider the various restrictions, we see that the digit in the hundreds position can be 3, 4, 5, 7 or 9. So, there are 5 different ways in which we can accomplish Stage 1.

Stage 2: In how many different ways can we choose a digit for the tens position? Well, since the tens digit can be any digit other than 1, 6 or 8, we can see that the tens digit can be 0, 2, 3, 4, 5, 7 or 9. So, there are 7 different ways in which we can accomplish Stage 2.

Stage 3: The units digit can be 0, 2, 3, 4, 5, 7 or 9. So, there are 7 different ways in which we can accomplish Stage 3.

At this point we can apply the FCP to see that the total number of ways to accomplish all three stages (and create our 3-digit numbers) will equal the product of the number of ways to accomplish each individual stage.

So, we get 5 × 7 × 7, which equals 245.

There are 245 different 3-digit numbers that are greater than 299 and do not contain any 2’s, 6’s or 8’s.  The answer is B.