Interpreting and Solving a Counting Problem

(An archive question of the week)

Combinatorics can be inherently tricky; making up your own problem is doubly so. Here we have a problem created by a teacher, who then is not entirely sure what it means. How can we figure out what meaning to give it? Combine that with working out how to solve a complex problem, and we have another occasion for a long discussion with a student!

The problem and its meaning

Here’s the question, from 2014 (I didn’t write the title, which is amazing):

Transporting Twenty in Two Ways, and the Twins Together

Twenty students must return from a school camp. There are two ways of getting back home. There is a 5-seat car and a bus. Two of the students have a license to drive, and there is a set of twins who have to go home together.

If the driver for the bus is already accounted for, how many ways can 5 people be chosen to go home in the car?

My teacher made this question up, and isn't 100% sure how to do it; there is some dispute between him and the class.

I'm having difficulty enumerating the number of cases that need to be taken into account. I think there are three cases: twins in the car, twins not in the car, and one or both of the twins driving (one or both; either way they'll both be in the car). My final answer was 5848, but some of my classmates brought up cases such as if one twin was the driver but wasn't chosen to be the driver. I'm not sure if that is accounted for in the cases I've considered.

I took the question, and started with a basic observation about interpretation: The author’s intent must determine the meaning:

When a problem is ambiguous, it's the poser's job to resolve it. So just ask your teacher whether a twin can be the driver of the car, and whether the driver is considered a distinct position. (That would make this partly a permutation, since it would matter who sits in that position, though it doesn't matter where others sit.)

Of course, this is ultimately the whole difficulty: The author probably doesn’t have a clear intent. My questions are intended to focus attention on the issues that must be resolved in order to have a meaning, both of which we’ll be coming back to. But sometimes, the way to clarify what we mean is to work though it, answering our own questions as we go. (This is reminiscent of something I said recently in connection with Polya’s How to Solve It.)

Here are the car and the bus, with a total of 20 seats for students; the car needs a driver, but the bus already has one. The students are lined up ready to get on; A and B can drive, and S and T are the twins who must be together:

We need to choose 5 to go in the car; the bus will hold all the rest.

Here's how I'd do it:

We have to fill 5 places in the car; at least one person in the car has to be a driver. We think of the twins as a unit. I'll assume that the wording of the problem excludes either twin from having a driver's license (more on that below).

There are two cases:

1. Neither twin is in the car. There are 18 people to choose from, two of whom are drivers. Rather than choose a driver first, we can count all the ways to choose the 5, and then subtract all the choices that include NO driver. That gives us

   C(18,5) - C(16,5) = 8568 - 4368
                     = 4200

2. Both twins are in the car. That leaves 18 people from whom to choose only 3 open places in the car; again, we'll count all ways to choose, then subtract those with no driver:

   C(18,3) - C(16,3) = 816 - 560
                     = 256

There are a total of 4200 + 256 = 4456 ways to choose.

Here are pictures of the two cases; keep in mind that we don’t care where within a vehicle anyone sits, just which they are in.

The subtractive method I chose to use is intended to avoid overcounting that tends to arise if we choose a driver first; we’ll see that below.

Can the twins drive?

I added a comment related to Oscar’s third case:

I was considering redoing the work to account for the assumption that one or both of the twins might have a license. But it occurs to me that if you don't know whether they do, then you really don't know enough to place people, so the question wouldn't be asked. In particular, we can't count separately cases where a twin is a driver and where neither twin is a driver, because that is not a distinction of *who is in the car*, just of *who is a driver*.

I'm strongly inclined toward my first assumption -- that the twins are not drivers (because that wasn't mentioned in the problem).

So by working through the problem, I decided that it really couldn’t be interpreted any other way and still be solvable. Ultimately, that’s because this would be a different problem:

Oscar replied; I hadn’t been clear enough yet about the twins being drivers:

I forgot to mention that there is the possibility that the twins can be drivers. Sorry about that.

If that is the case, how would you go about solving this?

The teacher believed there were three cases: the two you've mentioned; and if one or both of the twins are drivers, which I mentioned originally.

Also, for the first two cases you've done, I've gotten different answers. I selected the drivers first, then chose from the rest, and got:

  Case I: twins not in the car
           
       C(2,1) x C(17,4) = 4760
           
       There are 2 drivers from which we choose 1;
       then from the remaining 17 people -- which
       includes the other driver, whose sitting in
       the car excludes the twins -- we choose 4.

  Case II: twins in the car and not driving
   
       C(2,1) x C(17,2) = 272
            
       There are 2 drivers from which we choose 1;
       then from the remaining 17 people --
       excluding the twins since they MUST be in
       the vehicle -- we choose 2.

