Five girls have a little store that opens from Monday through Friday. Since two people are always enough for taking care of it, they decide to do a work plan for the week, specifying who will work each day, and fulfilling the following conditions: a) Each girl will work exactly two days a week b) The 5 assigned couples for the week must be different In how many ways can the girls do the work plan?
Problem
Source:
Tags: geometry, rectangle, combinatorics proposed, combinatorics
09.06.2008 03:11
Working by inclusion-exclusion principle, there are $ {5 \choose 2} = 10$ possible pairs, so there are $ {10\choose 5}$ possible plans. We then take out those plans where a girl appears exactly three times, which are $ 5{4\choose 3}{6 \choose 2} - {5\choose 2}{3\choose 2}{3\choose 2}$, then we take out those plans where a girl appears exactly four times which are $ 5{4 \choose 4}{6\choose 1}$, so there are $ {10\choose 5} - \left(5{4\choose 3}{6 \choose 2} - {5\choose 2}{3\choose 2}{3\choose 2}\right) - 5{4 \choose 4}{6\choose 1} = 12$ valid plans and $ 5!$ permutations of them all, giving a total of 1440 ways to make a plan.
10.06.2008 19:43
I got the answer in a different way, as $ {5\choose2}\cdot4\cdot3\cdot3\cdot2\cdot2\cdot1\cdot1$ Here is how: Create a 5x5 chart, with each row containing the day of the week and each column containing the name of a girls(the girl's names are A,B,C,D, and E). Each row and column must have exactly two X's, but no rectangle can be formed by four X's, or you'd have the same combiation of two girls on two days. So we start out by picking the two people who go on Monday, call them A and E. There are $ {5\choose2}$ ways to do this. Now choose the other day A works on, let it be Friday, there are 4 possibilities. Now, the other person who goes on Friday must be B,C, or D(not E, or we have a rectangle). Let's say it's B (there were 3 choices). The other day B goes on is either Tues, Wed, or Thur. Let's say it's Thur (there were 3 choices). Consider the other person on Thur. There are 2 possibilites. Keep doing this and you get the answer.
18.06.2008 00:28
I have another way. First will look up for the number of sets with five couples of girls (girls working the same day) which satisfy the conditions. Represent each girl as a dot and if two girls are couple in a schedule join their respective dots with a line. Also number the dots to identify each girl. Let's say that dot number one is joined with dots $ a$ and $ b$, with this given there are only two ways in which we can join the other points (prove it yourself) so they satisfy the conditions given by the problem. For the election of this $ a$ and $ b$ there are $ _4C_2$ ways and two ways of completing each so there are in total $ 12$ ways of choosing the couples. Each of these $ 12$ five-couples sets can be ordered in $ 5!$ ways. So there are $ 12\cdot 5!$ ways to set up the work plan.