7
$\begingroup$

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

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!)

$\endgroup$
  • $\begingroup$ I had a little trouble keeping track of all the letters, so I thought a glossary would be helpful. Could you please check that it's ok? Thanks! $\endgroup$ – Bass Jan 10 '18 at 7:59
  • $\begingroup$ @Bass I made a small edit to yours - K can't be N. Still, I'd recommend OP to have a look at it to be sure. $\endgroup$ – Lolgast Jan 10 '18 at 8:17
  • $\begingroup$ @Bass + Lolgast, checked that, thanks for your edits! $\endgroup$ – athin Jan 10 '18 at 9:00
4
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Ah yes. This is indeed a good optimization. I was thinking of something like this when I was thinking about my answer, but didn't have enough time to flesh it out (was on the train). Not sure if I'd found it even if I had longer, though. $\endgroup$ – Lolgast Jan 10 '18 at 9:21
  • $\begingroup$ Yup, this is the right approach to optimize the 4N-4 solutions. Great job! :D $\endgroup$ – athin Jan 10 '18 at 12:40
2
$\begingroup$

I believe the worst case scenario would be

K=N-1

Which would require a T of

4N-4, i.e. 4(N-1)

The way you'd solve it:

Start by pressing all the buttons in some order. The exact order doesn't matter, only that you're unlucky enough to press X as the very last one. Without loss of generality I'll assume you press the buttons in normal ordering, i.e. 1, 2, 3...
Then, after N presses, you know X can't be 1 (since it would beep at N presses). Thus you start pressing in order again, for N-1 presses. At press 2N-1, you hear a beep, so you know X=N. You pressed X 2 times now, so you press another N-2 times. Then, you need N-1 more presses to hear all the beeps, resulting in N+N-1+N-2+N-1 = 4N-4 presses.

$\endgroup$
  • $\begingroup$ I'm not very sure if repeating pressing them in order again from the beginning is a good strategy. We don't know if K = N-1, and if it's actually less, your strategy actually will not be able to determine which button is making the sounds without more checks. $\endgroup$ – votbear Jan 10 '18 at 7:51
  • $\begingroup$ @Votbear "Let's say, you get the information about the value of K from somewhere" you do know it actually :P I was thinking on where you don't know it, with an idea that you should press it backwards, but not sure on how to prove that is optimal (if it even is) $\endgroup$ – Lolgast Jan 10 '18 at 7:54
  • $\begingroup$ Haha yeah, going backwards was what i've been thinking too. But it really is rather complicated to check if that method really is optimal, especially since finding the button is only the first part of the problem - the defusing part after that relies on the K we found $\endgroup$ – votbear Jan 10 '18 at 7:56
  • $\begingroup$ Wait, nevermind me - i missed the part where we actually do know the K. My bad =_= $\endgroup$ – votbear Jan 10 '18 at 7:58
  • $\begingroup$ @Bass Ah, it happens :P Especially with a longer text, it's easy to miss a bit (No offense meant to long posts - they're generally not at all bad, this is just an inherent property of them). $\endgroup$ – Lolgast Jan 10 '18 at 8:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.