0
$\begingroup$

At the conference there are 30 languages spoken. We know that every triple of participants finds common language but there is no language that more than half of the participants speaks.

1) What is the smallest number of participants?

2) What is the largest number of participants?

3) What is the largest number of participants when every triple uses different language?

4) What is the largest number of participants if every participant uses different language in every triple he is part of.

The idea is to use double counting but I am not sure how.

When $p$ is the number of participants then ${p \choose 3} $ Is number of triples. And when $l_i$ is number of participants speaking language $i=1,..,30$ then $l_i \le {p \over 2}$

So 1) and 3) Are both 6 participants what about 2) and 4)-any ideas?

$\endgroup$
  • $\begingroup$ Does anyone have an idea? $\endgroup$ – KarmaL Jun 10 at 18:28
  • 2
    $\begingroup$ There must be at least $6$ participants, since three people with a common language are at most half the participants. I suggest you stat by seeing if you can work out a way to do part 1) with $6$ participants. (I would guess this is possible, but I haven't tried.) I find it usually helps my thinking to have a concrete case to work on. $\endgroup$ – saulspatz Jun 10 at 18:47
  • 1
    $\begingroup$ Similarly the answer to $3)$ would also be $6$ as with $7$ participants, you'd need at least ${{7}\choose{3}} = 35$ number of languages and this number would just keep rising as the number of participants grew $\endgroup$ – Sauhard Sharma Jun 10 at 18:51
  • $\begingroup$ And also 2) a 4) are the same, aren't they? Because criterium in 4 is the case of the most participants in general. Does anyone know how to country thé largest number? $\endgroup$ – KarmaL Jun 11 at 5:05
2
$\begingroup$

There must be at least $6$ participants, since the common language spoken by the members of a triple is spoken by no more than half the participants. If there are exactly $6$ participants, then there are ${6\choose3}=20$ triples, and we can assign a different language to each triple. That is, the members of $\{1,2,3\}$ speak language $1$, and no other participants do; the members of $\{1,2,4\}$ and no other participants speak language $2$, and so on. We may assume that the other $10$ languages are spoken only by participant $1$. This shows that the answer to part $1)$ is $6$.

For part 2) notice that we can add another $6$ participants, if number $7$ speaks exactly the same languages as number $1$, number $8$ exactly the same languages as number $2$ and so on. In fact, we can add as many participants as we like provided that participants $j$ and $k$ speak exactly the same languages precisely when $j\equiv k\pmod{6}$. So for part $2),$ there is no maximum.

This also shows, in response to the OP's comment that parts $2)$ and $4)$ are not the same. For part $4)$, an individual cannot be a member of more than $30$ triples, since he must use a different language in each triple, so if there are $p$ participants, we must have ${p-1\choose2}\leq30\implies p\leq9$. Note that in the solution to part $1)$ given above with $6$ participants, each person uses a different language in every triple. You have to determine whether there are solutions with $7$, $8$ or $9$ participants.

Part $3)$ is trivial.

$\endgroup$
  • $\begingroup$ typo? in part (4) ${8 \choose 2} = 28 \le 30$ so $p \le 9$ instead of $p < 9$? $\endgroup$ – antkam Jun 11 at 18:54
  • $\begingroup$ @antkam Some kind of mistake anyway; thanks, I'll fix it $\endgroup$ – saulspatz Jun 11 at 19:18
0
$\begingroup$

Answer for Part 4) / continuation of the answer by @saulspatz

Suppose there are $p$ participants. Then the following must hold:

  • Each participant belongs to ${p-1 \choose 2}$ triplets and must speak (at least) that many languages. So the total number of (language, speaker) pairs $\ge p {p-1 \choose 2}$.

  • Each language can be spoken by at most $\lfloor p/2 \rfloor$ speakers, so the total number of (language, speaker) pairs $\le 30 \lfloor p/2 \rfloor$.

  • Combining: $p {p-1 \choose 2} \le 30 \lfloor p/2 \rfloor$, i.e. $p(p-1)(p-2) \le 60 \lfloor p/2 \rfloor$.

It is easy to verify that $p \ge 7$ fails the above requirement. Thus the maximum is still $6$, which @saulspatz has achieved.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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