Really simple mistake in this combinatorics problem?

  • B
  • Thread starter tellmesomething
  • Start date
  • Tags
    Combinatorics
  • #1
tellmesomething
269
27
TL;DR Summary
A combinatorics problem solved in a needless and agonizing way. Found clever alternate solutions but do not understand why and how it works.
Right, so i came across this problem
Eight runners wearing their favorite colored jerseys have just completed a 100m race and we know the following results.
The BLUE runner finished AHEAD of the TEAL runner The PINK runner finished AHEAD of the GREEN runner The PURPLE runner finished AHEAD of the ORANGE runner
The GREY runner finished AHEAD of the RED runner.
How many different ways can the eight runners finish the race?
My approach was uninteresting and not clever at all. I started making cases i had to make about 14 of them and while it didnt take long,i think it would have been very tedious for a bigger number say 16 players. But it was logical and i got my answer.

Smart approach: I found this
Each restriction divides the total number of permutations by 2. Since they are symmetric and independet, you have 8!/(2^4).
Can someone please explain whats happening here? I understand that 8! is the total number of ways to arrange the players if there were no restriction, but the dividing by 2^4 i do not get.

Thankyou.
 
Last edited by a moderator:
Physics news on Phys.org
  • #2
Of the total number, half have Blue ahead of Teal and half have Teal ahead of Blue. We can exclude half of these. Of the remaining ones, half of those have Pink ahead of Green and half Green ahead of Pink, so we can exclude half again. Then reduce by half twice more.
 
  • Like
Likes DrClaude, Vanadium 50 and tellmesomething
  • #3
PeroK said:
Of the total number, half have Blue ahead of Teal and half have Teal ahead of Blue. We can exclude half of these. Of the remaining ones, half of those have Pink ahead of Green and half Green ahead of Pink, so we can exclude half again. Then reduce by half twice more.
Hm okay.. say if there were restrictions on 3 jerseys like pink ahead of teal teal ahead of gray.... something like this would it be divided by 3?
 
  • #4
tellmesomething said:
Hm okay.. say if there were restrictions on 3 jerseys like pink ahead of teal teal ahead of gray.... something like this would it be divided by 3?
What do you think?
 
  • #5
Suppose there were three runners: pink, teal and gray. How many ways can they finish a race? How many ways if pink finishes ahead of teal and teal ahead of gray?
 
  • #6

PeroK said:
Suppose there were three runners: pink, teal and gray. How many ways can they finish a race? How many ways if pink finishes ahead of teal and teal ahead of gray?
Total number of ways without restrictions would be 3!. But with the added restriction it would only be 1? So 3!/3!
 
  • Like
Likes PeroK
  • #7
So, it was divided by ##3!## and not 3(!)
 
  • Like
Likes tellmesomething
  • #8
PeroK said:
So, it was divided by ##3!## and not 3(!)
I must learn learn LaTex soon. Thankyou.. if you have some time i posted a doubt on chemistry forum regarding thermodynamics
 
  • #9
tellmesomething said:
I must learn learn LaTex soon. Thankyou.. if you have some time i posted a doubt on chemistry forum regarding thermodynamics
I know more about combinatorics than I do about thermodynamics!
 
  • Like
Likes tellmesomething
  • #10
Be careful. "Blue ahead of Teal and Pink Ahead of Gray" is not the same as "Blue ahead of Teal and Teal Ahead of Pink".

I would look at it this way. There are 8! possible outcomes. Half have Blue Ahead of Teal and the other half have Teal Ahead of Blue. So that constraint reduces this to 8!/2.

Half of the remaining ones have Pink Ahead of Gray and the other half have Gray ahead of Pink. So that reduces it to 8!/4.

And so on.
 
  • Like
Likes tellmesomething
  • #11
PeroK said:
I know more about combinatorics than I do about thermodynamics!
Makes sense. I would choose combinatorics over thermodynamics as well though i know very little of each!
 
  • Like
Likes PeroK
  • #12
Test to see if you get it. Suppose we make exactly one change to the problem - Teal comes in last. How many possibilities are there?