As you can see, my answers to your two cases are quite different; but from what I can see, there is nothing wrong with your method and nothing with mine. What is the difference, aside from the approach?

I answered, dealing first with the twins-can-drive issue; we’ll get to Oscar’s work soon.

You didn't forget to mention the possibility that the twins can drive; I rejected that interpretation, with an explanation why.

Let's see what I can do under the assumption that one or both twins can drive. The trouble with this interpretation, as I mentioned, is that this kind of counting problem requires that you know about the set from which you are selecting items, and the rules for selection. If we don't know who can drive, how can we count how many ways the car can be filled?

This is the central issue: In order to solve this problem, we would need to know things we haven’t been told. Each student comes with or without a driver’s license, so whether an individual can drive is part of the specification of the given set.

To demonstrate the problem, I gave it a try, supposing that the twins might be able to drive:

The way I'm thinking about it now, we can just think about how many ways there are to fill the car, and then decide whether any of them are not allowed. So we can first ignore the question of who can drive.

That gives us two cases again: both twins (so we have to pick 3 others), or neither (so we have to pick 5). 

The number of ways to do this is

   C(18,3) + C(18,5) = 816 + 8568
                     = 9384

Now, based on our knowledge of who can drive, are any of these choices not allowed? No! We don't know who can drive; it may be a twin, or may not. So we can't tell who has to be the driver. And every possible choice of people in the car includes SOMEONE who could be the driver, so we can't eliminate any.

Do you see why I rejected your interpretation of the problem?

Again, trying to solve helps us understand what it has to mean.

The problem of overcounting

I looked at his Case I:

I explained that I did it the way I did in order to avoid the difficulty involved in choosing a driver but then having to correct overcounting cases where there are two drivers in the car -- and indeed, you fell into that trap.

You are assuming you know who the drivers are, and you choose one of them. Then you choose from the 7 people other than the driver AND the twins, who are assumed not to be drivers. But you are making no adjustment for the fact that you are counting the same set of people twice if both drivers are in the car (once if this one is driving, and once if that one is driving).

The problem did NOT ask how many ways are there to choose people for the car AND specify who is driving -- only who is in the car.

Here is an example of a case that would be counted twice:

The same happens in Case II.

You could, I suppose, try adjusting your work to fix the error I pointed out, and that would help confirm the correctness of my numbers. (I'm never quite sure until I've found two ways to get the same answer!) I'll leave that to you.

The main thing I want to leave you with is an awareness that if you allow the twins to be drivers but do not specify whether they are, the problem makes no real sense. If you'd like, walk me through your own calculations to get your answer of 5848, and I'll see whether it makes sense. I'm pretty sure we'll find that you can't clearly explain each step without discovering a flaw in your interpretation of the problem.

After some further discussion, I tried a standard technique to help clarify:

Let's try a smaller problem, and see if that reveals what happens more clearly. 

At the risk of making this simpler problem too simple to be interesting, suppose the car holds two people, and there are 5 people in all, including the twins, two people being drivers. How many ways are there to fill the car?

Here are the people (S and T being the twins, A and B being the drivers) and the car:

   A B C S T              car: ___  ___

Taking it your way (as I understand it), we first choose a driver; there are C(2,1) = 2 choices:

   _A_  ___      _B_  ___

Now we chose another person (not a twin); there are C(2,1) = 2 choices:

   _A_  _B_      _B_  _A_
   _A_  _C_      _B_  _C_

This gives 2*2 = 4 ways to fill the car. But two of them are the same -- namely, AB. Remember, we are not counting ways to choose a driver and passenger; we are counting ways to put people in the car, without regard for who is driving. That's where you are over-counting. This is a very easy thing to do.

It was time to demonstrate how to adjust his answer to correct for overcounting:

One way to compensate is to subtract all the ways the first driver can be in the car when the first is the driver, since those have already been counted. In my little example, we subtract 1 to get the correct answer, 3. In your problem, if I'm thinking correctly, for the no-twin case we have to subtract C(16,3) -- the number of ways to choose the other 3 passengers, excluding the twins. Similarly, in the two-twin case, we have to subtract C(16,1), the number of ways to choose the one other passenger in addition to the first driver and the twins. 

