Qm
BrainteasersJane StreetCitadel

The multilingual society

combinatoricsspernerantichainsextremal

A society has 70 members. For any two members X and Y, there is a language that X speaks and Y does not, and also a language that Y speaks and X does not.

What is the smallest number of languages that could be spoken in the society altogether?

Show a hint

Represent each member by the set of languages they speak. The condition says no member's set is contained in another's. How large can a family of subsets of an n-element set be if no subset contains another? Look for a family of subsets that all have the same size.

Your answer

Solving needs a free account

Answers, streaks and solutions unlock when you are signed in. Reading the question and the hint stays free.

Create a free accountSign in

Discussion

Sign in to join the discussion · reading is open to everyone

💡 Discussion rules

  1. No full solutions here. Hints and approaches only.
  2. Complexity, edge cases and intuition are the point.
  3. Interview experiences are welcome. Respect your NDAs.

Loading discussion…

Learn the concepts

The theory behind this question.

The Lost Boarding Pass ProblemThe Ballot Problem and the Reflection PrincipleBalls and Bins and the Birthday ProblemThe Banach Matchbox ProblemBinomial Coefficients and Pascal's Triangle

Related questions

The chicken nugget problemThe fastest possible checkmateCutting a gold chain to pay rentHandshakes at a partyHow many possible games of chess are there?
All questions →