How should I solve this kind of set theory problem?

Question

The exercise is the following:

In a group of $30$ people, 20 people speak French, 22 people speak German, and 25 people speak English. We assume everyone speaks at least one language. What could the number of people speaking all three languages be?

So using set theory notation, we could say: $$ |U| = 30 \quad |F| = 20 \quad |G| = 22 \quad |E| = 25 \\ |F\cap G\cap E|=?$$

All I can think of is start guessing; For example, I would say that let us see what happens if we say that $20$ people learn all three languages. This way, there must be $2$ more people distributed somehow in $G$ and $5$ more in $E$. No matter where I put these remaining people (drawing a Venn-diagram helped me), the total number of people can't be $30$ this way. So I could now start going downwards, what if $19$, $18$,$\dots$ people speak all three...

I don't think that this is a very elegant solution. How would you do it?

Answer 1

To solve for at most you take the smallest set which is the set of people how speak French which is $20$.

To solve for at least you add the three set together and subtract twice the amount of the set of all people $20+22+25-2*30 = 7$ , so to conclude.

note : if you have say $k$ set, then you add them together and subtract $k-1$ the cardinal of the united set and if the result is less or equal to $0$ then we say that at least $0$ people speak all language

... and if its a number bigger than zero then at least $x$ people speak all languages.

there is at least 7 people and at most 20 how speak all languages.

Answer 2

Consider a $8\times1$ vector $\mathbf x$, where the row number $i \in [0,7]$ encoded in base 2 as $i = \mathrm{FGE}_2$ are the indicators for the count $x_i$ of people who speak that set of languages. So, for example, in row $5 = 101_2$, we have the count of people $x_5$ who do speak French $(\mathrm F=1)$, don't speak German $(\mathrm G=0)$ and do speak English $(\mathrm E=1)$.

\begin{array}{ccc|c} F & G & E & X \\ \hline 0 & 0 & 0 & x_0\\ 0 & 0 & 1 & x_1 \\ 0 & 1 & 0 & x_2 \\ 0 & 1 & 1 & x_3 \\ 1 & 0 & 0 & x_4 \\ 1 & 0 & 1 & x_5 \\ 1 & 1 & 0 & x_6 \\ 1 & 1 & 1 & x_7 \\ \end{array}

Then the constraints may by written as a linear algebra equation, $\mathbf{A x} = \mathbf{b}$, where $\mathbf A$ is the matrix of left-hand side constraints and $\mathbf b$ is the vector of right-hand side constraints as follows

\begin{equation} \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{bmatrix} \begin{bmatrix} x_0 \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 20 \\ 22 \\ 25 \\ 30 \\ \end{bmatrix} \end{equation}

For example, the first row captures that there are $0$ people who speak none of the languages, the second row captures all the speakers of English set to $20$, etc., and the last row is the constraint that total must be $30$.

Finding solutions to $\mathbf{A x} = \mathbf{b}$ is a system of linear Diophantine equations problem with known methods. However, you can often find a particular solution by inspection if you row reduce the augmented matrix $[\mathbf{A|b}]$, resulting in the following:

\begin{equation} \left[\begin{array}{cccccccc|c} A_0 & A_1 & A_2 & A_3 & A_4 & A_5 & A_6 & A_7 & b \\ \hline 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & -1 & -1 & -17 \\ 0 & 0 & 1 & 0 & 0 & -1 & 0 & -1 & -15 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 2 & 37 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 25 \\ \end{array}\right] \end{equation}

By inspection on the 4th row of the row-reduced matrix, $2 x_7 \leq 37$, so $x_7$, which represents the speakers of all three languages, must be less than or equal to 18. If we set $x_7 = 18$, then we only have $37-2(18)=1$ left to assign among $x_3$, $x_5$, and $x_6$. We'll greedily set $x_5=x_6=0$ to allow easily solutions in other rows, making $x_3=1$. Now there is only one non-zero entry in each of the remaining rows besides that for $x_7$ and we can easily see that $x_1=1$, $x_2=3$ and $x_4 = 7$. This is only one of many possible solutions.

Now we happen to already have a maximal solution for $x_7$ by inspection, but the general problem of finding a maximum (or minimum) may be expressed as wanting to maximize $\mathbf{c^T x}$ where $\mathbf{c^T} = \begin{matrix}[0 & 0 & 0 & 0 & 0 & 0 & 0 & 1]\end{matrix}$. This along with $\mathbf{Ax} = \mathbf{b}$ and each $x_i \ge 0$ specifies a Integer Programming problem. These are hard problems (NP-hard) in general, but there are algorithms for solving. For example, using the lpSolve package of R

lp("max", c, A, "==", b, all.int=TRUE)
# Success: the objective function is 18 

also yields the answer of 18.

Answer 3

Denote the number of people speaking solely English by $E$, the number of people speaking French and German, but not English, by $E'$, and the number of people speaking all three languages by $x$. Looking at a Venn diagram we obtain the four equations $$\eqalign{ x+G'+F'\quad &+E=25\cr x+F'+E'\quad&+G=22\cr x+G'+E'\quad&+F=20\cr x+G'+F'+E'\quad&+E+F+G=30\ .\cr}$$ Solving for $x$ and the $\>'$-variables gives $$x=7+E+F+G\tag{1}$$ and $$G'=8-E-F,\quad F'=10-E-G,\quad E'=5-F-G\ .$$ It is therefore necessary that $$E+F\leq8,\quad E+G\leq10,\quad F+G\leq5\ .\tag{2}$$ Adding these inequalities gives the condition $2(E+F+G)\leq23$, or $E+F+G\leq11$. The values $E=6$, $F=2$, and $G=3$ satisfy $(2)$ and give $E+F+G=11$; furthermore any smaller nonnegative $E$, $F$, $G$ satisfy $(2)$ as well. Looking at $(1)$ we see that the possible values for $x$ are $7\leq x\leq18$.