Matching locks to keys
You have distinct locks and distinct keys, each key opening exactly one lock. Testing a key in a lock tells you only whether it opens. Playing optimally, what is the worst-case number of key-in-lock trials needed to match every key to its lock?
Show hints (2)+
- For one key, if it fails on all but one remaining lock, the last is forced - so at most (locks ) trials.
- Sum as the pool shrinks.
Answer
Reveal answer →Final answer
10
Want the full step-by-step worked solution? It's part of Premium - along with a worked solution for every question in the bank.
Asked at: Jane Street, Optiver