5
$\begingroup$

2015 people are attending an international summit meeting on terrorism. Each of them speaks at most five languages, and in any group of three of them, at least two have a language in common. Prove that there is some language spoken by at least 203 of the participants.

(This puzzle was inspired by one with different wording and different choice of numbers from the 1985 Balkan Mathematical Olympiad.)

$\endgroup$

closed as off-topic by Mark N, f'', mmking, GentlePurpleRain, CodeNewbie Jul 10 '15 at 15:16

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is off-topic as it appears to be a mathematics problem, as opposed to a mathematical puzzle. For more info, see "Are math-textbook-style problems on topic?" on meta." – Mark N, f'', mmking, GentlePurpleRain, CodeNewbie
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Do you really mean "at most five languages"? @f" has a nice solution, but it seems to depend on everyone speaking five languages. $\endgroup$ – dzastergamer Jul 10 '15 at 13:41
  • $\begingroup$ @dzastergamer If anyone speaks fewer than 5 languages, you can give them dummy languages that nobody else speaks. $\endgroup$ – f'' Jul 10 '15 at 13:59
  • 1
    $\begingroup$ Could one of the close-voters please leave a comment about their decision? How is this more a maths problem and less a maths puzzle than many of Mike Earnest's posts? $\endgroup$ – Rand al'Thor Jul 10 '15 at 22:49
  • 1
    $\begingroup$ @randal'thor Having read the answer, I'm not sold on this one being enough of a puzzle rather than a math problem. The result isn't particularly surprising, nor is the solution unexpected, and while solving it takes skill, it's not really an aha but reasoning and casework. $\endgroup$ – xnor Jul 11 '15 at 0:22
  • 3
    $\begingroup$ @randal'thor To be fair, there are other posted questions that I could say similar things for, yet remain unclosed, so perhaps the community takes these things more liberally in general, and you got unlucky with this one. $\endgroup$ – xnor Jul 11 '15 at 6:56
13
$\begingroup$

Either every two participants have a language in common, or there is some pair that does not.

If every pair of participants shares a language, choose an arbitrary participant A. All 2014 other people must speak one of the at most 5 languages that A does. Whichever of these languages has the most speakers must have at least 403 not counting A.

Otherwise, there are some two participants (A and B) who have no common language. Then, any other participant must have a language in common with at least one of them. There are 2013 other participants, and only 10 languages that either A or B speaks. Therefore, at least one of these 10 languages must be spoken by at least 202 other participants. Because either A or B speaks this language, this language has at least 203 speakers.

$\endgroup$
  • 1
    $\begingroup$ I would change "only 10" to "x, which is at most 10". So at least one of these x is spoken by at least $y=\lceil\frac{2013}{x}\rceil$ other participants, so given that $x\leq 10$, y is at least 202. $\endgroup$ – h34 Jul 11 '15 at 21:21

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