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
\[ \left( \begin{matrix} K\\K/2 \end{matrix} \right) \ge 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
\[ \left( \begin{matrix} n\\m-1 \end{matrix} \right) \]
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
\[ \left( \begin{matrix} K\\K/2 \end{matrix} \right) \ge 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
\[ \left( \begin{matrix} n\\m-1 \end{matrix} \right) \]
No comments:
Post a Comment