There are 6 locked suitcases and 6 keys to them. However, it is unknown which key fits which suitcase. What is the minimum number of attempts needed to definitely open all the suitcases? And how many attempts would be needed if there were not 6, but 10 suitcases and keys?

#
Try to determine which of the 6 suitcases the first key fits in five attempts.

## Solution

Standard incorrect solution: "Each of the six suitcases is tried with each of the six keys, totaling $66=36$ attempts." However, it is possible to find the correspondence between the keys and the suitcases with fewer attempts. Take the first key and try to open the suitcases one by one. If one of the suitcases opens, set aside this suitcase with this key. If none of the first five suitcases open, then this key must correspond to the sixth suitcase. What happened? We used no more than five attempts; we have five keys and five suitcases left. Again, take one key and try to open all the remaining suitcases in sequence. To determine which suitcase this key corresponds to, it takes four attempts. Take the next key and so on. In total, it will take $5+4+3+2+1=15$ attempts. If there were 10 suitcases, the number of attempts would be $9+8+\ldots+2+1=45$.

## Answer

Problem