30
$\begingroup$

Summary:

It is your first day in prison serving a literal life-sentence under the supervision of the warden. You are to be kept in solitary confinement with no additional information for the duration of your stay.

However, there is one chance of escape. The warden will set you free if you guess the exact number of days (including the day you guess) it has been since he first became warden. The catch is that if you guess the wrong number of days, you will be executed immediately.


Rules:

  1. You may guess the exact number of days the warden has been in his position at any time and accept the consequences (this does not count as a yes/no question).
  2. You may ask n+1 total yes/no questions as long as it has been 2^n days since the warden's first day. For example:
    1. If it is his first day on the job, you get 1 Y/N question
    2. If it is his 2nd-3rd day on the job, you get 2 Y/N question
    3. If it is his 4th-7th day on the job, you get 3 Y/N questions
    4. If it is his 8th-15th day on the job, you get 4 Y/N questions
    5. etc.
  3. If you ask the warden too many yes/no questions, you will be executed. For example:
    1. If you ask your 2nd Y/N question and he had his job less than 2 days, you are executed
    2. If you ask your 3rd Y/N question and he had his job less than 4 days, you are executed
    3. If you ask your 4th Y/N question and he had his job less than 8 days, you are executed
    4. If you ask your 5th Y/N question and he had his job less than 16 days, you are executed
    5. etc.

That's it.


Question:

What strategy would you use and why?

$\endgroup$
  • 4
    $\begingroup$ You mention "guess the number of days the warden has been in his position at any time", and also that you can ask the questions as long as it has been "2^n days since". Does this mean you can ask a question on different days, and if so, do you get additional questions over time? e.g. If the warden hits an anniversary date, do you suddenly get an additional question? $\endgroup$ – APrough Jan 15 '18 at 21:41
  • 2
    $\begingroup$ Is asking "Have you been warden for N days?" a valid yes/no question, or would he interpret that as your guess and execute you if you're wrong? $\endgroup$ – DqwertyC Jan 15 '18 at 21:51
  • $\begingroup$ @APrough Any question is fine as long as it does not violate any of the rules at the time it was asked. $\endgroup$ – Briguy37 Jan 15 '18 at 23:04
  • $\begingroup$ @DqwertyC If you ask that and are wrong it will count against one of your yes/no questions. If that was the "one too many" you will be executed. $\endgroup$ – Briguy37 Jan 15 '18 at 23:04
  • 1
    $\begingroup$ Has a correct answer been given? If so, please don't forget to $\color{green}{\checkmark \small\text{Accept}}$ it. If not, some responses to the answerers to help steer them in the right direction would be helpful. $\endgroup$ – Rubio Jan 30 '18 at 9:13
21
$\begingroup$

"Can I ask another question?"
- No: "You've been here since 1 day!"
- Yes: I know he's been here for at least 2 days, so I got another question...

