2
$\begingroup$

There are 15 different students, 3 students each from 5 different high schools. There are 5 admission officers, one from each of 5 colleges. Each of the officers successively picks 3 of the students to go to their college. How many ways are there to do this so that no officer picks 3 students from the same high school?

\ \

I am struggling quite a bit to answer this question. I started by realizing there is ${19\choose 4}$ ways to assign the students to colleges in total since there are 15 students and 5 potential colleges. Then I tried to assign the colleges to the students, but I realize this is an issue because I'm not sure exactly how to assign the schools to students in such a way that no 3 students are selected from the same high school.

I also thought maybe assign the students students to the colleges. In this case, from each high school there are 3 students that have the potential to go to 5 X 5 X 4 colleges since the first student can go to any of the five colleges, the second student can go to any of the five colleges and the last student has only 4 remaining colleges to choose from since the restriction is such that all three students from a certain high school can't all go to the same college. I would assume using this method you would do this again four more times for the other 5 high schools and then would get: $(5 X 5 X 4)^5$ = $100^5$. I would also assume you should multiply this by 3 (or maybe 3!) to account for the potential arrangements of students within the high schools.

I guess this would leave me with an answer of either 3($100^5$) or 3!($100^5$).

Can someone let me know if I am at least on the right track? I'm still very confused...

$\endgroup$
  • 1
    $\begingroup$ Inclusion Exclusion works here. Figure out the total number of ways to choose three each, then subtract off the cases where one school gets all three from one high school, then add back the cases where two schools do, and so on. $\endgroup$ – lulu Oct 13 '18 at 20:38
0
$\begingroup$

Let me get you started. I assume that a college choice depends upon the three students, not the order. So Alice, Bob, Charlie is the same as Charlie, Bob, Alice.

Call the schools $A,B,C,D,E$ and the colleges $\alpha, \beta, \gamma, \delta, \epsilon$.

Let's figure out how many ways you get all students from all FIVE schools to go to the same college (i.e., all students from school $A$ to go to the same college $\alpha$ or $\beta$ or..., and all students from school $B$ to go to the same college $\alpha$ or $\beta$ or..., and so on):

There are five colleges for the first school, then four remaining colleges for the second school, and so on. Thus there are exactly $5!$ ways to get all three students from each school to go to the same college.

result: $5! = 120$

Next, what about getting all the students from exactly FOUR schools to go to the same college? Clearly there is NO WAY to achieve that. If you obtain this for four schools, then the remaining school's students must go to the remaining college. But this is counted in the FIVE case, above.

result: $0$

Next, what about getting all the students from exactly THREE schools to go to the same college? There are ${5 \choose 3}$ such schools, and also ${5 \choose 3}$ such colleges. For any choice of three schools and three colleges, there is exactly $3!$ pairings. There are then exactly two schools and two colleges remaining. Take the first unassigned school. One of its students will go to one unassigned college, and the other two must go to the other remaining college. There are thus exactly two ways for this to happen--one for each college-- (irrespective of which lone student is chosen), and then 3 ways for that lone student to be chosen. For the remaining unassigned school, there are exactly three students who can be placed with the two in an unassigned college. The remaining students are forced.

result: $\left( {5 \choose 3} {5 \choose 3} 3!\right) \cdot 3 \cdot 2 \cdot 3 = 10800$

Can you continue?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.