I got this from my friend :There are 1000 wine bottles and exactly one of them is poisoned.You can use as many rats to taste these bottles and a rat may taste as many bottles.If a rat dies on the 25th day from the day of tasting wine bottle then the bottle is piosoned. Question is to minimum number rats required to determine the piosoned bottle on 26th day.Want to check is this the minimum number:if p1,p2,..pk are primes less than 1000 and prime p(k+1) >1000 and let a1,....ak are the highest powers of p1,..pk such that p1^a1<= 1000 ,p2^a2<=1000 ,...,pk^ak<=1000 thenthe minimum number = a1+a2+....+ak

I don't follow your solution. How do work out that you need primes?I get 9.You check 500 bottles on day 1, and another 500 on day 2.Add in 12 imaginary bottles each day so we have 512 bottles and a simple binary problem.Each bottle gets a unique combination of rats, then by mapping which rats are dead after 25 days, you work out which bottle.

Ok I think I didnt make it clear ! The problem states on 1st day you have 1000 bottles and you have to determine on 26th day which bottle is poisoned, so you see if use rats on 2nd day onward it will be of no use ( As rat die 25 days later from the day of having the poison wine)..

here

If the only useful experiment is to feed rats wine on day 1 and see the results on day 26 (i.e., 25 days later), then the optimal pattern is binary and you need 10 rats (which is enough rats to handle 1024 wines).There's a variant of this problem (discussed previously on this forum, see DevonFang's link) where one has a chance to use two feedings. The answer in that case is a trinary pattern with 7 rats (which is enough rats to handle 2187 wines)

QuoteOriginally posted by: Traden4AlphaIf the only useful experiment is to feed rats wine on day 1 and see the results on day 26 (i.e., 25 days later), then the optimal pattern is binary and you need 10 rats (which is enough rats to handle 1024 wines).There's a variant of this problem (discussed previously on this forum, see DevonFang's link) where one has a chance to use two feedings. The answer in that case is a trinary pattern with 7 rats (which is enough rats to handle 2187 wines)Thanks Traden4Alpha and DevonFangsI hve another question what abt minimality of the value 10. I mean to say why not 9 or less possible !!!

Lets say you have 2 bottles of wine. Under the binary method, you need exactly 1 rat which drinks from one bottle and, if the rat dies then that bottle was poisoned, else it was the other.Lets say you have 4 bottles of wine. Under the binary method, you need exactly 2 rats with rat #1 drinking from bottles 1 and 3 and rat #2 drinking from bottles 3 and 4.Each time you double the number of bottles, you need one more rat.Another way to look at it is the information content requirements and information production capacity. With 1000 bottles, you need 10 bits to define which bottle is poisoned. And each rat can produce no more than 1 bit of information. Thus, 10 rats is the minimum.

Simlest way to look at it is by considering how much information you can store on a given number of rats. Each rat has 2 diffent states at the end of 25 days (alive or dead). Hence if you have n rats, then you can use them to represent 2^n different states. Since 2^10 = 1024 > 1000, 10 rats should be enough to organise them such that there is a different combination of alive or dead rats, for each possible poisoned wine bottle. Don't know how you'd arrange them, but that's another question.

In this version minimum 10 rats are required but for the sake of the rats you can encode it such that at most 8 will die.

QuoteOriginally posted by: karakfaIn this version minimum 10 rats are required but for the sake of the rats you can encode it such that at most 8 will die.That's VERY clever! I love it!

And the other rats will be used in drunkard's walk experiments.

here is a pretty hard variant if anyone interested: what if there are exactly two bottles being poisoned, how many rats are needed to identify these two bottles? assume each rat can taste as many bottles but can only be used once (so no 25th/26th complication)

Interesting variant.The first guesstimate answer based on information content is log2(1000*999/2) = 18.93 = 19 rats.The tricky bit is defining the rat-bottle assignment.

Traden4Alpha, it's a good guess, but unfortunately the information-theory bound cannot be reached. this two-poisonous-bottle variant is related to A054961 - only some weak bounds exist (following Erdos et al). for total of 1000 bottles, the answer is 33. the exact number for general n is not known

QuoteOriginally posted by: wileyswTraden4Alpha, it's a good guess, but unfortunately the information-theory bound cannot be reached. this two-poisonous-bottle variant is related to A054961 - only some weak bounds exist (following Erdos et al). for total of 1000 bottles, the answer is 33. the exact number for general n is not knownThat doesn't surprise me. I've seen related brainteasers in which the binary on/off, life/death outcome state provides less than 1 bit of information due to combinatoric uncertainty issues with assigning the potential bit of data to the unknown combinations or permutations inherent in the problem.