630
[/ISPOILER]
 
  • #13

Vanadium 50 said:
Test to see if you get it. Suppose we make exactly one change to the problem - Teal comes in last. How many possibilities are there?

630
[/ISPOILER][/SPOILER

Sorry for the late reply. The only restriction is teal comes in last? And everything is allowed?

Or is this is an added restriction to my original problem?
 
  • #14
tellmesomething said:
Sorry for the late reply. The only restriction is teal comes in last? And everything is allowed?

Or is this is an added restriction to my original problem?
Why not do both?
 
  • #15
PeroK said:
Why not do both?
Sure then I think, if we are considering only the restriction that teal comes in last, we can basically fix its place in the last position and the number of ways to arrange the remaining players would be 7! ?

If we consider the restriction of teal coming last in addition to pink ahead of green , purple ahead of orange and grey ahead of red, we can first count the total arrangements with the only restriction that teal comes in last I.e 7!
Then i think we must eliminate the half of the arrangements where pink is ahead of green so (7!/2!)
Purple is ahead of orange (7!/2!*2!)
Grey ahead of red (7!/2!*2!*2!)
?

 
  • Like
Likes Vanadium 50 and PeroK
  • #16
I think you have it.

If you want to apply it to a somewhat different situation: you're assigning the 8 runners to 8 lanes on a track. Blie must be next to Teal, Pink must be next to Green, Purple must be next to Orange, and Gray must be next to Red. How many ways to do this?

384
 
  • #17
Vanadium 50 said:
I think you have it.

If you want to apply it to a somewhat different situation: you're assigning the 8 runners to 8 lanes on a track. Blie must be next to Teal, Pink must be next to Green, Purple must be next to Orange, and Gray must be next to Red. How many ways to do this?

384
We can maybe think of them as pairs of two which are tied to each other, so it looks like they are one
For eg
Blue and teal; 1 whole person (one cannot be without the other)
Pink and green: 1 whole person
Purple and orange: 1 whole person
Gray and red: 1 whole person

So we essentially have to arrange 4 whole persons/groups which can be done in 4! ways.

Within each group they can be arranged in 2! ways

So: 4!*2!*2!*2!*2!
 
  • Like
Likes Vanadium 50
  • #18
tellmesomething said:
Purple is ahead of orange (7!/2!*2!)
Grey ahead of red (7!/2!*2!*2!)
?
That should be 7!/(2!*2!) and 7!/(2!*2!*2!)
 
  • #19
Vanadium 50 said:
Be careful. "Blue ahead of Teal and Pink Ahead of Gray" is not the same as "Blue ahead of Teal and Teal Ahead of Pink".

I would look at it this way. There are 8! possible outcomes. Half have Blue Ahead of Teal and the other half have Teal Ahead of Blue. So that constraint reduces this to 8!/2.

Half of the remaining ones have Pink Ahead of Gray and the other half have Gray ahead of Pink. So that reduces it to 8!/4.

And so on.
One should nevertheless be careful if one has several of these restrictions.
The statement in the OP can not be correct if just taken as is: namely, "if you have n binary restrictions (A comes in after B) you divide by ##2^n##.
There's namely a very simple counter example: consider 3 runners, a, b and c. In total, there are 3! ways of arriving. Now suppose that we have two binary conditions: a comes in before b, and b comes in before c. That would mean ##2^2##. But 6 / 4 isn't an integer. There is actually only one outcome with these restrictions.
So I guess this is only correct if the pairwise conditions are independent (don't mention same participants twice).

The reason is that once you introduce the condition: a comes in before b, then a and b are not distributed uniformly anymore over the slots. a has tendency to be more "in the front" and b has tendency to be "more in the back". So next time there's a condition on a or b, you can't just say, "there are as many a in front of c as behind c".
 

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Precalculus Mathematics Homework Help
Replies
1
Views
3K
Replies
13
Views
3K
  • Precalculus Mathematics Homework Help
Replies
13
Views
4K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
5
Views
2K
Back
Top