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 15
Qn 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|O
We 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 O
means that you can confirm the day after asking the question on that row. This means that for a O
in row 3, you can confirm that possibility in 3 questions.
As such, if you see a O
for 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.