Problem of the Day -- King's Wine

King's Wine

In celebration of our king finding the village that was cheating him he decides to throw a celebration for the other 9 villages. In preparation for the celebration he orders 1000 barrels of the finest wine.

When the members of the uninvited village find out about the party they send an assassin to poison one of the barrels of wine. The poison takes 7 days to kill so the party guests won't realize what is happening for awhile.

However, after poisoning a random barrel the king's guard finds out and has the assassin executed. There is no time to order more wine so the king devises a genius plan to have his 10 loyal servants taste test the wine to find the poisoned barrel just in time for the party in 10 days. What is the plan that he devises so that he is left with 999 barrels of wine for the party?

As a bonus, RSS and Atom feeds are now up!

Update: Added number of days until party (10)

Permalink: http://problemotd.com/problem/kings-wine/

Comments:

Jake - 10 years, 1 month ago
Divide the 1000 barrels into two even groups of 500. Mix one drop of wine from each barrel in the subset of 500 into a cup and have a servant drink that cup. If he dies then the poison is in one of those 500 barrels, if he lives its in the other set of 500 barrels. Take the subset of barrels you know to contain the poison and repeat this process. It would at most kill all 10 men but after that the poisoned barrel would be obvious.

reply permalink
THOR - 10 years, 1 month ago
test 10 barrels per day.

the poisonous barel will be know in the 7th day (best) or in the 107th day (worst case)

reply permalink
Oli - 10 years, 1 month ago
For 3 days, each servant tastes 100 barrels: - Day 1: 1st servant tastes barrels 1-100, 2nd servant tastes barrels 101-200, ... , 10th servant tastes 901-1000 - Day 2: 1st servant tastes barrels 1-10, 101-110, ... 901-910, 2nd servant tastes barrels 11-20, 111-120, ... 911-920, ..., 10th servant tastes barrels 91-100, 191-200, ... 991-1000 - Day 3: 1st servant tastes barrels 1, 11, 21, ..., 991, 2nd servant tastes barrels 2, 12, 22, ..., 992, ... 10th servant tastes barrels 10, 20, 30, ..., 1000. Wait 7 days, and you will know which barrel contains the poison...

reply permalink
Anonymous - 10 years, 1 month ago
Day 8: Servant 1 dies. Day 9: Servant 2 dies. Day 10: No servant dies.

Need more steps.

reply permalink
c2k - 10 years, 1 month ago
Divide the wine up into 10 batches.

Have each servant take a sip from each batch. One of the servants will die. Isolate that batch.

You now have 100 barrels of wine and 9 servants left.

split up your barrels again, 8 batches of 11 barrels and 1 batch of 12 barrels. Mix'em on up, have the servants partake.

Again 1 servant will die. You are left with either a batch of 12 barrels or 11 barrels, worst case, let's go with 12.

So you have 12 barrels of wine and 7 servants left, not bad!

At this point you can be lazy and just start going down the line 1 by 1, eventually a servant will die and that is the barrel.

This is the most piss poor inefficient method in terms of time of course. You can do a lot better if you stagger days of consumption and note what day a servant dies on.

reply permalink
M - 10 years, 1 month ago
Divide the barrels into groups of 1, 10, 45, 120, 210, 252, 210, 120, and 32.

Teh first barrel can be set aside untasted.

Let the ten servants taste one each of the next 10 barrels. Keep track of who taste what.

Then have two persons taste wine from each of the next 45 so that no two servants taste more than one barrel together. From combinatorics we have (10 choose 2) = 45.

Further (10 choose 3) = 120 so we can have a unike set of three servants drink from everyone the next 120 barrels.

Now, just continue this system. (10 choose 4) = 210, (10 choose 5) = 252, (10 choose 6) = 210, (10 choose 7) = 120.

We now have 32 barrels left. We let 8 servants drink from every one of the barrels, again such that the exact same combination of servants never drink from more than one barrel. ((10 choose 8) = 45, so some groups of 8 will have to pass, but I bet they are drunk enough anyway.)

Then we wait a week. If no one dies, the first barrel we put aside contains the poison. If three persons die, we find the one barrel that those three one no one else tasted. And so on. For every combination of servants that might die, there is exactly one barrel they and only they have tasted together.

