Combinatorial Solution to School Admission Interview Scheduling Problem

[erisedk]

Homework Statement

Three children, each accompanied by a guardian, seek admission in a school. The principal wants to interview all the 6 persons one after the other subject to the condition that no child is interviewed before its
guardian. In how many ways can this be done ?

Homework Equations

The Attempt at a Solution

So, I read the solution to this problem, because I could only work it out with a lot of casework (I did get the right answer), but this question wasn't supposed to be that time consuming.

So, here's what I read--
No. of ways = 6C2 * 4C2 * 2C2 = 90
That doesn't make much sense to me. Help?

 

[Edwin McCravy]

Suppose the 6 people are C1,G1,C2,G2,C3,G3,
Think of the 6 of them standing in line waiting to see the principal.
There are 6 positions in which they can stand in the line.
Choose 2 of the 6 positions in the line for C1 and G1 to stand in, placing C1 behind G1.
That can be done in 6C2 ways.
That leaves 4 positions in the line.
Choose 2 of the remaining 4 positions in the line for C2 and G2 to stand in, putting C2 behind G2.
That can be done in 4C2 ways.
That leaves 2 positions in the line.
Choose 2 of the remaining 2 positions in the line for C3 and G3 to stand in, putting C3 behind G3.
That can be done in 2C2 "ways". i.e., just 1 way!

Answer 6C2*4C2*2C2

 

[erisedk]

Thanks! That was pretty neat :)

 

[haruspex]

It's even easier than that.
With no constraint, there are 6! orders. In what fraction of those are guardian 1 and child 1 in the right order? Ditto, guardian 2 and child 2? Are those two fractions independent (as in, independent events)? Etc.

 

[erisedk]

They should be independent, or I could just use symmetry to justify independence. So, that'd be 6!/(2)^3. Which does give the same answer :)

 

[haruspex]

They should be independent, or I could just use symmetry to justify independence. So, that'd be 6!/(2)^3. Which does give the same answer :)

Exactly. For every arrangement in which G1 precedes C1 there is an otherwise identical arrangement in which C1 precedes G1, just by swapping them. Hence the independence.

 

[toforfiltum]

Hmm...why do we not need to multiply the answer by 3! since there are 3 'couples' to chose from when placing them in 6C2 and so forth?

 

[haruspex]

Hmm...why do we not need to multiply the answer by 3! since there are 3 'couples' to chose from when placing them in 6C2 and so forth?

Which post are you responding to?

 

[toforfiltum]

Which post are you responding to?

No one in particular, maybe just all of the posts above, since all agreed upon the same solution.

 

[haruspex]

No one in particular, maybe just all of the posts above, since all agreed upon the same solution.

My solution in posts #4 and #6 did not involve ⁶C₂, so it can't apply to that. I'll take it as referring to Edwin's solution in post #2.

Edwin took a particular pair and chose two places in the queue for that pair, then considered the next pair, etc.
The resulting ordering does not depend on the order in which the pairs were chosen. Any given ordering of the six can result from any ordering of selection of the three pairs. If you were to multiply by the number of orders in which the pairs were selected you would count each ordering of the six six times.

 

[toforfiltum]

My solution in posts #4 and #6 did not involve ⁶C₂, so it can't apply to that. I'll take it as referring to Edwin's solution in post #2.

Edwin took a particular pair and chose two places in the queue for that pair, then considered the next pair, etc.
The resulting ordering does not depend on the order in which the pairs were chosen. Any given ordering of the six can result from any ordering of selection of the three pairs. If you were to multiply by the number of orders in which the pairs were selected you would count each ordering of the six six times.

Oh I see. So his method has covered all possibilities. I have some weakness with combinatorics, especially in cases like this when I don't know if I should multiply the choices of couples or not. I have trouble seeing that the method above has covered all possibilities.

Anyway, thanks.

 

[haruspex]

in cases like this when I don't know if I should multiply the choices of couples or not. I have trouble seeing that the method above has covered all possibilities.

You're not alone!

 

[toforfiltum]

You're not alone!

It's nice to know, because it's frustrating. I have invested a lot of time doing lots of problems like this; I've gotten better but it's still not intuitive.

If you don't mind, can you explain the other solution? I don't understand where the 2^3 come from. Are they the 3 couples grouped together?

 

[haruspex]

It's nice to know, because it's frustrating. I have invested a lot of time doing lots of problems like this; I've gotten better but it's still not intuitive.

If you don't mind, can you explain the other solution? I don't understand where the 2^3 come from. Are they the 3 couples grouped together?

There are 6! orderings of the six people. In half of these, G1 and C1 are in the wrong order, so rule those out. In half of the remainder, G2 and C2 are in the wrong order, getting us down to 6!/4. Finally, cut out those where G3 and C3 are in the wrong order.

 

[toforfiltum]

There are 6! orderings of the six people. In half of these, G1 and C1 are in the wrong order, so rule those out. In half of the remainder, G2 and C2 are in the wrong order, getting us down to 6!/4. Finally, cut out those where G3 and C3 are in the wrong order.

This solution is new to me, so I have trouble understanding it. When you say that in half of the orderings, G1 and C1 are in the wrong order, is the working suppose to be like this:
( 5+4+3+2+1) x 4!

or is it just common sense? I can't 'see' it.

 

[haruspex]

This solution is new to me, so I have trouble understanding it. When you say that in half of the orderings, G1 and C1 are in the wrong order, is the working suppose to be like this:
( 5+4+3+2+1) x 4!

or is it just common sense? I can't 'see' it.

Consider any ordering of the six. If G1 and C1 are in the wrong order you can swap them to produce an ordering of the six in which they are in the right order, and vice versa. So there must be the same number of 6-sequences with G1 and C1 in the right order as in the wrong order.

 

[toforfiltum]

Consider any ordering of the six. If G1 and C1 are in the wrong order you can swap them to produce an ordering of the six in which they are in the right order, and vice versa. So there must be the same number of 6-sequences with G1 and C1 in the right order as in the wrong order.

Ah, ok. Thanks!