Comby for robbers

For discussing Olympiad Level Combinatorics problems
User avatar
SANZEED
Posts:550
Joined:Wed Dec 28, 2011 6:45 pm
Location:Mymensingh, Bangladesh
Comby for robbers

Unread post by SANZEED » Tue May 22, 2012 1:22 am

Eleven robbers own a treasure box. What is the least number of locks they can put on the box so that there is a way to distribute the keys of the locks to the eleven robbers with no five of them can open all the locks, but every six of them can open all the locks?The robbers agree to make enough duplicate keys of the locks for this plan to work.
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$

User avatar
SANZEED
Posts:550
Joined:Wed Dec 28, 2011 6:45 pm
Location:Mymensingh, Bangladesh

Re: Comby for robbers

Unread post by SANZEED » Tue May 29, 2012 11:19 pm

My solution (after a tedious observation):
Let $n$ be the least number of locks required. If for every group of $5$ robbers, we put a new lock on the box and give a key to each of $6$ other robbers only, then the plan works. Thus,$n\leq \binom{11}{5}=462$. Conversely, in the case when there are $n$ locks, for every group $G$ of $5$ robbers, there exists a lock $L(G)$, which they do not have the key, but the other $6$ robbers all have keys to $L(G)$. Assume there exist $G ≠G'$ such that $L(G)=L(G')$ Then there is a robber in $G$ and not in $G'$. Since $G$ is one of the $6$ robbers not in $G$,he has a key to $L(G')$, which is $L(G)$,contradiction. So $G ≠ G'$ implies $L(G) ≠L(G')$. Then the number of locks is at
least as many groups of $5$ robbers. So $n\geq \binom{11}{5}=462$. Finally, $n=462$.
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$

User avatar
sowmitra
Posts:155
Joined:Tue Mar 20, 2012 12:55 am
Location:Mirpur, Dhaka, Bangladesh

Re: Comby for robbers

Unread post by sowmitra » Wed May 30, 2012 6:45 pm

Sanzeed, claps for the observation. :D :D
Let me add something to the problem- :?: What is the least number of keys that each robber must carry ? :geek:
"Rhythm is mathematics of the sub-conscious."
Some-Angle Related Problems;

User avatar
sowmitra
Posts:155
Joined:Tue Mar 20, 2012 12:55 am
Location:Mirpur, Dhaka, Bangladesh

Re: Comby for robbers

Unread post by sowmitra » Fri Jun 01, 2012 12:55 am

Hey, where's Sanzeed ? Please post the solution of the problem.
"Rhythm is mathematics of the sub-conscious."
Some-Angle Related Problems;

Post Reply