Taming a Bomb Puzzle (Part 2 of 3)

Question

The part 1 can be found here: Taming a Bomb Puzzle (Part 1 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, let's up for the challenge. 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.

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 (spoiler ahead for further parts!)}}

Answer 1

First,

press all the buttons in order 1..N and then again in reverse order N..1. You will hear beeps at times X+K and 2N+1-X+K, so once those have happened you can deduce X and K (say the first beep is at time t and the second at time u; then t+u=2N+1+2K, giving K, and u-t=2N+1-2X, giving X. (You haven't necessarily heard the second beep by the time you reach button 1 for the second time; in that case, start up from 1 again.)

As soon as

you hear the second beep, at time 2N+1-X+K, you know which button you have to keep pressing. You've pressed it at least twice by now, so you need another N-2 presses, for a total of 3N-1-X+K. And then you have to wait another K presses for all the beeps to occur (might as well keep mashing on button X for this), for a total of 3N-1-X+2K. Since X is at least 1 and K is at most N-1, this is no worse than 3N-1-1+2N-2=5N-4 button presses.