All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Talk to me (Posted on 2015-09-10) Difficulty: 3 of 5
Of the 1985 people attending an international meeting, no one speaks more than five languages, and in any subset of three attendees, at least two speak a common language.

Prove that some language is spoken by at least 200 of the attendees.

Source : Balkan M.O.

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Solution Comment 1 of 1
For any pair of members they either do or do not have a language in common. There are two cases to consider. 1: Everybody is able to talk to everybody else.  2: There is some pair of individuals who cannot talk to each other.

Case 1 is the easy case.  Since each person only knows at most five languages, then there is at least one language that ceil(1984/5)=397 people know, far greater than the 200 needed by the problem.

For case 2 let Alex and Bert be a pair with no common language.  Then all other of the 1983 people know a language that either Alex or Bert knows; this follows from the group of three rule.

They could know up to 10 languages between them.  Assume that any language has at most 199 speakers.  Then Alex and Bert can talk to 5*198=990 people each.  That totals 1980 people but that does not cover all 1983 people.  So the 199 assumption is false, there must be a language spoken by at least 200 people.

  Posted by Brian Smith on 2017-06-30 22:14:53
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information