How long has the warden been the warden?

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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!

Answer 6

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

Answer 7

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.