For the general department store, popularly known as "pedet", sent 10 suitcases, and in the envelope is attached 10 keys, being notified, that each key opens only one suitcase and that each suitcase can be matched with the right key.
Employee, who was picking up those suitcases, he sighed: - And what will I have a stall with the selection of keys?! I know the malice of inanimate objects! When I start choosing the key for the first suitcase, this is how it will turn out, that only the tenth key will match. Ten attempts for one suitcase, and for ten suitcases as many as one hundred attempts!
A friend, who has gained great skill in operating keys in her household, she said:
- Is not so bad! It is only with the first suitcase that you face ten attempts. With the second suitcase, you will only have nine keys to try and the number of keys will continue to decrease.
— No, let's count it, how many trials will have to be made:
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 55
so I am in danger of no more than 55 trials!
At this point, a colleague-rationalizer advises:
– First of all, don't pick your keys one by one and try to match them to one suitcase, but take any key and use it to open the suitcases one by one. This will be the case sooner, and the keys will not be mistaken for you. A po drugie, you face ten at the first key, only a maximum of nine tries, for if nine trials fail, then go ahead and tie the key to the tenth suitcase. You face eight tries with the second key, on the third - seven attempts, …, at ninth - one try, and for the tenth key, there is only one suitcase left, and you won't have to try!
— No, together it will be at best 45 trials! .
- Yes, but it will be so in the worst case - viz, when each key will only fit into the last suitcase. However, it is likely that the total number of trials needed will be half of the maximum, it means that they are enough 22 or 23 trials.