Smallest number of absent workers in a factory

Question

I am trying to solve a brainteaser and would like some direction if my line of thought is correct...

At a worker plant, 25 workers were absent on Monday, 22 absent on Tuesday and 19 absent on Wednesday. If none of the workers were absent on all three days, what is the smallest possible total number of workers absent on at least one day?

My initial thought is:

To find the smallest possible total number of workers absent on at least one day, we need to consider the overlap of absences between the days.

Let's denote:

$A$: Set of workers absent on Monday. $B$: Set of workers absent on Tuesday. $C$: Set of workers absent on Wednesday.

We are given: \begin{align*} |A| &= 25 \\ |B| &= 22 \\ |C| &= 19 \end{align*}

We need to find the smallest possible total number of workers absent on at least one day.

So $|A \cup B \cup C| = |A| + |B| + |C| - |(A \cap B)| - |(B \cap C)| - |(A \cap C)| + |(A \cap B \cap C)|$

Would I then be correct in assuming the maximum overlap happens on day 1 and 2, i.e. 22? Following this logic I end up with a value greater than any of the total absentees on one day which I believe to be wrong?

Answer 1

Let us denote $x= |A \cap B|$, $y=|B\cap C|$, $z=|C\cap A|$. As you stated we want to maximize $x+y+z$. We have that $x+z\leq 25$, $y+x\leq 22$, $z+y \leq 19$. Add these and divide by $2$, we get that $x+y+z \leq 33$. Now let’s try find such $x,y,z$ that $x+z=25$, $y+x=22$, $z+y=19$. Then $x+y+z$ will be equal to $33$. Add the first and the second equation, subtract the third, we get: $2x=28$. So $x=14$. Then $z=25-14=11$ and $y=19-11=8$.

The answer is $25+22+19-33=33$ then.

Essentially, we make all the workers miss two days. Intuitively, it is clear that it is the optimal way.

Answer 2

Let's see if we can solve this problem more like a puzzle. We start by re-imagining the problem in a way that makes it easier to visualize.

The Problem Re-imagined

There are 25, 22, and 19 cards labeled M, T, and W respectively. We need to place these cards in envelopes such that -

1. No envelope contains more than $2$ cards.
2. No envelope contains $2$ cards with the same label.

What is the minimum number of envelopes needed? $^{[1]}$

Solution

It's intuitively clear that to minimize the number of envelopes, we must utilize each envelope as much as we can. Ideally each envelope would be full - containing two cards.

Step 1. Since two identical cards can't go into the same envelope, we need at least $25$ envelopes to begin with - one for each M.

At this stage, we have $25$ empty spaces left in the $25$ envelopes. [There is $1$ M in each.]

Error - Now, one might think (as OP did) - let's put the $22$ Ts in these spaces. But that's not a good strategy. We will be left with $19$ Ws. $3$ of these, we can place in the $3$ empty spaces. But for the remaining $16$, we will need one envelope each. So $16$ underutilized envelopes. Too bad!

Step 2. Here's what we do. We pair Ts and Ws together - as many as we can. So we have $19$ pairs and $3$ Ts that couldn't be paired.

The $3$ leftover Ts need a home, so we put them with the Ms in $3$ envelopes.

Great. Now, we have $22$ empty spaces left (in envelopes from earlier) and $19$ TW pairs left.

Step 3. $11$ of the TW pairs go into the $22$ empty spaces.

This fills us the $25$ envelopes we started with.

Step 4. Remaining $8$ TW pairs go into $8$ other envelopes.

That's it. We used $25 + 8 = \mathbf{33}$ envelopes and all of the cards have a home. all of the envelopes are fully utilized, so we couldn't do better.

---

$^{[1]}$ Each envelope represents a worker. An envelope with cards M and W in it represents a worker who was absent on Monday and Wednesday.