Alice is storing a document in a vault safe. 7 people have access to this vault. They want to assign keys to the safe and have multiple locks on it. They want that any 4 of them can open the safe if they got together, but no 3 of them can open the safe by themselves. For example, suppose we have locks labeled A, B, C, D, E on the safe, and you have keys for A, B, C and Bob has keys B, D, E, then you two can just open it together, but neither of you could open it yourself. That would cause one person to have too much power.

Alice has found a solution that uses 35 locks between these 7 people and is wondering if it could be done better. Find out how Alice did it with 35 locks (each lock can have duplicate keys; locks are expensive but making copies of keys are cheap). Hint: your answer should be fairly symmetric. Can you do better? Can you prove you cant do better?