So the net counts are

    no twins in car: C(2,1)*C(17,4) - C(16,3) = 4760 - 560 = 4200

  both twins in car: C(2,1)*C(17,2) - C(16,1) = 272 - 16 = 256

The total is 4456, which is the same as my count. That greatly increases my confidence in my answer. (Don't tell anyone, but I got a slightly different answer first, and comparing with my original answer led me to see a silly mistake I'd made.)

(As I said before, “I’m never quite sure until I’ve found two ways to get the same answer!” Here, when two answers differed, it helped me correct the one that was wrong.)

Does it matter who drives?

Oscar still didn’t quite get the driver issue:

Odd. I thought I made it clear that there had to be a driver in the driver's seat. Never mind now, I can see where you're coming from and I understand the working fine now. 

Thank you for taking your time to help me with this question.

I replied, focusing on that:

Of course there's a driver in the driver's seat; that can't not be clear. But what was the original question?

  Twenty students must return from a school camp.
  There are two ways of getting back home. There
  is a 5-seat car and a bus. Two of the students
  have a license to drive, and there is a set of
  twins who have to go home together.

  If the driver for the bus is already accounted
  for, how many ways can 5 people be chosen to go
  home in the car?

It's about ways to choose who is in the car -- NOT about choosing who is in the car AND who drives it. It's not about where people are sitting. So we can't distinguish between A driving and B being a passenger, vs. B driving and A being a passenger. All that matters is that there is a driver.

In combinatorics, the exact wording of a question is always important; that is why it is easy to be accidentally ambiguous, and also why these problems can be very difficult.

(It happens that I gave a test last week that included a question I thought was straightforward. But when I looked at the first student's answer, I realized I had used a wrong word, rendering the question either ambiguous or simply more difficult than the course is supposed to be -- so I had to discount the question.)

Oscar was still confused:

But but but ... the original question asks for how many ways can 5 people be chosen to go home in the car. They can't get home if there isn't a driver in the driver's seat driving the car, right?

I answered:

Hi, Oscar.

We can certainly say that this is another ambiguity of the original question (which I am presuming you quoted exactly). But just as I read it as saying that two people are drivers and two OTHER people are twins, I definitely read it as asking about ways to choose the five people, without distinguishing who is driving. (Depending on distance, there's good reason to suppose that if there are two drivers in the car, they might take turns, anyway.)

This is similar to the sort of question where we ask, on one hand, how many ways there are to choose a committee of two from a club of 20, and, on the other hand, how many ways there are to choose a president and a treasurer from a club of 20. The members of the committee may well play different roles, but the first question does not distinguish the two committee positions, and so is a combination problem; whereas the second explicitly distinguishes them, making it a permutation problem. In the same way, choosing five people is distinct from choosing what seats some or all sit in.

If we don’t care who sits in the back seat, we don’t care who sits in the driver’s seat either, as long as there is someone who can do so. If the question were stated differently, though, we might care.

Repairing the problem

Now the discussion changed direction, as I continued:

Rather than disagree about how to interpret the problem you stated, perhaps a more useful thing to do is to work on how to state the problem clearly, given any of the various interpretations we have been considering. I would certainly want to do this before putting the problem on a test.

Here is my version, edited from yours:

  Twenty students must return from a school camp.
  There are two ways of getting back home. There
  is a 5-seat car and a bus. Two of the students
  have a license to drive and two other students
  are twins who have to go home together.

  How many ways can 5 people be chosen to go home
  in the car, given that there must be at least
  one licensed driver in the car, but it is not
  necessary to choose who will actually drive?

Would you like to write the problem in a way that makes your interpretation explicit? You might also try to write a version that explicitly allows one or both twins to be drivers, though that would be considerably harder.

Oscar didn’t offer an alternative problem, though that would have been interesting to pursue:

I see. So it really all boils down to how the question is interpreted. My teacher said something like that as well when we came across a question asking for the number of combinations of a committee if there is to be a majority of women. 

Anyways, thanks for the help. I really appreciate it.

This was an interesting discussion, in part because students don’t often get to see the work that goes into designing a good problem, which can reveal new perspectives on interpretation. And in real life, posing a problem clearly is often a major part of solving it! A computer programmer, for example, may need to spend a good deal of time discussing what a program should do (with a client or boss who requests it, or in designing something for himself) before ever starting on the work. Or, in starting to write a program he may discover that the goal has to be refined in order to make it possible to write the program.