11
$\begingroup$

Suppose you have 240 bottles of juice, one of which has been poisoned.

You also have 5 blue parrots, all of them are immune to the poison, but will turn red 24 hours later and stays red forever upon tasting a sip of the poisoned juice.

it is currently 9 am and you're hosting a huge party 50 hours from now, you'd like to serve out as many bottles as possible while knowing, with certainty, that they are non-poisonous.

*Assume that a parrot can take sips from a bottle as many times you want and you cannot pour the content of a bottle to another to make it as another bottle

*EDIT 1: The parrots can only take the sips at 10 am for them to turn red for weird reasons involving their natural circadian rhythms.

Improve this question
$\endgroup$
11
  • $\begingroup$ So, just to clarify, you cannot pour the content of a bottle to another to make it as another bottle means we can't use group testing? $\endgroup$
    – Parthian Shot
    Commented Mar 7, 2016 at 14:31
  • $\begingroup$ @ParthianShot group testing is allowed but I want to make sure that people don't abuse the loophole by identifying say 5 poisonous bottles, emptying them and use other bottles to fill those emptied bottles partially and claiming them as a whole! $\endgroup$
    – Mc Kevin
    Commented Mar 7, 2016 at 14:33
  • $\begingroup$ Do you mean sips at 10 AM to turn red? $\endgroup$
    – Knight0fDragon
    Commented Mar 7, 2016 at 14:39
  • 4
    $\begingroup$ I think your edit invalidates not only the highest upvoted answer, but also the accepted answer. If the parrots are only allowed to drink at one specific time in 24h, you would have to prepare bottles for the 2nd day before knowing the results from 1st day. Technically it would be even impossible for them to drink from more than 1 bottle per day. $\endgroup$
    – Sleafar
    Commented Mar 7, 2016 at 17:12
  • 1
    $\begingroup$ This is exactly the same as the poisoned wine problem ($n = 240, k = 5, m = 2$) — the only difference in the problem statement is that the wine is juice and the test subjects are parrots who turn red instead of prisoners who die. $\endgroup$
    – user88
    Commented Mar 7, 2016 at 19:12

9 Answers 9

Reset to default
9
$\begingroup$

My reading of the question means we need to identify the poisoned bottle in at most 2 rounds of testing. Under these circumstances it's possible to safely serve

239 bottles

The procedure to achieve this is as follows:

on the first day:
Give each parrot 16 bottles of their own.
Give each pair of parrots a sip each from 8 bottles
Give each set of 3 parrots a sip each from 4 bottles
Give each set of 4 parrots a sip each from 2 bottles
Give all five parrots a sip from a single bottle
29 bottles are left over

On the second day we have n red parrots and 5-n blue parrots left
We also have no more than 2^(5-n) bottles so we can uniquely identify the poisoned one with a simple binary test.
This method works for up to 243 bottles.

Improve this answer
$\endgroup$
0
10
$\begingroup$

You can serve

239 bottles

Using the following method:

Give each parrot 48 bottles and note which parrot got which.
Then with 15 minutes apart divide the bottles uniquely between the parrots and let them drink.

A: 48 + 12 of B (after 15m) + 12 of C (after 30m) + 12 of D (after 45m) + 12 of E (after 1 hour)
B: 48 + same but with ACDE
C: 48 + same but with ABDE
D: 48 + same but with ABCE
E: 48 + same but with ABCD

case: A turns red after 1 hour and B after 1h + 15m
12 bottles can contain the poison

Divide the 12 bottles between the parots and then divide uniquely the others again (just as above)
C: 4 + 1 of D (after 15m) + 1 of D (after 15m) + 1 of E (after 15m) + 1 of E (after 15m)
D: 4 same but with CCEE
E: 4 same but with CCDD

case: C turns red after 1 hour and D after 1h + 15m

Conclusion: you found the poison bottle and you can serve the other 239 bottles.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Sorry, see edit 1. $\endgroup$
    – Mc Kevin
    Commented Mar 7, 2016 at 14:29
  • $\begingroup$ Is this allowed? It says the parrots can only sip at exactly 10 am. Your method requires them to sip at 10:00 and then again at 10:15 on both days. $\endgroup$
    – Darrel Hoffman
    Commented Mar 7, 2016 at 15:24
  • $\begingroup$ @DarrelHoffman It was allowed when being posted (prior the edit), hence McKevin's "Sorry". It is no longer a valid method. $\endgroup$
    – BmyGuest
    Commented Mar 7, 2016 at 15:24