reply permalink
ende76 - 10 years, 1 month ago
This is a really good solution! I've made use of this – admittedly very common – concept of combinatorics as well, trying to motivate a way to arrive at an (optimal solution)https://gist.github.com/ende76/9487691 that ends up killing at most 4 servants!

reply permalink
ende76 - 10 years, 1 month ago
Sorry, I seem to have messed up (the link)[https://gist.github.com/ende76/9487691] in the previous post.

reply permalink
ende76 - 10 years, 1 month ago
Sorry, I seem to have messed up the link in the previous post.

reply permalink
John - 10 years, 1 month ago
Number the barrels 0-999. Convert each of these numbers to binary, and use the servants as the binary digits. For each barrel, have the corresponding 1 digits take a drink.

The loyal but dead subjects will tell you exactly what barrel is poisoned.

Solved in 7 days, just in time for the banquet...

However, a wiser king would use subjects of the uninvited town instead of his own loyal servants.

reply permalink
Max Burstein - 10 years, 1 month ago

lol touché

reply permalink
toteto - 10 years, 1 month ago
Nice one, never thought of this one.

reply permalink

Tim - 10 years, 1 month ago

Here's some Java, solves within 7 days.

package com.tim.march;

import java.util.ArrayList; import java.util.Collection; import java.util.List; import java.util.Map; import java.util.TreeMap;

import junit.framework.TestCase;

public class Problem10 extends TestCase {

private static int BARRELS = 1000;

public void test1() {
    int poisoned = (int) (Math.random() * BARRELS + 1);
    System.out.println("Random barrel poisoned = " + poisoned);

    List<Integer> 
         person1 = new ArrayList<Integer>(), 
         person2 = new ArrayList<Integer>(), 
         person3 = new ArrayList<Integer>(), 
         person4 = new ArrayList<Integer>(), 
         person5 = new ArrayList<Integer>(), 
         person6 = new ArrayList<Integer>(), 
         person7 = new ArrayList<Integer>(), 
         person8 = new ArrayList<Integer>(), 
         person9 = new ArrayList<Integer>(), 
         person10 = new ArrayList<Integer>();


    List<Integer>[] people = new List[]{ person1, person2, person3, person4, person5, person6, person7, person8, person9, person10};

    Map<Integer, Integer[]> musterPoints = createMusterPoints();

    populatePersonWithValues(person1, musterPoints, 2, 0);
    populatePersonWithValues(person2, musterPoints, 4, 0);
    populatePersonWithValues(person3, musterPoints, 8, 0);
    populatePersonWithValues(person4, musterPoints, 16, 0);
    populatePersonWithValues(person5, musterPoints, 32, 0);
    populatePersonWithValues(person6, musterPoints, 64, 0);
    populatePersonWithValues(person7, musterPoints, 128, 0);
    populatePersonWithValues(person8, musterPoints, 256, 0);
    populatePersonWithValues(person9, musterPoints, 512, 0);
    populatePersonWithValues(person10, musterPoints, 1024, 0);

    List<Integer> candidates = new ArrayList<Integer>();

    if (person1.contains(poisoned)) {
        candidates.addAll(person1);
    } else {
        for (int i=0;i<BARRELS;i++) {
            if (!person1.contains(i)) {
                candidates.add(i);
            }
        }
    }

    for (List<Integer>person:people) {
        removeOrRetain(poisoned, candidates, person);
    }

    for (Integer candidate:candidates) {
        System.out.println("I'm choosing : " + candidate);
    }

}




private void removeOrRetain(int poisoned, List<Integer> candidates, List<Integer> person) {
    if (person.contains(poisoned)) {
        candidates.retainAll(person);
    } else {
        candidates.removeAll(person);
    }
}

private void populatePersonWithValues(List<Integer> person, Map<Integer, Integer[]> musterPoints, int key, int offSet) {
    Integer[] points = musterPoints.get(key);
    for (int musterPoint: points) {
        for (int i=musterPoint; i<musterPoint+(key/2); i++) {
            person.add(i + offSet);
        }
    }
}

private Map<Integer, Integer[]> createMusterPoints() {
    Map<Integer, Integer[]>musterPoints = new TreeMap<Integer, Integer[]>();

    musterPoints.put(2, getIntList(2));
    musterPoints.put(4, getIntList(4));
    musterPoints.put(8, getIntList(8));
    musterPoints.put(16, getIntList(16));
    musterPoints.put(32, getIntList(32));
    musterPoints.put(64, getIntList(64));
    musterPoints.put(128, getIntList(128));
    musterPoints.put(256, getIntList(256));
    musterPoints.put(512, getIntList(512));
    musterPoints.put(1024, getIntList(1024));

    return musterPoints;
}

private Integer[] getIntList(int i) {
    List<Integer>intList = new ArrayList<Integer>();
    for (int x=0;x<1024;x+=i) {
        intList.add(x);
    }
    return intList.toArray(new Integer[]{});
}

}

reply permalink

sean - 10 years, 1 month ago
This works.

reply permalink
tim - 10 years, 1 month ago
The real problem is getting the comments to load!

Joking aside, in the case of the event happening in seven days, the King asks each of his servants to sip from one wine barrel of their own, then pairs them up and each of them sip from a barrel unique to the pair. This combining and pairing of servants continues until all possible combinations of servants up to 7 have tried unique barrels, leaving 32 barrels to test with combinations of 8 servants and one barrel which no one touches.

At the end of seven days, which combination of servants drop dead (if any do, there's 1 barrel unsipped!) will show which barrel was poisoned.

That said, the king is a just man! If he has 8 days, he will, on the first day, only divide his servants into singletons, doubles, triples, quadruples, and 114 sets of five servants, making a unique 499 barrels per day and risking at most 5 servants' lives.

A tournament in 9 days would risk at most 4 servants, and so on and so on.

An interesting question would be, given a number of servants and the necessity that all of them may die in the process, how far away is the tournament? But I've procrastinated enough for one day, maybe this would make a good programming challenge for the future.

reply permalink
Anonymous - 10 years, 1 month ago
Name the barrels according to their binary representation: 1 -> 00_0000_0001 8 -> 00_0000_0100

Have each servant assigned to one of the 'bits'. The servant samples the barrels with that bit. So servant 1 samples barrels 1,3,5... servant 2 samples barrels 2, 3, 6, 7, ...

After 7 days, based on the servants that die, you know which barrel was poisoned. If servants 1,3, and 5 die, then barrel 10101 = 21 was poisoned.

reply permalink
Amo - 10 years, 1 month ago
I like this answer the best!

reply permalink
rankfocus - 10 years, 1 month ago
The problem here with this binary representation is that it is not optimal. You are not taking into account that you have ten days, but the poison starts after seven days - meaning you have three days to use. You are unnecessarily killing servants. My solution below can use five or less servants.

reply permalink
John - 10 years, 1 month ago
This is not actually true, because you will not know if day 1 was successful until day 7, so on day 2, you still have to have your servants drink. The only way to use extra time to save servant lives is if you have at least 7 extra days.

However, your algorithm does hold, only using 7 as the "extra iteration" number, instead of 1.

reply permalink
John - 10 years, 1 month ago
Wish I could delete that. I was wrong.

reply permalink
FartsFTW - 10 years, 1 month ago
Here's the solution written in MUMPS - Here, I hardcoded the poison to barrel#729 (PABPSN) and jerry-rigged this with the binary method another commenter mentioned. For non-mumps users, I essentially created a database called PABTMP that stored a decimal equivalent of the binary poisition in ten separate positions. (There might be a more practical way of doing this) If the poison is in barrel 729, the binary representation of that would be 10-1101-1001, meaning that persons (from left to right) 1, 3, 4, 6, 7, and 10 died for the king's cause.

BITS S ^PABTMP(1,0)=512 S ^PABTMP(2,0)=256 S ^PABTMP(3,0)=128 S ^PABTMP(4,0)=64 S ^PABTMP(5,0)=32 S ^PABTMP(6,0)=16 S ^PABTMP(7,0)=8 S ^PABTMP(8,0)=4 S ^PABTMP(9,0)=2 S ^PABTMP(10,0)=1 ; S PABPSN=729 S PAB1=0 S PABANS=0 ; F PABA=1:1 S PAB1=$O(^PABTMP(PAB1)) Q:PAB1="" D .S PAB1A=$P(^PABTMP(PAB1,0),U,1) .I ((PABPSN-PAB1A) >= 0) D ..S PABPSN=PABPSN-PAB1A ..S ^PABTMP(PABA,1)=1 ..Q .E S ^PABTMP(PABA,1)=0 .W $P(^PABTMP(PABA,1),U,1) .I ^PABTMP(PABA,1)=1 D ..S PABANS=PAB1A+PABANS .Q W !,PABANS K ^PABTMP,PABPSN,PABA,PAB1,PABANS,PAB1A

reply permalink
FartsFTW - 10 years, 1 month ago
Sorry for the mess - Idk how to format on this page.

BITS S ^PABTMP(1,0)=512 S ^PABTMP(2,0)=256 S ^PABTMP(3,0)=128 S ^PABTMP(4,0)=64 S ^PABTMP(5,0)=32 S ^PABTMP(6,0)=16 S ^PABTMP(7,0)=8 S ^PABTMP(8,0)=4 S ^PABTMP(9,0)=2 S ^PABTMP(10,0)=1 ; S PABPSN=729 S PAB1=0 S PABANS=0 ; F PABA=1:1 S PAB1=$O(^PABTMP(PAB1)) Q:PAB1="" D .S PAB1A=$P(^PABTMP(PAB1,0),U,1) .I ((PABPSN-PAB1A) >= 0) D ..S PABPSN=PABPSN-PAB1A ..S ^PABTMP(PABA,1)=1 ..Q .E S ^PABTMP(PABA,1)=0 .W $P(^PABTMP(PABA,1),U,1) .I ^PABTMP(PABA,1)=1 D ..S PABANS=PAB1A+PABANS .Q W !,PABANS K ^PABTMP,PABPSN,PABA,PAB1,PABANS,PAB1A

reply permalink
FartsFTW - 10 years, 1 month ago
and now is when I give up. nobody can read mumps anyways :/

reply permalink
Max Burstein - 10 years, 1 month ago

Never heard of mumps. Cool solution though. The site currently uses markdown so you can wrap your code in `s and it'll work. Here is some info on markdown formatting http://daringfireball.net/projects/markdown/syntax#code

I plan to move to a slightly more advanced markdown parser in the coming days to and prevent some of the weirdly formatted code.

reply permalink
Abomm - 10 years, 1 month ago
This is a great question!

In my solution, I can actually guarantee that I save the lives of at least five (5) servants, and probably only four less servants will die while testing this wine. To do so, my clarification here is that upon tasting the wine, the servant dies in exactly seven (7) days. Thus, we have three days from the beginning where we can actually time the deaths of servants and analyze the situation.

My solutio works without this exact timing of death, but then we risk all ten servants' lives!

Here is what you do: Label the wine bottles from 1 to 1000. Each bottle will have a unique encoding of servants' names AND the day they drank it. Based on the which servants died (and did not die) and which day each person died at the end of the ten days, we can tell which unique bottle caused the poisoning.

Example: Servants: Allan, Bob, Charlie [A,B,C] We have three different days we can sample wines since we have to wait a week, so the days are [1,2,3]

One label could be [A3,B2,C2]. This means Allan tried this on day 1, Bob tried the same wine on day 2, and Charlie also tried this bottle of wine on day 2 (with Bob). If Allan dies on day 10 (which is a seven days after he sampled it), and Bob dies on day 9, and Charlie dies on day 9, we know it was the bottle with label [A3,B2,C2].

Another label could be ['',B1,C3]. Allan did NOT drink the wine at all (he is a blank), Bob drank it on day 1, and Charlie drank it one day 3. So, if Allan stays alive, Bob dies on day 8, and Charlie dies on day 10, the bottle with label ['',B1,C3] is poisoned.

This describes my encoding. So how do I generate all the possible legal encodings? Remember, you can have each servant sample the wine one or zero times, and the wine must be sampled on exactly one of the three available days.

Assume that we have N = 5 servants, so we have N lists, and each list has the double (2-tuple) of (servant name, day) and a blank. Each list looks like ['', A1,A2,A3 ], ... ['',E1,E2,E3] for servants A through E. We then just take the cartesian product of each of these N lists, which gives us the encodings I described above. There are a total of 1024 such encodings for N=5 servants and three days.

Below is the python 3 code to generate these encodings!

`import itertools

people = ['A','B','C','D','E'] ndays = 3

plist = [[str(p)+str(d) for d in range(1,ndays+1)] for p in people]

need to add blank spaceholder to each at beginning to save lives!

for lister in plist: lister.insert(0,'')

tot = 0 for p in itertools.product(*plist): tot += 1 print(p)

print("final count: {}".format(tot))`

reply permalink
Max Burstein - 10 years, 1 month ago

Well explained. Thanks! Sorry about the weird formatting.

reply permalink
Sakington - 10 years, 1 month ago
List a thru j ( these ten letters signify 10 people )

FIRST DAY each letter tries 100 barrels ( a tries 1-100, b tries 101-200, etc.)

SECOND DAY each letter tries 10 from the previous groups of 100 ( a tries 1-10, 101 -110, 201-210 and b tries 11-20, 111-120, 211-220)

THIRD DAY each tries 1 from from the previous groups of ten ( each person drinks 100 a day) (a tries 1,101,201 b tries 2,102,202 etc.)

wait 7 days

now say barrel 55 of the thousand are poisoned A DIES on day 7 F DIES on day 8 E DIES on day 9

hope this makes sense I did this on my phone but it works and only three should die...

reply permalink
Sakington - 10 years, 1 month ago
Made a typo:

THIRD DAY a tries 1,11,21,31,41,101,111,121,131,141 etc. b tries 2,12,22,32,42,102,112,122,132,142 etc.

reply permalink
Duncan - 10 years, 1 month ago
Represent each of the 1000 barrels as a 10 bit binary number. Assign each servant a bit and each servent drinks from all the barrels where their bit is 1. The dead servants will create a number unique to one barrel

reply permalink
ende76 - 10 years, 1 month ago
I'd like to present a number of solutions, each one a little bit more optimized to save the lives of as many servants as possible.
- Solution 1: Binary Digits for numbers 0-999
  Assign the numbers 0-999 to the barrels, consider the binary representation of those numbers, use the servants as binary digits.
After 7 days, the number that corresponds to the dead servants' digits points to the poisoned barrel.

####Analysis Now, this is a great solution. It's simple yet elegant, and solves the problem with time to spare. However, we'd like to optimize for lives saved, and there's definitely room for improvement on that front! In one of the worst cases – of which there are 5 (barrels #511, #767, #895, #959, #991) – 9 of our servants die. In 36 other cases, 8 servants will die. (Full distribution of deaths, starting with zero deaths: [ 1, 10, 45, 120, 210, 252, 208, 113, 36, 5 ] ).

Let's try to get those numbers down!
- Solution 2: Using all the days!
  Disclaimer: I will assume that the servants have 4 days to sample the barrels, since the time limit is arbitrary anyway. This simplifies some partitions and numbers, conveying the ideas easily. If they really only have 3 days, the same ideas can be applied, albeit with some odd numbers and possible remainders.
A simple way to reduce the number of potentially dead servants is to reduce the number of barrels. However, we have to test all 1000 barrels, so we're stuck here.

Or are we? We could let our servants test only 250 barrels on the first day. So, we number the barrels 0-249, and use Solution 1. If we have dead servants 7 days later, we can identify the barrel just as in Solution 1 using binary digits.

On the second day, the servants test the second batch of 250 barrels. This time, we label those barrels 1-250. If we have dead servants 7 days after this test, we know the poisoned barrel was in this second batch.

We do this with two more batches of 250 each on days 3 and 4, using labels 1-250. If no servant dies at all, we know the poisoned barrel was #0 of the first batch.

####Analysis This solution is better already! By effectively reducing the number of barrels we have to encode each time to 250, we only require 7 servants to begin with, and can send 3 home to their families right away. If the poisoned barrel is in the first batch, the distribution of deaths over the number 0-249 is [ 1, 8, 28, 56, 70, 56, 26, 5 ], giving us 5 out of 250 cases where 7 servants die. If the barrel is in one of the later batches with labels 1-250, we get [ 0, 8, 28, 56, 70, 56, 27, 5 ], meaning that at least one servant will die, but still we only kill 7 servants in the worst case.
- Solution 3: Pack those digits tight!
  Solution 2 looked pretty good, but it seemed odd that we would not make use of 3 servants. Somehow we should be able to improve our results by using all of our resources, right?
We will keep the batches of 250 barrels. But this time, instead of labeling them 0-249, we choose different labels. We will use: * 0, * 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, * 3, 5, 9, 17, 33, 65, 129, 257, 513, 6, 10, 18, 34, 66, 130, 258, 514, …

Now, why those magic numbers, and where do they come from?

Why: We select our numbers from the range 0-1023 (inclusive) so that the binary representation of a number uses as few 1-digits as possible. There's one number with zero 1-digits. There are 10 numbers with exactly one 1-digit. There are 45 numbers with exactly two 1-digits, …

In general, there are 10!/(k!(10-k)!) numbers with exactly k 1-digits. A quick calculation shows us that we can easily cover 250 barrels with numbers having at most four 1-digits!

####Analysis Some of our servants might feel ambivalent about this solution. Because with this approach, we don't send anyone home right away. For our own benevolent purposes however, this solution is great!

In the worst case, only 4 servants will die, and we even get to minimize the number of those cases in our Distribution Of Death!

For the first batch, where we can use the 0, we get a DoD of [1, 10, 45, 120, 74], meaning that in 74 out of 250 cases, 4 servants will die.

For the subsequent 3 batches, we get a DoD each of [0, 10, 45, 120, 75].

Epilogue

This is as good as it gets for this line of thinking. For 4 Days of Potential Death and 10 Willing Testers, we get a worst case of 4 deaths, with an overall distribution as outlined in the analysis above.

The number of days do matter, as do the number of servants.

Extremes: We could have 999 servants. Each servant would sample exactly one barrel, and after 7 days, either: * the dead servant corresponds to the poisoned barrel, or * nobody dies, and the unsampled barrel is the poisoned one. We have 1006 days to find the poisoned barrel. One servant could sample one of 999 of the 1000 barrels each day, and * if he dies, we know the poisoned barrel was the one he tested 7 days earlier, or * if he lives, we know the poisoned barrel was the one he did not test at all.

I'm sure those factors could be optimized for expectation of survival for the individual servants.

If someone can come up with a solution that uses even less than 4 servants in the worst case, or if I have made mistakes, I'd love to hear them!

reply permalink
ende76 - 10 years, 1 month ago
Welp, apprently the site does not support as much markdown as the linked page suggests. It's easier to read in this gist

reply permalink
El Ninja - 10 years, 1 month ago
Easy, with 10 people we get ten bits of address space that maps to the barrels (1 through 1023)

Note we only have 1000 barrels, knowing that actually guarantees that at least 1 will live.

Best case barrel #1 (1 dead)

Worst case barrel #991 (9 dead)

We order the people in a straight line (and for no reason we brand them with a letter A to J)

then in succession, every person with the positive bit in the binary representation of the barrel will have a drink.

$$ A B C D E F G H I J $$

$$ 0 0 0 0 0 0 0 0 0 1 = 001 $$

$$ 0 0 0 0 0 0 0 0 1 0 = 002 $$

$$ 0 0 0 0 0 0 0 0 1 1 = 003 $$

$$ 0 0 0 0 0 0 0 1 0 0 = 004 $$

$$ ----- All Up To---- $$

$$ 1 1 1 1 1 0 0 1 1 0 = 998 $$

$$ 1 1 1 1 1 0 0 1 1 1 = 999 $$

Now we only wait the 7 days, and we will get our binary representation of the barrel that was poisoned.

reply permalink

Problem of the Day A new programming or logic puzzle every Mon-Fri

King's Wine

Comments:

need to add blank spaceholder to each at beginning to save lives!

Solution 1: Binary Digits for numbers 0-999

Solution 2: Using all the days!

Solution 3: Pack those digits tight!

Epilogue

Problem of the Day
A new programming or logic puzzle every Mon-Fri