This is follow up question to How long has the warden been the warden
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:
- 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).
- 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:
- If it is his first day on the job, you get 1 Y/N question
- If it is his 2nd-3rd day on the job, you get 2 Y/N questions
- If it is his 4th-7th day on the job, you get 3 Y/N questions
- If it is his 8th-15th day on the job, you get 4 Y/N questions
- etc.
- If you ask the warden too many yes/no questions, you will be executed. For example:
- If you ask your 2nd Y/N question and he had his job less than 2 days, you are executed
- If you ask your 3rd Y/N question and he had his job less than 4 days, you are executed
- If you ask your 4th Y/N question and he had his job less than 8 days, you are executed
- If you ask your 5th Y/N question and he had his job less than 16 days, you are executed
- etc.
That's it.
Question:
The only information you have now is that it can be at most $15$ days since warden has been in his position. Given this specific information,
In the worst case scenario, at least how long will it take to get out of the jail with the optimal strategy?
Note: It is assumed that you can count the day in the prison.
Answer
I can do it in
4 Days.
Observation
You always start with a free question.
Warden needs to work at least 2 days for you to ask a 2nd question.
Warden needs to work at least 4 days for you to ask a 3rd question.
Warden needs to work at least 8 days for you to ask a 4th question.
Warden needs to work at least 16 days for you to ask a 5th question.For readability, the days I use in my solution are days the warden has worked at the start. When executing the strategy, just add the # of days that has passed to the questions.
Benchmark: binary search
Worst case: 6 days.
Binary search splits the possible days into half every time, i.e. "Have you worked for more than 7 days?". Using this strategy, it should take exactly 4 questions before you can guess precisely what day it is.
The earlier his start date is, however, the longer we have to wait. The worst case is when he has only worked for 1 day, because then we need to wait 7 days to get 4 questions.
However, binary searches are designed for 2^N possibilities. Since there are 15 possible dates (1..15), some of the splits will not be exactly half, but rather 1 smaller on one side. Abusing this, if we adjust the questions, we're able to make it so that the worst case answer (1) will be discovered in one less question. Therefore, the new worst case answer is (2), where you only need to wait 6 days to get 4 questions
Example:
1: Have you worked for at least 8 days?
Ans: NO - He's worked 1..7 days. You have to wait for 1 day.
Ans: YES - he's worked for at least 8 days, so you already have 4 questions. You can figure out the answer without waiting.2: Have you worked for at least 4 (+1) days?
Ans: NO - He's worked 1..3 (+1) days. You have to wait for 2 more days for the next question.
Ans: YES - he's worked for at least 4 (+1) days, so you already have 3 questions. You have to wait 3 more days to figure out the answer.3: Have you worked for at least 2 (+3) days?
Ans: NO - He's worked for 1 day at the start.
Ans: YES - He's worked 2..3 (+3) days. You have to wait for 3 more days for the next question.4: Have you worked for at least 3 (+6) days?
Ans: NO - He's worked for 2 days at the start.
Ans: YES - He's worked for 3 days at the start.Worst case, 6 days of waiting.
Optimization: Uneven splits
Worst case: 4 days.
An observation you can make is that the longer the warden starts, the more questions you get - And subsequently, the less you need to wait for more questions.
This means it's inefficient to split evenly - you want to try to guess smaller start dates in less questions, while you can afford to ask more questions if he started at later dates.
Here is a solution i found by hand:
Possibilities: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Qn 1 split : ---------|-------------------------Qn 2 split : ---|----- -------|-----------------Qn 3 split : O|O O|--- ---|--- -----|-----------Qn 4 split : O|O O|O O|O O|O -----|-----Qn 5 split : O|O O|OWe start with all 15 possibilities as one big segment. Each row is a question in the form of "have you worked here for at least X days?", which will split the possibilities into two segments represented by the
|("at least 6 days" will show the|between 5 and 6).A
Omeans that you can confirm the day after asking the question on that row. This means that for aOin row 3, you can confirm that possibility in 3 questions.As such, if you see a
Ofor day X at row Y, the 'cost' of figuring out this possibility is the # of days needed to ask Y questions, minus the smallest day of the segment which contains X in the row Y-1.For example, for possibility 5, we can figure it out on question 4 (at least 8 days). However, from the previous questions we know that the warden has worked 4 or 5 days, so we only need to wait 8 - 4 = 4 days. Using this formula for every possible day, we find out that all possibilities are able to be figured out with at most 4 days of waiting.
I don't think this is unique - there may be other partitions that result in 4 worst case days. But to do it in 3 should be impossible, as you'll need to figure out possibilities (1..3) in 3 questions and (5..13) in 4 questions, and that's just plain not enough with this method.
Or, that solution in question form (warning, terrible formatting):
1: Have you worked for at least 6 days?
NO - He's worked 1..5 days. Wait 1 day for next qn.
----2: Have you worked for at least 3 (+1) days?
----NO - He's worked 1..2 (+1) days. Wait 2 more days for next qn.
--------3: Have you worked for at least 2 (+3) days?
--------NO - He's worked 1 (+3) day. 3 days wait.
--------YES - He's worked 2 (+3) days. 3 days wait.
----YES - He's worked 3..5 (+1) days.
--------3: Have you worked for at least 4 (+1) days?
--------NO - He's worked 3 day. 1 day wait.
--------YES - He's worked 4..5 (+1) days. Wait 3 more days for next qn.
------------4: Have you worked for 5 (+4) days?
------------NO - He's worked 4 day. 4 days wait.
------------YES - He's worked 5 days. 4 days wait.
YES - He's worked 6..15 days.
----2: Have you worked for at least 10 days?
----NO - He's worked 6..9 days.
--------3: Have you worked for at least 8 days?
--------NO - He's worked 6..7 days. Wait 2 more days for next qn.
------------4: Have you worked for 7 (+2) days?
------------NO - He's worked 6 days. 2 days wait.
------------YES - He's worked 7 days. 2 days wait.
--------YES - He's worked 8..9 days.
------------4: Have you worked for 9 days?
------------NO - He's worked 8 days. No wait.
------------YES - He's worked 9 days. No wait.
----YES - He's worked 10..15 days.
--------3: Have you worked for at least 12 days?
--------NO - He's worked 10..11 days.
------------4: Have you worked for 11 days?
------------NO - He's worked 10 days. No wait.
------------YES - He's worked 11 days. No wait.
--------YES - He's worked 12..15 days.
------------4: Have you worked for at least 14 days?
------------NO - He's worked 12..13 days. Wait 4 more days for next qn.
----------------5: Have you worked for 13 (+4) days?
----------------NO - He's worked 12 days. 4 days wait.
----------------YES - He's worked 13 days. 4 days wait.
------------YES - He's worked 14..15 days. Wait 2 more days for next qn.
----------------5: Have you worked for 15 (+2) days?
----------------NO - He's worked 14 days. 2 days wait.
----------------YES - He's worked 15 days. 2 days wait.Wow, that unholy mess was the most unreadable solution i've ever written. But hey, the answer is 4 days.
No comments:
Post a Comment