4
$\begingroup$

This answer is DISPROVED

We can have maximum

235 bottles.

Something that can be done is that

First let every parrot have 60 bottles such that one parrot always have 20 bottles in common with each of them. To explain this...let us say that 4 parrots drank 60 sips of bottles. So every bottle is covered. Now let the fifth parrot have 15 bottles of each of the other parrots. By doing this we can be sure that which bottle can have the poison. Now we have two cases based on the number of parrots who changed their colors.
enter image description here
In this picture each of the four colored squares represents one of the four parrots. The square in the middle is the parrot who takes 15 sips from each bottle.

CASE 1 - If only one parrot turns red

Then we know that there are 45 bottles in which there can be the poison. This time we have only four parrot because one has turned red. Now we can repeat that process again. Giving 3 parrots 15 bottles each and giving the last parrot 15 bottles, 5 from each of the other parrot's bottles. In the end we have to throw away minimum 5 bottles...So we have 235 bottles for guests.

CASE 2 - If two parrots turn red.

Then we know that 15 bottles are poisonous. This time we have only 3 parrots remaining. So this time we will give each parrot 5 bottles. One of them will turn red. So we will have 235 bottles for the guests

Improve this answer
$\endgroup$
1
  • $\begingroup$ close but no cig =D $\endgroup$
    – Mc Kevin
    Commented Mar 7, 2016 at 14:31
3
$\begingroup$

Naively,

