I've been thinking about an ordinary problem for which there doesn't seem to exist a solution given its constraints. I was wondering how would one go about formulating the problem mathematically such that the non-existence of the solution can be proven.

An example:

4 flatmates {1,2,3,4} are deciding on how to distribute 4 housekeeping tasks: garbage disposal (G), grocery shopping (S), big bathroom cleaning (B1), small bathroom cleaning (B2).

The conditions are (weeks should be understood as 7 days, not calendar weeks):

1) Tasks G, B2, and S must be completed every week.

2) Task B1 must be completed twice within every week, but not on the same day.

3) Tasks B1 and B2 are completed simultaneously by one flatmate once a week in order to reduce overhead.

4) Each flatmate must complete each task at least once.

5) Flatmates 1, 2, and 3 can complete tasks on Monday and Thursday.

6) Flatmate 4 can only complete tasks on Monday.


  • Is it possible to divide the housekeeping such that over the course of 4 weeks all flatmates complete the exact same number of tasks?

  • If not, what distribution of tasks meets the conditions and minimizes the total number of tasks over the course of 4 weeks?

  • How would the generalization of this problem (and its solution) look like if there are n flatmates, m tasks, and not only flatmate 4 has a time constraint?

  • $\begingroup$ how much time does each task need to be completed? $\endgroup$ – dcolazin May 15 at 22:08
  • $\begingroup$ Do the two cleanings of the big bathroom have to be on different days? If not, then I'd volunteer to clean it immediately after you've thoroughly cleaned it. (The point is that you probably have more assumptions than you've explicitly stated.) $\endgroup$ – Andreas Blass May 15 at 23:22
  • $\begingroup$ @AndreasBlass haha very good point. Yeah, some real world assumptions are in there (adjusted accordingly, thx!). $\endgroup$ – nomadStack May 17 at 13:52
  • $\begingroup$ @dcolazin assume an hour $\endgroup$ – nomadStack May 17 at 13:58

Your Answer

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

Browse other questions tagged or ask your own question.