Buttons

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.


The answer is 2625.

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.

2 solutions

Let n n be the number of buttons.

In the worst-case scenario, you have to press at most ( n 1 ) (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 ) ((n-2)\times2) 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 24 ( 25 i ) × i = i = 1 24 25 i i 2 = 25 × 24 × 25 2 24 × 25 × 49 6 = 2600 b u t t o n s \displaystyle \sum_{i=1}^{24} (25-i)\times i = \sum_{i=1}^{24} 25i - i^2 = 25\times \dfrac{24\times25}{2} - \dfrac{24\times25\times49}{6} = 2600 \enspace buttons

A s w e k n o w , i = 1 n i = n ( n + 1 ) 2 i = 1 n i 2 = n ( n + 1 ) ( 2 n + 1 ) 6 As \enspace we \enspace know, \\ \boxed{\displaystyle \sum_{i=1}^{n} i = \dfrac{n(n+1)}{2} \\\displaystyle \sum_{i=1}^{n} i^2 = \dfrac{n(n+1)(2n+1)}{6} }

After being sure of the sequence, we only have to press those 25 25 buttons(sequentially) and the door is open.

Total pressed buttons = 2600 + 25 = 2625 2600+25 = \boxed{2625}

And remember, this is for the worst cases.

Nice solution, @Fahim Shahriar Shakkhor

Anuj Shikarkhane - 6 years, 8 months ago

Why are you not counting the buttons that Are correct, i.e. n buttons to make sure of the first button of the sequence. This way I get 2925 as answer.

Kashish Goyal - 6 years, 8 months ago

Log in to reply

We are acting optimally here. For the first button,we can be sure of it by pressing the other ( n 1 ) (n-1) buttons. After that we do not need the press the correct one to check whether it is actually correct or not. This will give us unnecessary extra moves. That's why you are getting that answer.

Fahim Shahriar Shakkhor - 6 years, 8 months ago

Really nice solution..Thnks

Sanjay Das - 6 years, 8 months ago
Palash Som
Oct 6, 2014

first try to think through brain the condition when there are only 4 buttons left how many trials you need to do .

doing this you will get such series : for last button 1 time , for second last 2 time for third last 4 time and for the fourth last 7 time .

as you can see the series is going as : the trials done for button (n) are (n)+(the no. of trials done for any lock after the n lock -1 )

i.e. if you need to find the trials for the fourth last lock you need to do 4+no. of trials done for the next lock -1

i.e 4 + 4-1 = 7

so you can start the series from the last lock i.e 25th and apply the formula accordingly and add it up.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...