Dishonest dungeon staff

Question

You are faced with the difficult task to set up a dungeon for adventurers. However you made a deal with the guild: any adventurer brave enough to beat the dungeon and reach the treasure room will be guaranteed to recieve some treasure, whatever he or she does. Of course, this goes against your master's rules, and so you will need to be clever about it. Under normal circumstances, the treasure room works as follows:

• There are N keys, and M rooms containing one treasure chest each. Every key opens at least one chest, and every chest has at least one key opening it, but you have no control over which keys open which chests.
• Each adventurer can pick a key, enter one chest room, and attempt to open each chest reachable from that room, with each key in his or her possession.

Your plan is to place the keys on keyrings (so that an adventurer that picks a key also gets any other keys on the same keyring), and dig tunnels connecting different chest rooms (so that an adventurer that enters a chest room can also reach any other rooms connected to it via tunnels), so that for every combination of keyring and chest room, there is at least one key on the keyring that can open a chest reachable from that room. Now, if you were unsupervised, you could put all N keys on the same keyring and connect all M rooms to each other, but you are under close surveillance, so you will need to minimize the risk of getting caught. In practice, this means that you will need to ensure the adventurer wins, with the fewest combinations of keys and chest. For example, combining key 1 and key 2 in one key ring and then combining this key ring with key 3 counts for 2 combinations, and the same goes for chests. You don't have all eternity to find a solution. Your procedure should be able to tell you the actions to take in a reasonable time as a function of N and M.

Is there a way you can ensure you fulfill your contract in the minimum number of combinations?

Answer 1

Two things to note, right off the bat:

First, there is a symmetry between keys and chests - every possible matching between $N$ keys and $M$ chests is equivalent to a matching between $M$ keys and $N$ chests, and so are all the potential arrangements of keyrings and tunnels. Thus, we will assume, without loss of generality, that there are at least as many keys as chests.

Second, we are asked to guarantee a treasure using as few combinations as possible. Every combination, whether of keys or of chests, turns two groups into one group, so an equivalent question to ask is that of the maximum number of groups into which the keys and chests can be profitably divided, which sounds relatively straightforward: connect all the rooms together, and leave the keys untouched, for $N+1$ groups and $M-1$ combinations in the worst case.

The reason this works is clear, but why can't we do better?

Suppose the chest rooms are divided into two sections. Then, every key group must contain either a key that opens a chest in both sections (which we'll call lucky), or two keys, one opening a chest in each section (we'll call these unlucky).
In general, the lucky keys can't be assumed to exist, and all-unlucky keys require $\lceil\frac{N}{2}+2\rceil$ groups, which is only greater than $N+1$ in the degenerate case when $N=1$ and such a strategy isn't even possible. By a similar argument, larger numbers of sections are even more stringent.
In the fortunate event that the chests can be sorted into multiple sections such that every key is lucky, or that the number of unlucky keys is smaller than the number of additional sections, then the worst-case strategy can be modified accordingly.