Determining the complement of a set in a solution and interpretation of the problem statement

35 Views Asked by At

I was reading the following exercise (in a section for the pigeonhole principle):

There are $42$ students who are to share $12$ computers. Each student uses exactly $1$ computer and no computer is used by more than $6$ students. Show that at least $5$ computers are used by $3$ or more students.

My question is about the problem statement and a part of the solution presented in the text.

For the problem statement question: I think the statement

at least $5$ computers are used by $3$ or more

is non nonsensical. Since $1$ student uses exactly $1$ computer it is impossible for $5$ computers to be used by $3$ students. Shouldn't the statement have been

at least $5$ computers are used by $5$ or more

Am I interpreting this the wrong way?

For the solution part:
The solution uses an argument by contradiction. So starts by supposing it is not the case that at least $5$ computers are used by $3$ or more. So we assume that $4$ or fewer computers are used by $3$ or more students. So far so good. Then the solution states:
Since $12 - 4 = 8$ or more computers are used by $2$ of fewer students.
But I don't understand this.
So apparently
When we have the statement

$4$ or fewer computers are used by $3$ or more students

is the complement of that statement that

$8$ or more computers are used by $2$ of fewer students

?
But how did we figure out that this is the correct statement?

1

There are 1 best solutions below

2
On BEST ANSWER

I think "at least $5$ computers are used by $3$ or more students" means "we can find $5$ computers: A, B, C, D, E, such that A is used by at least 3 students, B is used by at least 3 students, and so on".

For solution, each computer falls into one of two groups: "used by 3 or more students" or "used by 2 or fewer students". This groups don't intersect, and their combined size is $12$. So, denoting the size of the first as $x$, and of the second as $y$, we have $x + y = 12$, statement "4 or fewer computers are used by 3 or more students" means $x \leq 4$ and statement "8 or more computers are used by $2$ or fewer students" means $y \geq 8$.

As $x + y = 12$ implies $y = 12 - x$, so $x \leq 4$ is equal to $12 - y \leq 4$, which, in turn, is equal to $y \geq 8$.