0
$\begingroup$

There are 120 students at University College taking the introductory Java programming class. The students have access to the following computers:

80 students have access to a PC running Microsoft's Windows operating system.
40 students have access to a computer running the Apple operating system.
10 students have access to a computer running the Linux operating system.
30 students have access to a computer running the Apple or Windows operating system.
7 students have access to a computer running the Windows or Linux operating system.
5 students have access to a computer running the Apple or Linux operating system.

How many have access to computers running all three operating systems?

The solution, using the Inclusion-Exclusion principle for 3 sets wikipedia link, is 32. However, how can it be 32 when the number of students who have access to Linux is only 10?

$\endgroup$
2
  • 1
    $\begingroup$ The wording of the question is confusing. When they say "running A or B" do they mean "running A and B"? I'd interpret the former as "runs one of the two" and the latter as "runs both". $\endgroup$ Jan 20, 2015 at 17:48
  • 2
    $\begingroup$ The last three constraints must be interpreted as intersections and not as unions, since otherwise since $A\subseteq A\cup B$, we'd have an immediate contradiction with, say, the Apple and the Windows people. That being said, the answer, 32, would be impossible, as you noted. Either the problem was wrong or you copied it incorrectly. $\endgroup$ Jan 20, 2015 at 20:54

1 Answer 1

5
$\begingroup$

Let $A$, $B$, and $C$ be the set of pupils that have access to a PC running Windows, Apple, and Linux, respectively.

We know that \begin{align*} |A \cup B \cup C| &= 120 \\ |A| &= 80 \\ |B| &= 40 \\ |C| &= 10 \end{align*}

As @Tom van der Zanden pointed already pointed out in the comments, the wording of "... running the Apple or Windows operating system" is unclear. Thus I will cover all three interpretations of that wording.


Interpretation 1: "... running the Apple or Windows operating system" means the PC has installed both the Apple and Windows OS.

This means \begin{align*} |A \cap B| &= 30 \\ |A \cap C| &= 7 \\ |B \cap C| &= 5 \end{align*} Using inclusion-exclusion, we come to the result that \begin{align*} |A \cap B \cap C| &= |A \cup B \cup C| - |A| - |B| - |C| + |A \cap B| + |A \cap C| + |B \cap C|\\ &= 120 - 80 - 40 - 10 + 30 + 7 + 5 \\ &= 32 \end{align*} So your calculation is correct and there is a contraction. That means that either

  1. the inclusion-exclusion princliple does not hold in general, or
  2. the exercise description is inconsitent, i.e. some of the cardinalities are wrong.

Since the inclusion-exclusion principle is proven to hold for any arbitrary set of sets, the latter case must be true.


Interpretation 2: "... running the Apple or Windows operating system" means that the PC runs either the Apple or the Windows OS.

We can calculate the cardinalities of the intersections $A \cap B$, $A \cap C$, and $B \cap C$. However, we also run into a contradiction by using this interpretation:

\begin{align*} & |(A \cup C) \setminus (A \cap C)| = |A \cup C| - |A \cap C| = |A| + |C| - 2|A \cap C| \\ \implies & |A \cap C| = \frac{|(A \cup C) \setminus (A \cap C)| - |A| - |C|}{-2} = \frac{7 - 80 - 10}{-2} = 41.5 \end{align*} The above is a contradiction, since the cardinality of a finite set must be a natural number.


Interpretation 3: "... running the Apple or Windows operating system" is a regular logic or.

We have $|A| = 80 > 30 = |A \cup B|$. This is also a contradiction, since the cardinality of a set cannot be greater than the cardinality of its superset.


For either interpretation we show that there is a contradiction, therefore there must be a problem in the exercise description

$\endgroup$
2
  • $\begingroup$ Do you have any ideas on what is wrong specifically? Maybe if the question was "How many computers are there assuming one computer runs one operating system?" would that fix it? $\endgroup$ Jan 20, 2015 at 21:59
  • $\begingroup$ @MeliponeMoody I think that most likely one of the cardinalities is wrong. Changing the question does not help, since the contradictions exists regardless of the question. $\endgroup$
    – Gaste
    Jan 20, 2015 at 22:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.