A Hundred Locks and a Hundred Keys

What’s going on

You have 100 locks that all look the same and a heap of 100 keys. Each key opens exactly one lock. A try means putting one key into one lock and seeing whether it turns. You want to know which key opens which lock. How many tries do you need, if you are as unlucky as possible?

An upper bound: key by key

Trying every key in every lock would take 100 × 100 = 10,000 tries, but that is wasteful. Take key 1 and try it in the locks one after another. After 99 failures you do not need the last try: it must be the 100th lock. Put that pair aside. Key 2 now needs at most 98 tries, key 3 at most 97, and so on, until the last key needs none at all:

99 + 98 + 97 + … + 2 + 1 + 0 = 4,950.

(Write the sum twice, once backwards: the 100 columns each add up to 99, so twice the sum is 9,900.) For n locks the same idea gives n(n − 1)/2 tries.

Can a smarter method do better?

Perhaps a clever pattern of failures could suddenly reveal several pairs at once? To prove that no method at all can guarantee fewer than 4,950 tries, we play against an opponent with the worst possible luck. The opponent has not fixed the locks in advance. After each try it answers “no” whenever some arrangement of the keys still fits all its earlier answers. That is fair: the locks look identical, so every such arrangement could really be the one in front of you, and a method that “guarantees” success must cope with all of them.

In the scene above you play exactly this opponent with 6 locks. Click cells to try keys. A − marks a failure; small dots and faint + signs already follow from your tries. Then press Key by key on a new game, and press Show why when you finish.

Why the bound cannot be beaten

Against this opponent, every useful try is answered “no”. The only “yes” answers come from tries whose result you could already deduce, and those are wasted. So at the end you hold a table of − signs, and from those alone the whole matching follows.

Now rearrange the rows so that each key sits in the row of its own lock: the matching pairs, the + signs, run along the diagonal. Take any two keys, say key A with lock A and key B with lock B. Look at the two cells “key A in lock B” and “key B in lock A”. They are mirror images across the diagonal. If both were empty, keys A and B could swap locks, and every answer you received would still be true. Then you would not know the matching. So every mirror pair must contain at least one −.

Fold the table along the diagonal and you see it at once. A table of 100 × 100 has 100 × 99 ÷ 2 = 4,950 mirror pairs, so you received at least 4,950 “no” answers. Key by key is the best possible method.

Try it yourself

1. Three locks

With 3 locks and 3 keys, key by key needs 2 + 1 = 3 tries. Show without the fold that 2 tries can never be enough.

Answer

There are 6 ways to put 3 keys in 3 locks. Two tries give at most 2 × 2 = 4 different patterns of answers, and 4 patterns cannot tell 6 arrangements apart. This counting trick is quick but weak: for 100 locks it only proves that about 525 tries are needed, far below the true 4,950.

2. Random locks

The locks are now set up by chance, not by a tricky opponent. You try key 1 in locks 1, 2, 3, … in turn. With 100 locks, how many tries does key 1 take on average?

Answer

About 50. If key 1 fits lock j for j from 1 to 99, it takes j tries; if it fits lock 100, you know after 99 tries. Each lock is equally likely, so the average is (1 + 2 + … + 99 + 99) ÷ 100 = (4,950 + 99) ÷ 100 = 50.49. Luck roughly halves the work, but only a worst-case count is a guarantee.

3. Halfway there

Going key by key with 100 locks and the worst luck, you have matched 50 keys. What fraction of the 4,950 tries have you used?

Answer

About three quarters. The first 50 keys cost 99 + 98 + … + 50 = 3,725 tries. The other 50 keys cost only 49 + … + 0 = 1,225. The early keys are expensive because there are so many locks left to try.

Go deeper

• The argument with a worst-luck opponent is called an adversary argument. Computer scientists use it to prove lower bounds, for example that finding the largest of n numbers needs n − 1 comparisons.
• If a try also told you whether the key is too big or too small, as with nuts and bolts of slightly different sizes, about n × log n tries would be enough. With only “fits” or “doesn’t fit”, you are stuck with n(n − 1)/2.