Taming a Bomb Puzzle (Part 3 of 3)

Question

The part 1 can be found here: Taming a Bomb Puzzle (Part 1 of 3)
The part 2 can be found here: Taming a Bomb Puzzle (Part 2 of 3)

The Mechanics

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.

---

The Example

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.

---

The Puzzle

Now, the last part of this puzzle is the real challenge. Same as before, you know that the bomb has N = 50 buttons with a limit of T = 250 pushes. You don't know what are the values for X and K.

Unluckily, the terrorist has upgraded the bomb! There is an additional behavior: the bomb will explode as after a “BEEP” heard, the next “BEEP” is not heard in the next N button pushes.

So, on above example, the bomb will explode after the 13-th push because the "BEEP" is not heard since the 9-th push.

Let's find a way to tame the bomb!

Bonus: Can you generalize with any N given that T = 5N?

---

_{^{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.}}

Answer 1

First, press the following 99 buttons, stopping early at the second beep we hear if it occurs:
_{(x..y stands for the numbers between x and y in order)}

1..25 25..1 26..49 50 49..26

By then, if the number is in 1..25:

The first two presses will have returned (an ODD number of presses apart) and we can find out which button is the correct button, note that the last button press which could have caused the beep is at most 49 presses ago so the bomb won't explode as long as the next press is correct.

Otherwise, press these as the next 50 buttons:

50..26 50..26

And by then:

The second beep will have occurred regardless of what number button is applicable. The gap between the first two beeps again can tell us which button it is, note that the gap is of EVEN length if the number is from 26..49 (so we can tell it apart from 1..25) or ODD length if it is 50 (note that the second beep is at the earliest at the 100th press, the second time we click 50, so it can't be in 1..25)

Once we have figured the correct button:

Constantly press it until the bomb is tamed

I'm fairly certain a similar method will work for arbitrary N, although a bit of tweaking may be required for odd N.