The upper bound for wasted juice bottles is 24. You have 50 hours, which is greater than 24 x 2, which means you have ten opportunities to check bottles in groups of 24 (i.e., Divide bottles into 10 groups of 24; split those 10 groups into two groups; from the first group, assign each group of 24 to one parrot, and have that parrot take a sip from each of the bottles. If no parrot is red within 24 hours, repeat the process with the other group-of-groups of bottles. Whichever parrot is red 24 hours later, remove that parrot's group of 24 bottles from service). You are now left with 216 Definitely Not Poisoned bottles of juice.

Improve this answer
$\endgroup$
2
  • $\begingroup$ far from optimal $\endgroup$
    – Mc Kevin
    Commented Mar 7, 2016 at 14:24
  • 3
    $\begingroup$ @McKevin I know! Hence "naively" $\endgroup$
    – question_asker
    Commented Mar 7, 2016 at 14:26
3
$\begingroup$

Another optimal solution that I believe is equivalent to @user19942's, but more intuitive to me (as a programmer):

Number and label the the bottles with 5 digit serial numbers in base 3 (i.e. 00000, 00001, ..., 22212, 22220). Each parrot will give you one digit of the poisoned bottle's serial number: On the first day each parrot should sip from bottles having a '1' in their digit position, and on the second day they'll sip from bottles having a '2' in their position. Each digit can then be decoded as a '1' or '2' if its corresponding parrot turns red tomorrow or the day after respectively, or a '0' if the relevant parrot is still blue.

This solution also has the advantage of letting you plan all of the trials in advance - as @Sleafar has implied in a comment, the accepted answer requires you to instantaneously prepare the Parrots' breakfast beverages at 10AM on the second day after noting which ones have changed colour.

Improve this answer
$\endgroup$
3
  • $\begingroup$ To further @Sleafar 's point you seem to be watering down the quantity of information you can get on day 1 because there are 3 possibilities for a given digit instead of 2. Both 0 and 2 do not get tested on Day 1. $\endgroup$
    – Mark Balhoff
    Commented Mar 7, 2016 at 19:02
  • 1
    $\begingroup$ @Sleafar & Mark: that's not an issue here - for simplicity I've stated that every parrot takes a drink on every day, but each parrot will only be drinking the poison on at most one day, because the poisoned bottle's serial number can't have a '1' and a '2' in the same position. In other words, each parrot samples roughly 1/3 of the bottles on each day, with no overlap between the two days. If they turn red from the first day, we know they wouldn't have turned red from the second day since the poison was in the first batch and can't be in both. $\endgroup$
    – Joe Lee-Moyet
    Commented Mar 7, 2016 at 19:07
  • $\begingroup$ Ok I missed a piece of your method on first read. This is mathematically equivalent to the other answers/comments indicating a binary assignment on Day 1 and another on Day 2. You are just combining the two numbering assignments. $\endgroup$
    – Mark Balhoff
    Commented Mar 7, 2016 at 19:36
2
$\begingroup$

Since it is 9 am now, in 50 hours, 10 am comes twice, so we will have two trials, assuming we have any birds left.

The first trial idea comes from @manshu. We will split the bottles up into 4 groups of 60 and label them and number them. The first group will be $A=\{a_1, ... a_{60}\}$ for example.
We will then create a fifth group $E=\{a_1, ... a_{15}, b_1, ... b_{15}, c_1, ... c_{15}, d_1, ... d_{15}\}$.

Now label all the parrots $A, B, C, D, E$ and give them a sip from all the bottles in their same named group at 10 am of the first day.

In 24 hours, you will have one of 2 cases:

1 parrot turns red. You can exclude all bottles in $E$ and the other three groups. This means that the poisoned bottle is one of 45 bottles in that group, and you have 4 birds remaining.
2 parrots turn red. This means that the poisoned bottle is one of 15 bottles in that group, and you have 3 birds remaining.
Now we can number the bottles in binary and take the lower bits to decide which bird to feed it to. For example, if the bottle number is 35, in binary it is 100011. If you have 4 bird, then use the last 4 bits 0011 and feed it to the first and second bird, since the first and second bit are set in that number. Repeat with all the bottles.
If you started with 4 birds and 45 bottles, then you can see which birds turn and re-create the binary number. If birds 3 and 4 change, then the binary number is 1100. So you know that birds 12 (001100), and 28 (011100), and 44 (101100) might be poisonous.
If you started with 3 birds and 15 bottles, then you can do a bit better and only end up with two possibilities.

Thus, at the end, you can guarantee

237 bottles

are safe.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I'm pretty sure you can only guarantee 236 are safe, not 237. Because, with 45 bottles and 4 birds, you only have 4 bits of resolution on nearly 6 bits of data, so in the worst case you can only narrow it down to $2^2 = 4$ possible bottles. $\endgroup$
    – Parthian Shot
    Commented Mar 7, 2016 at 18:20
  • $\begingroup$ @ParthianShot This isn't the best solution, since that has been accepted. However, when you have 4 parrots, you can identify 16 possible bottles. With 45 bottles, that means that $\frac{45}{16} = 3$ will share those 4 bits. $\endgroup$
    – Trenin
    Commented Mar 8, 2016 at 14:24
2
$\begingroup$

Pour drops from 120 bottles into the five birds' food bowls using a gray code pattern such that no two birds get juice from the same 120 bottles, thus dividing the 240 bottles into 32 ($2^5$) distinct groups. The algorithm for deciding which bird gets which bottle is relatively simple. Assign each bottle a number from zero to 239. Convert that number to binary. If the $n^{th}$ bit from the right of the bottle's number is 1, then the $n^{th}$ bird gets a sip from that bottle. Notice that this means that one in every 32 bottles will not be drank from by any of the birds. Since 240 / 32 = 7.5, in the worst case we will have to discard 8 bottles, because we can't evenly divide the groups.

In other words,

With 0 birds, we must discard all 240 bottles. With 1 bird, we must only discard 120. 2 birds --> 60, 3 birds --> 30, 4 birds --> 15, 5 birds --> $\lceil{}7.5\rceil{}$ = 8. So, you can serve at least 232 bottles, and at most 233.

Of course, that's only in the first 25 hours. In the next 24 hours...

You can repeat the process from before. In fact, you only need three parrots this time, because you only need a 3-bit gray code since there are only 8 options. So you can serve a total of 239 drinks. That is assuming that at least three birds weren't used in the first round, which cannot be guaranteed. The algorithm is the same from before, except with only those 8 bottles which may be poisoned and only those birds which have not changed color. Again, due to the nature of this test, we cannot guarantee we will still have any birds to use at this point, so in the worst case we only have 232 usable bottles, 1 out of every 32 times we'll lose 8 bottles, and the rest of the time we'll lose fewer than four bottles.

How good is this solution?

It's optimal most of the time. We have at worst 5 bits of resolution, and at best 10 bits of resolution. Since we only have 240 bottles, the identity of the poisoned one is contained in slightly under 8 bits of information. Since this solution depends on the probability distribution of the number of birds we'll have left over, it's possible to give the exact expectation of remaining bottles along with the variance. However, since that distribution is skewed by the fact that we have 240 bottles, and not 256, the math is mildly annoying, so I'm not going to do that calculation. Suffice it to say that about 31 out of every 32 times we'll lose $\le$ 4 bottles. Most of the time we'll lose only the poisoned bottle. E(usable bottles) will be nearly 239.

Improve this answer
$\endgroup$
4
  • $\begingroup$ If after the first round any bird turned red, then the remaining 8 bottles are clear and don't need testing? So the 2nd round can guarantee that there are parorts available! $\endgroup$
    – BmyGuest
    Commented Mar 7, 2016 at 15:29
  • $\begingroup$ @BmyGuest Well, the problem is if we hit a bottle in group 31 (i.e. a bottle such that its binary number's low order bits are 11111). When that's the case, all the birds turn red, and we can no longer test. We simply know that we'll need to discard all bottles in group 31. It's unlikely, but it's not impossible. It will happen roughly once every 32 times we're put in this scenario (assuming the numbers assigned to bottles are uniformly random with respect to the poisoned bottle's location). $\endgroup$
    – Parthian Shot
    Commented Mar 7, 2016 at 15:35
  • $\begingroup$ Just FYI, your comments to me weren't in vain - I was picking up on what you were saying before you deleted them, and then @Trenin filled it out for me. $\endgroup$
    – question_asker
    Commented Mar 7, 2016 at 16:53
  • 1
    $\begingroup$ I've been expanding on the accepted answer's explanation of grey codes. $\endgroup$
    – Parthian Shot
    Commented Mar 7, 2016 at 17:08
1
$\begingroup$

I assume you ment the turn red after taking a sip from the poisonous jouce. After 48 hours and some feeding time I end up with

230 bottles

Assume you place all 240 bottles in one line and give them numbers from 1 to 240.

Let parrot Alfred drink the first half (1 - 120) and parrot Bjorn the second and third quarter (61 - 180). One day later you maybe will find one, two or none of them beeing red. Here comes the clue: when overlapping the bottle-intervals of the red parrots you will end up with one of the four quarters. Let's assume the poison is in bottle 1 to 60. Now do the same trick again, but use three parrots and assign them a diffrent array: parrot Charles drinks 1 to 30, parrot Duffy drinks 11 to 40 and parrot Edguy drinks 21 to 50. Again: One day later overlap their drinking intervals and you will end up throwing 10 bottles away and having a random mixed blue-green quintet of parrots.

Aiye, Pirate!

Improve this answer
$\endgroup$
3
  • $\begingroup$ Wouldnt Afred and Bjorn be red no matter what since they drank juice $\endgroup$
    – Knight0fDragon
    Commented Mar 7, 2016 at 14:38
  • $\begingroup$ Mc Kevin said they will turn all read after drinking. But I think he ment they turn red after drinking the poison. In that case: no: both will be red for 25%, one of them is red at 50% and none at 25%. $\endgroup$
    – Phil
    Commented Mar 7, 2016 at 14:47
  • $\begingroup$ ok red from drinking poison makes this the opposite LOL I am trying to figure it out by red from juice lol could not get past 5 $\endgroup$
    – Knight0fDragon
    Commented Mar 7, 2016 at 14:48
1
$\begingroup$

I am getting

236 served, 4 lost You have 240 bottles, divided by the 5 birds on 10AM Day 1 (1 hour) Each bird has 48, so one turns red leaving 4 birds Divide the 48 by 4, that gives us 12 with 3 birds left so on 10AM day (25 hour) 2 Divide the remaining 12 by 3, on 10 am day 3 (49 hour), giving you 4 bottles you need to drop

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.