discrete puzzles
medium | discrete |
A group has 70 members. For any two members and there is a language that speaks but does not, and there is a language that speaks but does not. At least how many different languages are spoken by this group?
8 choose 4
This group has at least 8 different languages.
Let's go with hit and trial.
- Everyone knows the same language, that is a contradiction. Therefore it must be more than 1 language.
- So, knows one language and knows another language. But will know the same language as either or . We cannot extend this to 3 people.
- Might be true, but it is hard to confirm.
Let's try a different approach. Let's calculate the largest group possible, given the number of languages.
- If there are three languages (), we can construct the following table.
knows | |||
knows | |||
knows |
- If there are four languages (), we can construct the following table.
knows | ||||
knows | ||||
knows | ||||
knows |
This is decent, but I think we can do better by assigning more than one language to each person.
knows | knows | |||
knows | knows | |||
knows | knows | |||
knows | knows | |||
knows | ||||
knows | knows |
Now, there are people, because we assigned two languages. The number 6 is coming from choosing from , i.e.
Note that if we assign the same set of languages to two people (say: & ) then these two members will fail the desired criteria. Therefore we have to choose different sets of languages for each member, and one set cannot even be a subset of another set.
Also, note that the term takes the maximum value for .
Therefore, the maximum number of people for a given number of languages is , where is the number of languages.
Now, looking at the original question, , i.e. the maximum number of languages is , and the maximum number of languages that one person knows is .
Note that we can also