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.
In an attempt to get a feel for the sequence, with an eye either to look up a sequence on the OEIS, or develop a recursive method devolving into lower numbers, I worked out what I think are the answers for 2, 3 or 4 symbols:
ABr
B
4
ABCr
BAr
CAr
CB 12
ABCDr 4
BCAr 6
CAr 8
DABr 11
DBCr 13
DCA 15
23
The cumulative counts above represent the number of combinations accounted for thus far in the set, and the numbers to the right are the counts of presses needed.
Together with 1 for 1 symbol, the sequence is 1, 4, 12, 23 presses. Of course the pattern is affected by the lack of need for a final r (reset); if that were included the sequence would be 2, 5, 13, 24.
Working out a recursive method must take into consideration that some lower sets have been included already, and how most efficiently to avoid as many repeated subsets as possible.
Lest anyone try a situation where pressing a symbol toggles that symbol's light instead of staying on if it's already on, the answer to that would be 2^N-1, as the burglar could enter the gray code for every integer from 1 to 2^N-1 by pressing only one button to get from one to the next.
Edited on April 17, 2019, 11:17 am
|
|
Posted by Charlie
on 2019-04-17 11:03:51 |
some thoughts
