8
$\begingroup$

You are the ruler of a medieval kingdom. This time, you've decided to throw a royal party with 10,000 bottles of wine, rather than just 1,000.

You remember the problems the courtier gave you with the wine last time — you search the kingdom high and low for a wine bottler who can produce 10,000 bottles in time for your party, but alas, the courtier is your only choice.

You plead with the courtier not to poison the wine this time around, under the threat of refusing to pay for the wine received — alas, on the day the courtier delivers the wine, it comes with a note containing exactly what you'd dreaded.

Your Majesty,

I must apologize deeply; for you see, a demon has besotted me. I simply cannot help myself. I have once again poisoned one of the wine bottles.

Whoever should drink the poison shall die at the stroke of midnight on the day that it touches their lips, but only if they drink it in the morning, before noon. Should they drink it in the evening (or indeed any time after noon), they will die at the stroke of noon the next day.

As you had so threatened me, so I shall not request payment for this wine.

— Your Humble Courtier

You grumble under your breath. You're going to have to kill some prisoners in testing again — you're running out of death row inmates in your dungeon to use for this!

It's currently morning, and your party is set to start at the stroke of noon two days hence. What's the fewest number of prisoners you can use to test to find the poisoned bottle, and possibly force the courtier to drink it himself?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ The difference between this problem and other poisoned-wine problems is that there's a limited mechanism to perform a timing attack, which is usually disallowed. $\endgroup$
    – user88
    Commented Mar 10, 2016 at 2:54

1 Answer 1

Reset to default
6
$\begingroup$

I think the same generalized strategy described in this answer applies. Though the time of death occurring after the end of the subsequent window makes the bookkeeping a little trickier, you can "pipeline" the wine (drinking the next batch while waiting to see if the first will kill you), but I don't see a way to use that to further reduce the needed number of prisoners.

You can identify the poisoned bottle with six prisoners:

Assign each prisoner a number 1–6, and each bottle a 6-digit label in base 5 (000000, 000001, ... 304444).

There are four poison-able time windows before the party: today morning ($t=0$; die at midnight tonight), today evening ($t=1$; die tomorrow at noon), tomorrow morning ($t=2$; die at midnight at the end of tomorrow), and tomorrow evening ($t=3$; die at the commencement of the party—cutting it close!).

During time window $t$, prisoner $n$ should drink from every bottle where the $n^{th}$ digit equals $t$. Record when each prisoner dies—if a prisoner doesn't die when the party starts, consider it a $4$. The times of death will indicate the poisoned bottle, which, if at least one prisoner survives, you may have to pluck from the hands of an eager guest.

(If you're uncomfortable cutting it that close, you can skip the the final time window, which only requires using one additional prisoner with 7-digit base-4 labels on the wine, up to 2130033).

For example, say that the poisoned bottle is $134401$. The following would take place:

  • At $t=0$ (6:00am on the first day), prisoner 2 would drink from this bottle. Prisoner 2 would also drink from many other bottles, and other prisoners would drink from other bottles, but no other prisoner would drink from this bottle at this time because the only 0 (current time slot) is in the second prisoner's position.
  • At $t=1$ (6:00pm on the first day), prisoners 1 and 6 would drink from this bottle
  • At midnight on the first day, prisoner 2 dies. This is the first data point. You then know that prisoner drank the poison during $t=0$. So start to recreate the bottle number by putting a 0 in that prisoner's position: $XXXX0X$.
  • At $t=2$ (6:00am on the second day), no one drinks.
  • At noon on the second day, prisoners 1 and 6 die. Record the poisoned bottle number as $1XXX01$.
  • At $t=3$ (6:00pm on the second day), prisoner 5 drinks.
  • At midnight on the second day, no one dies.
  • At noon on the third day (start of the party), prisoner 5 dies. Record the poisoned bottle number as $13XX01$.
  • No one else dies at noon, so you know that the last 2 prisoners (3 and 4) didn't drink from this bottle at all. Record the number as $134401$. Go find that bottle and remove it from the party, hopefully before anyone has had a chance to drink from it.
Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Note that with this strategy, prisoner 6 (or which ever prisoner you choose to represent the most significant digit) is guaranteed to die. If you had the numbers range from 140000 - 44444, then you could on average kill slightly less prisoners since the number of occurrences of the digit 4 is higher in this number set. $\endgroup$
    – Trenin
    Commented Mar 10, 2016 at 15:22
  • $\begingroup$ @Trenin: I guess you could potentially save that last one by not letting him drink at t=3. $\endgroup$
    – EagleV_Attnam
    Commented Mar 10, 2016 at 17:08
  • 1
    $\begingroup$ @Trenin, we're only concerned with how many prisoners are required for the test, not maximizing their chances of survival. $\endgroup$
    – Ian MacDonald
    Commented Mar 10, 2016 at 19:02
  • $\begingroup$ @IanMacDonald I understand, but maximizing their survival is a trivial offset. $\endgroup$
    – Trenin
    Commented Mar 10, 2016 at 19:15
  • $\begingroup$ @Trenin Yep "running out of /death row/ inmates" - more importantly once we have XXXX0X we can stop serving non-matching bottles to prisoners to conserve wine for the knees-up. $\endgroup$
    – Jonathan Allan
    Commented Mar 11, 2016 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.