logical deduction - Taming a Bomb Puzzle (Part 1 of 3)

Ampera Bridge, the famous landmark of Palembang City is in danger! A terrorist has sticked a bomb in the middle of Ampera Bridge. The bomb cannot be removed and it can explode anytime.

The bomb has N buttons, labeled from 1 to N (inclusive). It will explode right after pushing any of those buttons T times except one thing as follows.

Among the buttons, there is exactly one button, namely X. The bomb is designed so that when X has been pushed, it will sound “BEEP” but delayed at next K button pushings after it was pushed. In other word, if X was pushed at the i-th push, its “BEEP” can be heard at the (i+K)-th push. You don't know the value of K, but K is guaranteed to be between 0 to N-1. Of course, you also don't know the value of X.

Whenever the "BEEP" has been heard for N times (not necessarily consecutive), the bomb can be deactivated (tamed), of course, as long as the total number of button pushes does not exceed T times. When you hear the "BEEP", you may not know from which push it is made. But surely, if at the i-th push you hear the "BEEP", then your (i-K)-th push must be X.

To help you follow the definition and the example, here's a quick glossary:

  N: the number of buttons
  T: at this many button presses, the bomb goes off
  X: the button you need to identify
  K: an unknown but constant delay before the beep, measured in button presses. From 0 up to, but not including N
  i: the total press count, when a particular button was pressed

You, as a top bomb tamer, are to find a sequence of button pushes for deactivating the bomb.

---

Let's say you have the information of N = 4 and T = 20.

You have no clue at the beginning that this bomb has a value of X = 3 and K = 2.

 -----------------------
| No | You Push | Beep? |  
 -----------------------
|  1 |     3    |   -   |

|  2 |     2    |   -   | 
|  3 |     3    | BEEP! | 
|  4 |     4    |   -   | 
|  5 |     1    | BEEP! | 
|  6 |     4    |   -   | 
|  7 |     3    |   -   | 
|  8 |     1    |   -   | 
|  9 |     1    | BEEP! | 
| 10 |     1    |   -   | 
| 11 |     1    |   -   | 

| 12 |     3    |   -   |
| 13 |     3    |   -   | 
| 14 |     3    | BEEP! |

Some key points:

• You push button X = 3 as the first push, but its "BEEP" is heard after third (1+K = 1+2 = 3) push. Same as the third push's "BEEP" is heard at fifth push.


• The bomb hasn't been tamed at 12-th push. It will be tamed after 14-th push, when the N = 4-th "BEEP" is heard.


• If T is 13 or less, the bomb will explode in this case.

---

Let's say, you get the information about the value of K from somewhere (maybe the terrorist wrote it down on the back of the bomb).

The bomb has N = 50 buttons. What is the least possible value of T which still guarantees you to tame the bomb?

Bonus: Can you generalize T with any N?

Note that K can be 0 to 49 (N-1).

---

_{^{This puzzle is based on a competitive programming problem authored by me. It is used in Indonesia National Science Olympiad in Informatics 2016. The link is here (spoiler ahead for further parts!)}}

Answer

Building on Lolgast's answer, it's actually possible to do it in a few presses less! To be exact, it's

N + N-1 + N-(M+1) + N-1, or 4N - M - 3
With M being the largest number where (1+2+..+M <= N-1).

So at the very least, in order for the bomb to always be defusable, T must be

4N - M - 2

Explanation:

Let K = N - 1,

There are generally 4 'phases' to the presses:

1) The 'initial check' phase - just press every button in order, 1 to N. if there are no beeps by the time you press N, 1 is no longer a possible correct button. This costs N presses

2) The 'wait' phase - we know K = N-1, so at worst case (last button is the correct button) we'll know the correct button at the latest in N - 1 steps.

3) The 'press' phase - Press the correct button as many times as needed to reach N times. This costs N - [however many times we've pressed the correct button earlier]

4) The 'second wait' phase - wait for time to pass until there are N beeps. This is N-1 from the last press.

Lolgast's answer assumes we just repress every button from the start for the second phase, so at worst case (last button is correct), we would have pressed it twice, for the total of 4N - 4.

But see, if (2) is the correct button, then phase 2 will only last 1 step. Generalizing that, if (X) is the correct button, then phase 2 will last X-1 steps. On the other hand, phase 3 can be shorter depending on how many times you press (X) in phase 2 as well!

The key here is to make sure the free time we have in phase 2 is not wasted - for larger X, make sure we've pressed it as many times as possible to minimize the length of phase 3.

It's a bit difficult to explain the idea by words, so here's a visualization of the first 2 phases with 7 buttons (- will separate phase 1 and 2):

Instead of
1 2 3 4 5 6 7 - 2 3 4 5 6 7
Worst case, If 7 is the right button, it has been pressed 2 times by 2N-1 steps.
So total of Phase 2 + 3 would be N-1 + N-2 = 2N-3.

We can do
1 2 3 4 5 6 7 - 5 6 6 7 7 7
If 7 is the right button, it has been pressed 4 times by 2N-1 steps, or
If 6 is the right button, it has been pressed 3 times by 2N-2 steps, or
If 5 is the right button, it has been pressed 2 times by 2N-3 steps, and so on
This results in a total of Phase 2 + 3 to be N + N - 5 = 2N-5.

Using this strategy, the minimum number of presses required is:
N + N-1 + N-(M+1) + N-1, or 4N - M - 3

With M being the largest number where (1+2+..+M <= N-1).