What is the maximum number of people who speak only 1 language?

Question

There are 1000 people in a conference. 500 speak English, 500 speak Spanish and 500 speak Hindi. Everyone at the conference speaks at least one of these languages.

What can the maximum number of people be who speak only 1 language?

Answer 1

I believe the answer is

750.

Intuitively, we would achieve the maximum number of people speaking only one language by assuming all of the remaining people speak all three languages, so we can set up a simple equation:

$x + 3 * (1000 - x) = 1500 \Rightarrow x = 750$

Answer 2

A visual explanation:

We want to maximize the area of the venn diagram that is non-intersecting, $a+b+c$. Suppose we had $N$ people who spoke exactly two languages, then by switching all $N$ people to speak three languages (i.e. center of diagram), we now have an excess +$N$ to place in the non-intersecting regions. Therefore we should have no bilingual persons, and solving we get 750.

Answer 3

You can solve the problem via integer linear programming, with a nonnegative decision variable $x_S$ for each of the seven nonempty subsets $S$ of the three languages and linear constraints to enforce the cardinalities. The problem is to maximize $x_{001}+x_{010}+x_{100}$ subject to \begin{align} x_{001} + x_{011} + x_{101} + x_{111} &= 500 \tag1\label1\\ x_{010} + x_{011} + x_{110} + x_{111} &= 500 \tag2\label2\\ x_{100} + x_{101} + x_{110} + x_{111} &= 500 \tag3\label3\\ x_{001} + x_{010} + x_{011} + x_{100} + x_{101} + x_{110} + x_{111} &= 1000 \tag4\label4 \end{align} The maximum objective value turns out to be

$750$, attained by $x_{001}=x_{010}=x_{100}=x_{111}=250$ and all other $x_S = 0$.

---

It turns out that the linear programming relaxation also has maximum value

$750$,

and the corresponding dual variables provide a short certificate of optimality as follows. Multiply the first three constraints \eqref{1} through \eqref{3} by $-1/2$, the last constraint \eqref{4} by $3/2$, the lower bounds $x_{011},x_{101}, x_{110}\ge 0$ by $-1/2$, and add everything up, yielding $$x_{001}+x_{010}+x_{100} \le \frac{1}{2}\left(-500 - 500 - 500 + 3000\right) = 750.$$

Answer 4

Another approach:

Let $A$ be the set of attendees and $N$ be the total number of attendees.

Let $L$ be the given set of languages, where each language is spoken by the same number, say $X$, of attendees.

Let $An : n>0$ be the set of attendees speaking exactly $n$ languages in given L.

We want to make number of attendees in $A1$ maximal. Let $M$ be that maximum number and let, for each language $l$ in $L$, $Ml$ be the number of attendees in $A1$ speaking language $l$.

For every attendee $a$ in every $An$ with $n>1$, one can, within limits imposed by constraints, compose an attendee set $A'$ for the polyglot conference with more attendees in $A'1$ by changing $a$ to an $a'$ speaking only one language.

For every attendee $a$ in every $An$ with $n<L$ one, one can, within limits imposed by constraints, compose an attendee set $A'$ for the polyglot conference, with more attendees in $A'L$, by changing $a$ to an $a'$ speak all languages.

Therefore, all $An$ $1<n<L$ can be made empty, and, since every given language is spoken by the same number $X$ of attendees, all $Ml$ for l in L, can be made equal, to, say $Y$, and, $M = Y * L$.

But to meet constrains, for example:

$AL$ can not be empty, in this puzzle, because, then: $X = Y$ but $X * L > N$ since here we have ($500 * 3 > 1000$).

In general we must find smallest $Z$ for which $M + Z <= N$ where we know $X = Y + Z$.

Now: $M + Z <= N$ rewrites $Y <= (N - X) / (L - 1)$ and $Z >= (X * L - N) / (L - 1)$.

In the particular OP example $N=1000$ $L=3$ $X=500$ gives smallest $Z=250$ and $Y=250$ and $M=750$.

Answer 5

Following method explicitly transforms any audience speaking different given languages into an audience with maximal amount of attendees speaking exactly one of the given languages.

Let there be $A$ attendees and $L$ languages given, and let every given language be spoken by same amount $S$ of attendees.

Consider the $A*L$ matrix $M$ representing an audience, where rows are indexed by attendees $a$, and columns are indexed by given languages $l$, and, where $M_{(a,l)}$ equals $1$ or $0$ depending on attendee $a$ speaking given language $l$ or not.

Note that one can explicitly adjust this audience by swapping a $0$ and a $1$ in same column. That is: one attendee instantly forgets, and another attendee instantly learns the given language corresponding to the column.

We will adjust the audience, attendee by attendee, to end up with an audience where every attendee has the property $P$ either to exactly speak one given language or to exactly speak all given languages.

Position attendees speaking all given languages at the bottom of the matrix. Then take the bottom row, corresponding to, say, attendee $a$ not having above property $P$. Since each given language is spoken by same amount $S$ of attendees, for each given language $l$ not spoken by $a$ there must be attendees (rows) $a'$ above $a$ speaking $l$.

Now swap each such $M_{(a,l)}$ with one such $M_{(a',l)}$, for example the first such $a'$ above $a$ to obtain one more attendee speaking all given languages.

Note that ordening the attendees this way, and selecting bottom row, is not required, it only helps to visualise the $1$s dropping down to swap with $0$s.

Continue this process until no more rows not containing all $1$s contain more than one $1$.

Note that $a'$ above could just perhaps only speak given language $l$ and no other. But that would in the end give attendees speaking no given language which is not a valid audience for this puzzle.

Since each given language is spoken by same amount of attendees, each given language spoken exactly once has same amount, say $X$, of attendees speaking it. Let $Z$ be remaining amount of attendees speaking all given languages. Then $A=Y+Z$ where $Y=L*X$ and $S=X+Z$.

Note that not every triplet $(A,L,S)$ ends up with such $Y$ and $Z$. One needs $X=(A-S)/(L-1)$ to be a natural number. Then $Y=L*X$ is the maximum OP is looking for.

In OP we have triple $(1000,3,500)$ and $X=250$ and maximum $Y=750$.