Sunday, June 29, 2008

Probability and Counting Challenge -- You'll Need To Sit Down for This One

Five people with first initials A, B, C, D and E were seated randomly in a row in a movie theater with no spaces between them. What is the probability that A, B and C were adjacent to each other in some order? (For example: "DBACE")

A potential SAT problem or is it a level above? A math contest problem or not difficult enough? More importantly, how much experience do most of our students have with these kinds of combinatorial problems? I know that some of our educators who visit here do these with their classes, but is it the norm? My feeling is that students need to see many of these developed over time in more than one course.

What method (s) do you consider the most effective for solving these kinds of problems? For teaching? Are these 2 questions really the same?

After this question is discussed with the class, how does the instructor assess the learning? Give them another one to try immediately or give a worksheet of these (if the text does not provide enough practice)? How could one raise the bar even higher?


Suggested Extension #1: This time we have 10 people seated randomly in a row (no spaces). What is the probability that 4 of them, say A. B, C and D, would be adjacent to each other?

Suggested Extension #2: N people seated randomly in a row (no spaces). What is the probability that a particular subset of M of these people would be adjacent to each other?

Your thoughts...

9 comments:

Anonymous said...

ABCDE, 5! = 120 seating orders.

XDE where X represents ABC in any order, 3! arrangements of XDE times 3! manifestations of X = 36 orders.

36/120

These are very very hard for kids. I would strongly encourage a complete listing, and then discussion.

Perhaps ABCD with AB together would be a good warmup.

ABCDE with AB together might be easier to visualize, and avoids 3! popping twice with different meanings.

We can also ask P(A,B non-adjacent), but only to show that it is very very different. When attacking counting problems it is unforgivable to turn your brain off.

Of course an answer can be reasoned out of P(A,B,C non-adjacent), and I find more value there as it pushes the student back to first principles and away from relying on a formula.

And we can re-ask each of these in terms of seating around a circular table... in one case the probability goes to 0, but in others the math is interesting and the relationship to the original question may be surprising.

Dave Marain said...

Nice discussion, Jonathan!
I definitely would not start with this question. 'Make it simpler' and encouraging enumeration in the beginning is definitely the way to go. Your non-adjacent variation is important as well as bringing in circular permutations into a broader discussion. You're right on target when you say that most struggle with these. I do feel that repeated exposure with increasing levels of difficulty starting in middle school would make a huge difference. Agree?

I appreciate that you responded more to the pedagogy here than the problem itself!

Anonymous said...

Do remember, I teach a 1 term counting course as a junior/senior elective.

Listing (enumerating) is a skill to be taught. I have "make a complete list" question on every test.

As far as earlier grades, I would recommend off-topic problem solving (or challenges) only. The first introduction to permutations, as such, or combinations, as such, needs to be delayed until after the point that children count well. Otherwise the child will guess which formula works in a particular situation, C, P, !, multiplication, addition, and be correct about 20% of the time. It's really horrific.

Jonathan

Anonymous said...

Another way to solve this problem is to use combinations:

Given a permutation of ABCDE, what are the odds that the first three are ABC in any order? The first three considered as a set, not a sequence, form a random combination, of which there are C(5, 3) = 10. Only one of them is ABC, and so the odds of the first three being ABC is 1/C(5,3).

Now, how many ways can you fit a sequence of 3 in a sequence of 5. Just 3: 1–3, 2–4, 3–5. And the permutations where ABC are in 1–3 are distinct from the ones where they are 2–4, and so on. Obviously, each one gives the same probability, 1/10 = 1/C(5,3). So, the answer is 3/C(5,3).

However, there is a chance students would not get the correct general formula for extension 2 from this example. Unfortunately, the 3 in the numerator might seem as if it comes from the 3 in the original problem. So, do the problem with 3 replaced by 2, or even replaced by 1. The answers will be 4/C(5, 2) and 5/C(5,1). Now, the students should see that the numerator is N - M + 1, not M, and definitely not N - M (off-by-one error!). So, the answer is (N-M+1)/C(N,M).

Note that extension 2 is easier than extension 1.

Combinatorics can provide infinitely many examples to your students, most of which can be visualized easily.

Dave Marain said...

Thank you, Eric, for that alternate view of the universe!

What I think is particularly instructive for students is to help them view the relationship between C(N,M) and P(N,M) in a variety of ways. This surely develops mental flexibility!

In this problem, Jonathan and I both viewed it as an 'arrangements' problem. Here's one way to link it it your approach:

For any particular placement of the M objects, there are P(M,M) = M! arrangements. Similarly there are P(N-M,N-M) = (N-M)! arrangements for the remaining objects. Thus, the probability for such a placement is (M!(N-M)!)/N!, which we would hope students would recognize is the reciprocal of C(N,M)!!! (The 3 exclamation points for exuberance). And this is only one of many interpretations for C(N,M).

noone said...

I don't think this would be hard for kids (I mean 7-8th grade and above) at all as long as the children learn to think of objects in more abstract terms. We have done something like this with some classes before (note: I'm not a teacher, but worked in a program, as a math graduate student, which aimed to encourage and enrich mathematics education in middle schools).

At any rate, our kids wouldn't differentiate between A, B and C, and would treat the string 'ABC' (without regard for order) as one object, call it O. They would compute the total number of permutations of three objects: O, D, E, which obviously equals 6. Having done so, they now would need to account for rearrangements of ABC. There is total of 6 such. For each rearrangement of O,D,E, there are six "representations" of O. Hence a total of 36 ways our desired sitting can be achieved.

noone said...

PS. After all, isn't this how mathematicians should think? The emphasis, in my opinion, must always be on the concept; however, one need not forget that one operates, often times, not on the information but on its representation. Learning to represent and to "read" information is, in my opinion, a substantial part of success in any science.

noone said...

PS. Oh, right, so the probability is 36/120 = 3/10.

Dave Marain said...

What a great comment pffft!
I always tried to convey to my students that mathematics can often be viewed as the science of equivalent 'forms.' I cannot imagine how many times I used the phrase "rewrite that expression."

I also agree with you that middle school students can handle these kinds of questions. After younger students have been making organized lists, they move on to counting by grouping which morphs into the Multiplication Principle (which used to be called the Fundamental Principle of Counting).

More important than any of this is the benefit in improved reasoning that results from tacking combinatorial problems. As Jonathan pointed out, there is no simple formulaic approach that "always" works. Many different strategies are needed and only from experience with dozens of these does one begin to recognize effective approaches.

In the end, I always told my students to begin each counting problem by making a list. It doesn't have to be organized at first -- just start listing until a "form" becomes evident! If it's an easily recognized problem go with methods you know will work. If not sure, DO NOT resort to meaningless formulas that fail most of the time!

Your students' approach to these is admirable. "Chunking" ABC, i.e., treating these people as a single entity, is an important stage of development. Bravo!