I am quite rusty on combinatorial formulas, but I think the following practical question has a combinatorial answer. This is not homework.

A company gives it's technicians two work days per week to work at home. In a team of four, a manager and three technicians, what assignment of days working at home will gurantee that at least one technician or the manager is NOT at home on every working day (Mon-Fri)? I.E., at least one person from the team of four is in the office every working day.

There are only 10 unique combinations of two weekdays (5 things taken 2 at a time), so I think the question becomes which of the combinations of two days among four employees satisfies the constraint that the count of any one of the days assigned to work at home among the four employees is less than 4 (thus guaranteeing that for any weekday at least one employee is NOT at home)?

If I haven't formulated this question correctly, please enlighten me and help cure my ignorance (and rusty mathematics).



[Edit] Based on one of the answers I have seen so far, I need to clarify two things:

  • All four team members always have two scheduled days at home each week
  • I would like to know if there is a way to generate combinations of scheduled days at home for the whole team which satisfy the constraint of at least one team member not at home each weekday

The team has a total of eight days off and twelve days in per week. You can get that with one person at home two of the days and two people at home the other three days. You have two or three people in the office each day.

There are many other combinations, but it is easy to guarantee at least one person in the office or even two.

  • $\begingroup$ The number of days at home for each person is always 2, so that solution is not viable. Sorry if I was not clear, two days at home for each person is not optional, it is required. $\endgroup$ – pjfarley3 Apr 20 '13 at 1:15
  • $\begingroup$ @pjfarley3: I got that. I was counting person-days in and out. For example, one could be out MW, one TT, one MF, one WF. Then you have two people out MWF and one out TT. Each is home twice. There are lots of combinations that meet your requirement. $\endgroup$ – Ross Millikan Apr 20 '13 at 1:23
  • $\begingroup$ Yes, but how does one generate such a list of combinations which satisfy the constraint? This is only one example of the problem of course. It gets much too complex for "answers by inpection" for teams with larger numbers of members. $\endgroup$ – pjfarley3 Apr 20 '13 at 1:39
  • $\begingroup$ @pjfarley3: each person has 10 possible pairs of days off. As the other answer says, most of them are acceptable. The easiest way here is to generate a list of all 10,000 possibilities (four loops to 10 will do that) and throw out the ones that don't work. Since these are exactly the ones that have everybody off, it is easy to check. $\endgroup$ – Ross Millikan Apr 20 '13 at 1:42
  • $\begingroup$ OK, so the generation is just "brute force" then, with a constraint check on each generated set. I had been hoping for a more elegant mathematical solution, but if there isn't one then I can go the other way. Thanks for your help. $\endgroup$ – pjfarley3 Apr 22 '13 at 18:42

This is an inclusion-exclusion problem.

Call $S$ the set of all $10^4=10,000$ schedules. Let $M$ denote the subset wherein all four take a day off on Monday. We calculate $|M|=4^4=256$ -- each of the four people chooses one of four remaining days for their second day off. Let $T$ denote the subset wherein they all take Tuesday off. We have $|T|=256$. Similarly, we have $W,R,F$ for Wednesday, Thursday, Friday.

However, the answer isn't simply $|S|-|M|-|T|-|W|-|R|-|F|=10,000-5*256=8720$. Consider the schedule where everybody takes Monday and Tuesday off. We counted it once in $|S|$, but subtracted it twice -- once in $|M|$ and again in $|T|$. Hence we need to add it back in, so we count it a total of zero times. There are ${5 \choose 2}=10$ such issues, one for each pair of days. Thus the answer is $8730$.

  • $\begingroup$ That's interesting, but it seems to me that it only tells us how many solutions there are, not how to generate actual solution sets. I would like to know if there is a mathematical solution that generates combinations of days at home for the four team members that satisfy the constraint of at least one team member not at home each day of the week, while all team members are guaranteed have two days at home each week. $\endgroup$ – pjfarley3 Apr 20 '13 at 1:21
  • $\begingroup$ Well, over 87% of all schedules are acceptable, so just pick a schedule at random and toss it out if it doesn't meet the criterion. $\endgroup$ – vadim123 Apr 20 '13 at 3:27

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.