You have just been hired for a new job. You are told that you will work with two other employees, Adam and Eve.
In your new office, there are three locked configuration boxes: one for electricity, one for plumbing, and one for gas.
Because your employer is cheap and unwilling to pay for repairs, you and your coworkers have to do routine maintenance on these boxes.
Originally, your employer bought three keys for each safe so each of you could access it. However, he has lost all of the keys and is only willing to pay for the absolute minimum number of keys to the boxes. Additionally, he doesn't trust you or your coworkers, so he will refuse to buy as many of any type of a key as there are of you.
What is the minimum number of keys that must be bought such that at any time, you or your coworkers are able to access all three configuration boxes, regardless of how many of you are at the office?
Note: Keys cannot be left out as your employer refuses to pay for minimal security and the janitors may throw them away by accident.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
While the problem may appear difficult and confusing on the surface, it is actually rather quite simple. Stripping away all of the needless detail, we see that we have three containers, each of which can only be opened with its respective key.
The most efficient solution will be creating a complete cycle of A, B, and C, as this on its own would only require 4 keys:
one key to access the cycle,
one key that leads to the next box,
another key in that box that leads to the next box, and
finally the last key in the final box which leads back to the first box, creating a complete cycle.
Extending this to 3 people is essentially the same: 3 keys to access the infinite cycle and the 3 keys that create the cycle within the boxes.
So, therefore, the most efficient solution to this problem is a total of 6 keys, where