Combinatorics!

[griffin.811]

Hi,

My question is around the structure of combinatorics questions.

I've come across questions that say something like "there are x teams in a league, each team plays each of the others exactly once, if a game involves two teams, what is the min number of games that can be played" and the result would be (x!)/(2!6!).

How would I attack this question if, instead, it read "each team plays each of the other teams exactly twice...?" would this be 2[(x!)/(2!6!)]?

What if each team only played half of the other teams exactly once? What does this look like?

Thanks!

[RonPurewal]

a game involves two teams, what is the min number of games that can be played" and the result would be (x!)/(2!6!).

Where are you getting the "6" from?
Unless there are exactly 8 teams in the league, that's going to give the incorrect answer.
If the league happens to have exactly 8 teams then this formula will work, but, it's not a very intuitive approach.

More tellingly, you're leaving this "6" in the formula (and it's definitely not a typo, since you have it there twice).
If you have that "6" in there, then you're not thinking—at all—about WHY you're doing the math you're doing. You're just pushing meaningless symbols around a page. Not good.

[RonPurewal]

The factorials are from "combination"/"permutation" formulas (can't remember which term is correct here).
The thing with these formulas is that, for this exam, they're both inefficient and unnecessary.

Let's say there are, indeed, 8 teams in the league.
Ok. Then there are 8 choices for one team in a game, and 7 choices for a second team.
But this scenario will double-count every game—e.g., you're counting both "A vs. B" and "B vs. A"—so you need to divide by 2.
(8 x 7)/2

Believe it or not, the formula actually comes from UN-simplifying this expression.
(8 x 7 x 6 x 5 x 4 x 3 x 2 x 1) / 2(6 x 5 x 4 x 3 x 2 x 1)
= 8! / 2(6!)
That's right—the formulas with factorials are deliberately less efficient.
Believe it or not, the only purpose of this un-simplification is to make formulas that look pretty.
Not kidding at all. Mathematicians think that factorials are more aesthetically attractive than formulas with long products, so they actually un-simplify expressions to make such formulas.
You're not a mathematician, and there's zero need to generalize formulas here, so no advantage is gained (and there's the obvious disadvantage that the formula becomse more inefficient and labor-intensive, not to mention less intuitive).

[RonPurewal]

How would I attack this question if, instead, it read "each team plays each of the other teams exactly twice...?" would this be 2[(x!)/(2!6!)]?

If every match-up is played twice, then, yes, you'll get twice as many games as if every match-up is played once.

The formula is incorrect, though, for the same reasons described in the posts above.

[RonPurewal]

MOST IMPORTANTLY

On official problems—
If you don't IMMEDIATELY know how to calculate the number of possibilities, JUST START MAKING A LIST.

On literally every GMAC combinatorics problem I've seen—excepting only the most basic ones (just straight products)—it has been quite feasible to just list out all of the possibilities.

For instance, if there are 8 teams in a league, you can very easily just list all the games:
Team 1 vs 2, 3, 4, 5, 6, 7, 8 (7 games)
Team 2 vs 3, 4, 5, 6, 7, 8 (6 more games)
Team 3 vs 4, 5, 6, 7, 8 (5 more)
Team 4 vs 5, 6, 7, 8 (4 more)
Team 5 vs 6, 7, 8 (3 more)
Team 6 vs 7, 8 (2 more)
Team 7 vs 8 (1 more)
7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 games.
You should be able to make this list in 30 seconds or less. If you can't, then forget about the combinatorics formulas, and practice the lowly art of making lists.

One of the tragic aspects of the MGMAT CAT exams is that the numbers on combinatorics problems are, unfortunately, usually much bigger than the numbers in official problems.
The tragedy is that listing and counting possibilities—which just about ALWAYS works on official problems, as long as you don't dilly-dally too much before you get started—doesn't work nearly as often on the MGMAT problems. It becomes a tragedy if people decide, as a result, that trying to make a list "isn't worth it".
This is something that's in the queue of Things To Be Fixed/Things To Do. But there are a lot of other things in that queue.

[griffin.811]

Thanks Ron. I definitely did mean to say that there were 8 total teams, sorry for the confusion there. Nice to know that lists should work with the relatively smaller numbers on the exam.

[RonPurewal]

Thanks Ron. I definitely did mean to say that there were 8 total teams, sorry for the confusion there. Nice to know that lists should work with the relatively smaller numbers on the exam.

Making lists really does work just about every time. It's like a secret weapon that's not secret at all.

The real problem is psychological. I've had students who wouldn't even consider listing out the possibilities because they "felt dumb" doing so. Weird, but true.