# Dishonest dungeon staff

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?

• Welcome! A great first attempt at a puzzle but I think it needs some clarification. Is there one treasure room or many treasure rooms? Is there one adventurer or many adventurers. If there are many adventurers, is the contract such that every adventurer must get a treasure? You say that an adventurer should get "at least a treasure", but if an adventurer can only pick one key, then they only get a chance at one treasure, so is it possible that they can get more than one treasure? Commented Apr 12 at 11:09
• @LeppyR64 What i meant was, there is one treasure room with multiple chest rooms. Now let's say you can dig a tunnel under a chest room to another chest room, that would be combining them in a single chest room. Maybe I should've formulated it like that. There's many adventurers in the guild but only one can beat the dungeon ;) He should get a least a treasure yes. So if you do nothing he has a chance to get one chest, but if you combine keys and combine chest, he can get multiple treasures, although this doesn't affect your contract. I will edit to reflect those clarifications, thanks. Commented Apr 12 at 11:42
• Is the basic premise "how can you divide N keys and M chests into groups such that each key-group opens at least one chest in each chest-group?" Commented Apr 12 at 13:24
• Also, if a chest can be opened by multiple keys, can I trivially make all keys and chests the same, with no grouping required? Commented Apr 12 at 13:57
• I've used your responses to update the question - please double-check it to ensure that everything is correct. Commented Apr 12 at 23:09

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.

• Suppose you were presented with the instance of 4 keys and 4 chests: Chest 1 is opened by key 4, chest 2 by key 2 and key 3, chest 3 by key 1, key 2 and key 4, and chest 4 by the same keys as chest 3. The strategy you suggested works in 3 moves, while the optimal here is 2 moves. I think when you exclude "the fortunate event" you are swiping the difficulty of the problem under the rug. How would you detect that the chests can be sorted into multiple sections such that every key is lucky for example? Commented Apr 16 at 12:25