-

There are 1000 buckets, one of them contains poison, the rest are filled with water. They all look the same. If a pig drinks that poison it will die within in 30 mins. What is the minimum amount of pigs you need to figure out which bucket contains the poison.

Répondre

Réponses aux questions d'entretien

14 réponse(s)

6

I make it 10. The first pig drinks from every other bucket. The second pig drinks from the first two buckets, then skips two, and so forth. The tenth pig drinks from the first 512 buckets. Wait 30 minutes. You can determine which bucket is poisoned uniquely from the pattern of porcine mortality - if all the pigs die then then first bucket is poisoned. If none of the pigs die then the last bucket is poisoned (it's a binary encoding). You have 30 minutes to spare. You might think it possible to divide the problem up between these two halves, but since the experiment might kill all your pigs the worst case would be needing 9+9 = 18 pigs, so worse than doing it all in one shot.

Matt le

2

Matt has the right idea with the encoding, but 1 hour gives you time for two passes. So first you divide the 1000 buckets into groups of 32 buckets each. You'll have 32 groups (the last one with only 8 buckets). The 32 groups you can binary encode with 5 digits, so 5 pigs will tell you after 30 mins which _group_ of buckets contains the poisoned one. So for the the second 30 mins you binary encode that group of 32 buckets the way Matt described. This way you're using no more than 5 pigs at any given time. You might still kill a total of 10 in the worst case, but this approach takes advantage of the extra time to reduce the number of pigs used simultaneously. Slightly more efficient.

Karoly le

1

I think the question is missing "within one hour?" at the end. If that's the case then you only get two tests / trials. Start with 33 pigs each drinking from 30 buckets, then wait 30 min. If none die, then it's the leftover bucket, if one dies then get another 30 pigs to drink from the buckets that the dead pig drank from.

Bill le

1

The answer is one. Theoretically if the first pig finds the poisoned bucket the task is complete. Therefore the minimum number of pigs required would be one.

Bee le

1

In the 1 hour case the correct answer is 7 pigs. Saketh is extremely close in his approach, but only considers the loss of one pig in the first set of drinking pigs. For every pig you have remaining going into the second search, the number of tests you can make doubles. Therefore if you can get more than twice as many combinations by sacrificing an extra pig in the first search, then you can test more buckets with the same number of pigs. Using 7 pigs, build every combination from the binary approach listed above that kills no more than 3 pigs. This gives a total of 64 combinations - splitting the buckets evenly amongst them, this gives a maximum of 16 buckets for each combination. Then you have 4 pigs and 16 (2^4) buckets, which is solved as in the previous methods.

James le

0

*Assuming this has to be done within an hour* First step is to put another 24 empty buckets, or pick up pebbles, coins and pretend to be buckets. Think are made easier this way... 1) Split then into two groups, and number them from 0 to 511. 2) Get 9 pigs and put them in a row judging of their cuteness, let's say the cutest pig is on the right and the least cute pig is on the left! 2) define Dead pig =1, alive pig =0. 3) The cutest pig drinks from the last 256 buckets, the next from every second group of 128, etc. The least cute drinks from every other buckets, (1,3,5,etc remember we are counting from zero.) 4) We wait 30 minutes to see if any of the pigs died, if not we repeat with the next group. On a second though, should we wait another 1-2 minutes just in case any pig turns out to be a fighter? How can we be sure that the poison acts exactly after 30 minutes? Remember that we are at a tight timeline so we better give them to drink again exactly after 30 minutes. We can give our self a few sec window before ... ...WAAAAAIT A MINUTE... This has nothing to do with binary coding (nor pigs)! It's all about parallel processing and scheduling your pipelines from getting thirsty. I just need one Pig and a Timekeeper App.

nKast le

0

A pig has 2 tries each within the 1 hour for the test. So for a three bucket case, if it drinks from bucket A first, bucket B second, and doesnt drink from bucket C and doesn't die, we know that bucket C has poison. Now for a 9 bucket case (3**2 = 9), lets arrange the buckets in a 2D matrix and make one pig drink from the entire first row in the first try, and so on. The second pig tries the entire first column in the first try and so on. This way, 2 pigs can identify the x,y coordinates for the poisoned bucket within 1 hour. With three pigs, you can add another dimension, and arrange the buckets in a cuboid form to identify 27 buckets. Keep adding pigs till you reach a min of 1000 to arrive at the answer, which is in this case, 7 pigs that can identify upto 2187 buckets. A generic formula for the same would be: (floor(time_to_test÷time_to_die)+1)**pigs >= buckets.