"Can I ask another question?"
- No: Then he's been here since 2 or 3 days, easy to sort out with one question. To ask a third question, I need him to be there since at least 4 days, so let's wait 2 days and ask if the answer is 4 (if not, it's 5 days!)
- Yes: Then he's been here since at least 4 days, so I got another question...

"Can I ask another question?"
- No: Then he's been here since 4 to 7 days, easy to sort out with two questions. To ask a fourth and fifth question, I need him to be there since at least 16 days, so let's wait 12 days and use my 2 brand new questions to narrow it down to the answer !
- Yes: Then he's been here since at least 8 days, so I got another question...

"Can I ask another question?"

Etc...
Long story short : always wait long enough to get enough questions to make a basic dichotomy search. For example, if you know the warden has been there for16 to 19 days you need 2 questions : have you been there for 17 days or less ? Yes: 16 or 17 is the answer, one question to get it right. No: 18 or 19 is the answer, one question to get it right.

$\endgroup$
  • 2
    $\begingroup$ a way of reducing that could be to ask not for 1 more, but for an arbitrary number, larger than 1. In which case, you have to wait less if the warden says yes, but wait 1 extra day to ask as new question. The optimal case becomes less good, but the worst case is better. $\endgroup$ – njzk2 Jan 16 '18 at 5:54
  • 15
    $\begingroup$ A better question will be "Can I ask another question without being executed?" $\endgroup$ – prog_SAHIL Jan 16 '18 at 10:46
9
$\begingroup$

My Strategy:

Start by repeatedly asking "May I ask another question today, after this one, without being executed?" until he says No.
If he says Yes N times, then he has been there between $2^N$ (inclusive) and $2^{N+1}$ (exclusive) days already. If N is 0, then you know that this is his first day, and you can guess that and be free. Otherwise, there are $2^N$ possible days it could have been, and we'll need more questions to figure out when things started.

Then, you wait:

By using a binary search, you'll need N more questions to narrow it down to the exact date, which means waiting $2^N + 2^{N+1} + 2^{N+2} + ... + 2^{2N} = 2^{2N+1} - 2^{N}$ days. This will guarantee that you have N more questions available. Then, ask questions along the line of "When I first got here was it (at least/at most) your Mth day here?", each time choosing M and the direction such that your range of possible values is cut in half. Eventually, you'll narrow it down to the exact date, and be free.

With this strategy:

The number of days imprisoned is determined solely by how many times the guard said yes on the first day, which may mean waiting longer than some cases in other strategies, but also means waiting shorter than other cases.

$\endgroup$
5
$\begingroup$

Of course, the true answer to what the best strategy is depends on the probability that the warden served for a certain amount of days. I think the other answers given so far are particularly poor; I'll explain why later. A class of strategies is of the form

define a sequence $A = (x_1, x_2, x_3, ...)$ of days, and for your $n$th question ask "when this started had you been warden for $x_n$ days?" until you get a no, then bisect the range $[x_{n-1}, x_{n})$ until you get the final answer.

Assuming $x_n$ are powers of two for simplicity, the time this takes is

If the warden served less than $x_n$ days, this takes $x_n \times 2^{n-1}$ days.

Now, assuming we are going to pick one of these strategies, which one do we select here?

The popular choice (as the other 4 answers so far have picked) is to select $A = (1,2,4,8,...)$, but this is not a good choice, as if the initial answer is $D$, you might need $D^2$ days to get out. For some datapoints: if the warden has served for a mere 16 days then you get out in 256 days (about 8 months), and if the warden has served for those 256 days, you're already pretty much guaranteed to rot in jail for life (180 years).

As an example of a better option, you might choose $A = (1024, 4096, ...)$, in which case you get out in 3 years if he has been there for less than 3 years and in 44 years if he has been there for less than 22 years. This is already better or equal to the other choice if he has been there for at least 32 days, which is a really tiny amount.

It gets even more complicated if you expect the warden to be more likely to be at one end of the range than the other, in which case bisecting will not be the optimal choice. But I won't get into that can of worms...

$\endgroup$
  • $\begingroup$ if warden has been working 80 years, that is 29200 days. What if you start with an array with {2^0, 2^1, 2^2 ,,,,, 2^15} and start in the middle with 2^8. $\endgroup$ – Juan Carlos Oropeza Jan 16 '18 at 19:15
  • $\begingroup$ @JuanCarlosOropeza If the warden has been working for X years, then you need at least X years to escape without guessing; I opted to ignore the 80 year case because escaping in 80 years is long enough of a timeframe that it wouldn't be worth going for it. $\endgroup$ – ffao Jan 16 '18 at 19:48
  • $\begingroup$ you might choose A = (1024, 4096, ...) with only two values isnt clear what array you choose to solve this $\endgroup$ – Juan Carlos Oropeza Jan 17 '18 at 13:35
3
$\begingroup$

If we're bit sneaky, we can gain our freedom the first day.

We can continually ask the warden a question in this form:

Given $n$ is the number of days you've been on the job, if I select an integer randomly from the range $[\lceil\frac{n-x}{n}\rceil, 1]$ and add it to $\lfloor\frac{n}{2^q}\rfloor$, will the sum be even?

Values for $q$ start at $0$ and increase by $1$ each question. For the first question, $x$ is $1$. For subsequent questions, if the answer to the previous question was "Yes", then $x = x' + 2^q$; if "No", then $x = x' + 2^q - 2^{q'}$.

We continue asking the warden questions of this form until he says "I don't know." Then we tell him that he has been here $x$ days, where the value of $x$ is the one used in the question that he couldn't answer.

The key to this is that $\lceil\frac{n-x}{n}\rceil=1$ when $1 \le x \lt n$ ensuring the random integer is $1$ in these cases. Once $x \ge n$, the random number is no longer restricted to $1$, so the question about the sum being even cannot be answered. But while the answers are "Yes" and "No", this indicates whether $2^q$ is or isn't in the the powers-of-two that sum to $n$. By summing the known powers-of-two in $n$ and adding the next-lowest possible power-of-two, we ensure that $x \le n$ for every question.

Example

The prisoner (P) informs the warden (W) that for purposes of his questions, $n$ is the number of days the warden has been on the job. If the warden has been on the job 73 days, the following would occur:

P: Sets initial value $x=1$ and asks "Is the sum of $\lfloor\frac{n}{1}\rfloor$ and a random integer in $[\lceil\frac{n-1}{n}\rceil, 1]$ even?"

W: Evaluates summing $73$ with a random integer in $[1, 1]$ and replies: "Yes."

P: Sets $x=1+2=3$ and asks "Is the sum of $\lfloor\frac{n}{2}\rfloor$ and a random integer in $[\lceil\frac{n-3}{n}\rceil, 1]$ even?"

W: Evaluates summing $36$ with a random integer in $[1, 1]$ and replies: "No."

P: Sets $x=3+4-2=5$ and asks "Is the sum of $\lfloor\frac{n}{4}\rfloor$ and a random integer in $[\lceil\frac{n-5}{n}\rceil, 1]$ even?"

W: Evaluates summing $18$ with a random integer in $[1, 1]$ and replies: "No."

P: Sets $x=5+8-4=9$ and asks "Is the sum of $\lfloor\frac{n}{8}\rfloor$ and a random integer in $[\lceil\frac{n-9}{n}\rceil, 1]$ even?"

W: Evaluates summing $9$ with a random integer in $[1, 1]$ and replies: "Yes."

P: Sets $x=9+16=25$ and asks "Is the sum of $\lfloor\frac{n}{16}\rfloor$ and a random integer in $[\lceil\frac{n-25}{n}\rceil, 1]$ even?"

W: Evaluates summing $4$ with a random integer in $[1, 1]$ and replies: "No."

P: Sets $x=25+32-16=41$ and asks "Is the sum of $\lfloor\frac{n}{32}\rfloor$ and a random integer in $[\lceil\frac{n-41}{n}\rceil, 1]$ even?"

W: Evaluates summing $2$ with a random integer in $[1, 1]$ and replies: "No."

P: Sets $x=41+64-32=73$ and asks "Is the sum of $\lfloor\frac{n}{64}\rfloor$ and a random integer in $[\lceil\frac{n-73}{n}\rceil, 1]$ even?"

W: Evaluates summing $1$ with a random integer in $[0, 1]$ and replies: "I don't know."

P: States: "You've been on the job $73$ days."


By looking at the binary values for $x$ as the questioning proceeds, we can see that the final answer is built up from the least- to most-significant bit. The bit value is $1$ for "Yes", $0$ for "No", and $1$ for the "Don't know" that also indicates the final value has been determined.

| x (dec) | x (bin) | Response | |---------+---------+------------| | 1 | 1 | Yes | | 3 | 11 | No | | 5 | 101 | No | | 9 | 1001 | Yes | | 25 | 11001 | No | | 41 | 101001 | No | | 73 | 1001001 | Don't know |

This method always uses $1+\lfloor log_2(n) \rfloor$ questions, which coincidentally (or not) is the maximum allowed per day.

$\endgroup$
  • $\begingroup$ Maybe you could add an example with some n and show how the calculation works. Also not sure what you mean you can gain freedom the first day when you also say need ask multiple questions? $\endgroup$ – Juan Carlos Oropeza Jan 17 '18 at 13:44
  • $\begingroup$ @JuanCarlosOropeza D Krueger is using an unanswerable question to force the warden to answer "I don't know" under certain conditions, then using the now 3-value questions (Yes/No/Don't know) to get all the information he needs on the first day. He still uses all of his questions, but he's guaranteed not to go over with this method. $\endgroup$ – Brilliand Jan 17 '18 at 23:15
  • $\begingroup$ @Brilliand I imagine is something like that, just isnt easy too see $\endgroup$ – Juan Carlos Oropeza Jan 18 '18 at 1:49
  • $\begingroup$ @JuanCarlosOropeza I'll add an example that will hopefully make it clearer. $\endgroup$ – D Krueger Jan 18 '18 at 2:29
1
$\begingroup$

There is a way to guarantee to find the exact day with the logic below:

Firstly,

Ask "Have you been here less than $2^x$ days?" starting from $2^1$ to $2^x$ until you get Yes answer, which will be safe. After you get Yes answer you will know that you are in the range of the days in between $2^{x-1}$ to $2^{x}-1$.

Secondly,

After getting the range of days, we need to wait $2^{x-1}$ days to guarantee to get another question in case the day could be $2^{x-1}$.

Thirdly,

Then ask the same question for the $2^{x-1}+2^x-1$. If the answer is yes, go to second part of the methodology above, if no, you have found the day!

For example:

First question with the assumption the day is 6th day and assuming we don't know the exact day:

You - Have you been here less than 2 days?
Warden - No
You - Have you been here less than 4 days?
Warden - No
You - Have you been here less than 8 days?
Warden - Yes

So we know that at this point the day could be in between 4 to 7 days but we don't know exactly which day and we don't have any question left to ask, to ask another question, we need to wait another $4$ days to guarantee that we have another question option and ask:

You - Have you been here less than 11 days? 
(which is practically asking him that it has been 7 days or not?)
Warden - Yes

This is bad, because it could be inbetween 8 days to 10 days but we have one less day. and we need to wait another $8$ days to guarantee to get another question. So:

You - Have you been here less than 18 days? 
(which is practically asking him that it has been 6 days or not for the beginning?)
Warden - No

That means it has been 18 days and you can get out!

$\endgroup$
1
$\begingroup$

Assuming you can save your questions, and don't mind spending some time in jail, here is something that can guarantee your release (eventually)

On specific days, ask the following question...

Have you been warden for less than or equal to X days

In this situation, X is equal to

On every 2^n day you have been there, X = 2^n + (prev num Y/N questions * 1)

So, as follows...

Day 1, X = 1; Day 3, X = 4; Day 7, X = 9, etc.

With this logic, when the warden finally says Yes,

He has actually been there that number of days! So you can guess immediately.

The only downside is that the amount of time you actually spend in jail will be

equal to the number of days that you are currently guessing (e.g. 2^n + number previous questions).

$\endgroup$
  • $\begingroup$ This sounds promising, but on further inspection, I think it's inaccurate. For example, if you ask on "Day 7" whether he's been warden for "9 days", then you get out if he was originally warden for 2 days, which is much less than 7. $\endgroup$ – Brilliand Jan 16 '18 at 23:22
  • $\begingroup$ @Brilliand - But on Day 7, he has been there 9 days (the original 2, plus the 7 you have been there). $\endgroup$ – APrough Jan 17 '18 at 13:13
  • 1
    $\begingroup$ Yeah, but you say "equal to the number of days that the warden has already served". Staying in for 7 days when the warden had originally served 2 days is a lot worse than equal. $\endgroup$ – Brilliand Jan 17 '18 at 23:06
  • $\begingroup$ You are correct. I think the edit I added in shows that it will be much longer. $\endgroup$ – APrough Jan 25 '18 at 20:25
0
$\begingroup$

Were I in that situation, I would place considerable importance on getting out quickly. I certainly don't want to wait the length of the warden's career to date, unless it turns out to be quite short. So, I'll accept some risk of dying in exchange for keeping the waits low.

The first step is to figure out the order of magnitude of the warden's day count. Whatever order of magnitude I find, I have that number of questions plus one to work with, and need that many questions for a binary search to find the exact number.

So, I have 1 question with which to find the order of magnitude, so I get one guess as to what the order of magnitude is.

  • If my guess is correct, then I get out on the first day.
  • If it's too low, then I die.
  • If it's too high, then I may have to wait at most the shortest period in the range my guess represents to guarantee survival.

So, there's an estimation step there, and I could probably make that guess more easily from in the prison than from in front of my computer. In case the warden doesn't allow me any sort of hint (not even the sound of his voice), I can fall back on the assumption that no one would hold such a job for over 40 years... so the 20-40 year range will be my opening guess.

To minimize the time spent in prison, I'll be as impatient as I can safely be, and ask each question as soon as I'm certain I have it.

Converted to a procedure, this is:

  • Ask "Have you been warden for at least 8192 days?"
    • Yes: I have 13 questions left, use those to binary search on the range 8192-16383
    • No: Wait 1 day, then ask "Have you been warden for at least 4097 days?"
      • Yes: I have 11 questions left, use those to narrow the range 4097-8192 down to a choice of even or odd. Then, wait just enough days to guarantee another question (1-4095 days), and ask which of the two possible answers are right.
      • No: Wait 2 days, then ask "Have you been warden for at least 2051 days?"
        • Yes: I have 9 questions left, use those to narrow the range 2051-4098 down to four possibilities. Then, wait for more questions (4095-6141 days) to narrow it down to one.
        • No: Wait 4 days, then ask "Have you been warden for at least 1031 days?"
          • Continue this cycle to the end, or just wait a little longer and binary search; this process will require at most 8191 days of waiting, or about 22 years.

22 years seems a little long. In practice, I think I'd take a 50/50 gamble to speed things up if the wait time exceeded 10 years.

$\endgroup$
  • $\begingroup$ You have only one question to find the range, not two. $\endgroup$ – ffao Jan 17 '18 at 3:03
  • $\begingroup$ @ffao Crap, off-by-one error! Well, I still aim to maximize the chances of getting out quickly, so I'll adjust it to use just one calibration question. $\endgroup$ – Brilliand Jan 17 '18 at 23:51

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.