You are trying to open a challenging lock. The lock has 25 buttons on it. To open it, you should press the buttons in a certain order. When you push some button, it either stays pressed into the lock (that means that you've guessed correctly and pushed the button that goes next in the sequence), or all pressed buttons return to the initial position. When all 25 buttons are pressed in the correct order, the lock opens.
Example:
Consider an example with 3 buttons. Let's say that the opening sequence is: [2,3,1]. If you first press buttons 1 or 3, the buttons unpress immediately. If you first press button 2, it stays pressed. If you press 1 after 2, all buttons unpress. If you press 3 after 2, buttons 3 and 2 stay pressed. As soon as you've got two pressed buttons, you only need to press button 1 to open the lock.
You are going to act in the optimal way. Calculate the number of times you have to press a button in order to open the lock in the worst-case scenario.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Let n be the number of buttons.
In the worst-case scenario, you have to press at most ( n − 1 ) buttons to make sure of the first button of the sequence.
Now to find the second button of the sequence, you have to press the first correct button(you have already known that) and then press another button. If it's wrong, then again press the first correct button and try for another. This time you have to press ( ( n − 2 ) × 2 ) buttons at most to make sure of the second button of the sequence.
Thus to be sure of the correct sequence of the buttons, we need to press
i = 1 ∑ 2 4 ( 2 5 − i ) × i = i = 1 ∑ 2 4 2 5 i − i 2 = 2 5 × 2 2 4 × 2 5 − 6 2 4 × 2 5 × 4 9 = 2 6 0 0 b u t t o n s
A s w e k n o w , i = 1 ∑ n i = 2 n ( n + 1 ) i = 1 ∑ n i 2 = 6 n ( n + 1 ) ( 2 n + 1 )
After being sure of the sequence, we only have to press those 2 5 buttons(sequentially) and the door is open.
Total pressed buttons = 2 6 0 0 + 2 5 = 2 6 2 5
And remember, this is for the worst cases.