arjun augustine le

0

I was going with the encoding method until it dawned on me that you would have to wait 30mins from the last sip the last pig took. It might take almost 30 mins for those pigs to get their sip on, so for me, it does not make much sense anymore. If you're not given a time limit I'd start by asking some questions: -You stated they all look the same but do they all smell the same? -How many pigs do I have access to? -Is this time sensitive? -Is the 30-min time to death reliable? With these answers answered you could do a number of solutions: -Smelling each, and having the pig taste the one that smells different. If he dies it's the poison, if not keep trying till you find it. (might not be in 1 hour or might be in 1 hour). Only 1 pig would die in this method. -Using 500 Pigs each sipping at the same time from their dedicated bucket, wait 30 mins if none die run it again on the next 500 buckets. Only 1 pig would die in this method. -With 1 pig go one bucket at a time. 1000 buckets * 30 mins to test= 30,000 minutes of testing if the last bucket contained the poison. That would be 500hrs or about 20 days max to test with 1 pig, 1 bucket at a time. (this could be done in an hour if one of the first 2 buckets contain the poison) I think this is a question with many solutions and is used to see your problem-solving methodology. There is no right answer in my opinion, but this is how I looked at it.

Al le

0

@Ricardo: You're asked to minimize the number of pigs used, not the number of pigs that die. @Bee: The theoretical best case for the number of pigs that die is certainly 1. However, you need a greater number of pigs to be able to complete testing within one hour. Anyway, you can actually do this with 8 pigs if you are given one hour. First pass: split the cups into 8 groups of 125, and use 8 pigs to determine which group the target cup is in (each pig drinks from all of the cups in its assigned group). One of these pigs will die, and you are left with a narrowed field of 125 cups. The 7 pigs you have left are sufficient to binary search on this set of cups, because 2^7 > 125. See Matt's comment above for an explanation of how the binary search works. In the case that you are only given half an hour, I agree that 10 pigs is optimal. It's relatively easy to prove this. Each pig we use will provide us 1 bit of information. Thus, n pigs can produce 2^n different possible outcomes. Since we need to distinguish between 1000 cups, we need at least 1000 distinct outcomes. n=10 is the least value of n for which 2^n exceeds 1000. Thus, n must be at least 10. We know that there is in fact a working strategy with 10 pigs, so we also know that our lower bound is attainable.

Saketh le

0

9 pigs. use 9 pigs to test half the buckets using Matt's binary encoding - 30 minutes. if no pig dies (poor pigs), use the pigs again for the remaining buckets - 30 minutes.

Barry le

0

The previous answers consider as an optimum solution using less pigs, no matter how many of them will sacrifice their lives. I will consider I can use infinite pigs so the optimum criteria is saving pigs lives. In the solutions bellow, at most, 1 pig dies, but it is possible to get the answer without killing any of them, as I will always exclude 1 bucket. In 30min: I need 999 pigs; In 1h: 500 pigs (I use 500 for the 1st round; after 30min, if all of them are alive, I use 499 of them); In 1h 30min: 333 pigs; In 2h: 250 pigs (in the last round I only use 249 of them); ... In 499h 30min: 1 pig.

Ricardo le

0

Matt, thank you!) To others wondering: third pig drinks from the first 4 buckets, skips 4 etc; fourth one drinks from first 8, skips 8 etc; this way if you draw a table with buckets on top and pigs on the left, and populate it with 1 for drank bucket and 0 for untouched one, each column will contain unique set of values (binary rep of 1023 to 0), as 1-1-1-1-1-1-1-1-1-1 for first one and 0-0-0-0-0-0-0-0-0-0 for last one. Just took me a while to figure, though I'm a programmer myself). These days you can program without even knowing binary system, let alone converting drinking swine problem to this rep. p.s. Though 32 pigs will allow you to sacrifice 2 at max :).

Vitaly le

0

The answer is none. You don't need any pigs. Just go round and smell the buckets. It says they all look the same, but you'd smell the poison. And before anyone says it, even an odourless poison would have a different 'nose' (or snout...) to 999 buckets of water (because water is not 100% odorless)

Alister le

3

you just need one pig - it drinks a bucket, wait 30 mins, if it doesnt die, it drinks another, repeat until it dies

dave le

Ajouter des réponses ou des commentaires

Pour commenter ceci, connectez-vous ou inscrivez-vous.