The famous Kohinoor diamond has been put on display in a certain museum. The museum authorities have installed an electronic lock which has N buttons, each with a different symbol. To open the lock one must select the correct combination of the symbols, irrespective of the order in which the buttons are pressed. When each button is pressed it lights up. If the correct combination is lit, the lock immediately opens. On the side of the lock is a reset button which will turn off all the lights.
The Jewel Thief visited the museum and noted down all the symbols. That night, he returned to steal the precious gem. Due to shortage of time, he must open the lock as fast as possible.
What is the minimum number of presses needed to guarantee that the lock will open (including both symbols and reset)? Assume that all the lights are off when he arrives.
For simplicity, let's assume that the symbols in the problem are just the numbers 1,2,3,... etc. and let P be the total number of presses required. One way of computing P for any given n is to evaluate the combination {1,2,..n} and then sort through the results to compile a list of the optimised series of presses. There is thus a clear connection with Pascal's Triangle which suggests a neater solution that avoids having to do the actual sorting.
Noting that the first row of the triangle is by convention labelled 0, say that n = 5. The 5th row of Pascal's Triangle contains the entries 1,5,10,10,5,1, totalling 32, corresponding to the number of combinations of {1,2,3,4,5}, that is one string of length 5, 5 of length 4, 10 of length 3, and so on. We can ignore the last 1 since that is the empty set.
Now, we know that one set of presses, {12345} will subsume all the combinations {1}, {1,2}, {1,2,3}, {1,2,3,4}, and {1,2,3,4,5}, using up the one combination of length 5, and one of every other length. Now we have 4 remaining strings of length 4, and do the same thing, subsuming the shorter combinations in the longer. Note that by symmetry these 2 actions absorb all the combinations of length 1. Finally we have 10-5=5 combinations of length 2 and 3 and match those similarly.
This gives a total of 1*5+4*4+5*3 presses of numbered buttons, for a total of 36, plus 10-1=9 resets (-1, because if the last combination was correct, the safe opens immediately) for a total P=45.
If n was even, say 6, the 6th row of Pascal's Triangle contains the entries 1,6,15,20,15,6,1. Note that the middle term is bigger than the others, so we will not be able to absorb all the combinations of length 3. Instead we will have 1 combination of length 6, 5 of length 5, 15-1-5=9 of length 4, and 21-15 = 6 singletons of length 3, for a total of 1*6+5*5+9*4+6*3=85 presses of numbered buttons, plus 21-1=20 resets, for a total P=105.
So for n buttons, let the corresponding entries of line n of Pascal's Triangle be {1,nC1,nC2,...,nCk} with nCk the largest term.
Then the number of presses of numbered buttons will be n+(nC1-1)*(n-1)+(nC2-nC1)*(n-2)...for k terms, plus (k-1) resets.
There's probably a more formal way of expressing this, but I believe the above transmits the idea clearly enough.
Edited on April 22, 2019, 11:08 am
|
|
Posted by broll
on 2019-04-22 05:41:44 |
Possible solution
