I recently heard a fun puzzle. Puzzle: How many languages are needed so that we can have that for any two people in a group of 70 each one knows a language that the other does not.
Solution: Basically we need to assign to each person a unique subset of languages. If there are K languages number of such such subsets will be maximum if each person knows K/2 languages. So, we will need the number of languages K to be such that
(KK/2)≥70
Another, variant of this puzzle is regarding bank locks. Puzzle: Suppose, you have n people working at a bank and you want that at least m should be present to be able to open a lock. How many locks do you need, and how many keys are needed for each lock.
Solution: For each subset of m−1 people there should be a lock that they cannot open so we need
(nm−1)
locks. Also, for any lock we cannot find m people that together cannot open it. So each lock should have n−(m−1) keys.
Solution: Basically we need to assign to each person a unique subset of languages. If there are K languages number of such such subsets will be maximum if each person knows K/2 languages. So, we will need the number of languages K to be such that
(KK/2)≥70
Another, variant of this puzzle is regarding bank locks. Puzzle: Suppose, you have n people working at a bank and you want that at least m should be present to be able to open a lock. How many locks do you need, and how many keys are needed for each lock.
Solution: For each subset of m−1 people there should be a lock that they cannot open so we need
(nm−1)
No comments:
Post a Comment