Question

In: Computer Science

6. An evil king has n bottles of wines, and a spy has just poisoned one...

6. An evil king has n bottles of wines, and a spy has just poisoned one of them. Unfortunately, they do not know which one it is. The poison is very deadly; just one drop diluted even a billion to one will still kill. Even so, it takes a full month for the poison to take effect. Design a scheme for determining exactly which one of the wine bottles was poisoned in just one month’s time while expending O(log n) taste testers.



Java Language....

Solutions

Expert Solution

consider each bottle has t Label from 1 to n , and consider each as a binary number.
e.g. 11 bottles

i.e 00000001,00000010,00000011,00000100,00000101,00000110,00000111,000001000,000001001,000001010,000001011,

Now, from the right to left , first take a drop from each of the bottles whose rightest bit is set to '1' and deposited it in the first cup.
next take a drop from each bottle whose 2nd bit is set '1' and deposited it in the second cup.
Continue in similar metod through the highest bit,for that  total we need 4 cups and 4 tasters.

taster4 taster3 taster2 tester1
cup4     cup3    cup2     cup1

now we need to map the tasters to cups and map the cups to bits, so map tasters to bits
command tasters to drink. In a month, some of your tasters will become dead.
(e.g. taster3 and taster1 become dead)
then set the corresponding bits to 1, and all other bits to 0. The resulting binary number
00000101 will identify the poisoned bottle.
Finally number of tasters f(n) = (int)(logn)+1 , so f(n) is O(logn)


Related Solutions

CASE STUDY CH.6 A spice manufacturer has a machine that fills bottles. The bottles are labeled...
CASE STUDY CH.6 A spice manufacturer has a machine that fills bottles. The bottles are labeled 16 grams net weight so the company wants to have that much spice in each bottle. The company knows that just like any packaging process this packaging process is not perfect and that there will some variation in the amount filled. If the machine is set at exactly 16 grams and the normal distribution applies, then about half of the bottles will be underweight...
CASE STUDY CH.6 DROPBOX ASSIGNMENT A spice manufacturer has a machine that fills bottles. The bottles...
CASE STUDY CH.6 DROPBOX ASSIGNMENT A spice manufacturer has a machine that fills bottles. The bottles are labeled 16 grams net weight so the company wants to have that much spice in each bottle. The company knows that just like any packaging process this packaging process is not perfect and that there will some variation in the amount filled. If the machine is set at exactly 16 grams and the normal distribution applies, then about half of the bottles will...
A student has two compounds in two separate bottles but with no labels on either one....
A student has two compounds in two separate bottles but with no labels on either one. One is an unbranched alkane, octane (C8H18); the other is 1-hexene (C6H12), an unbranched alkene. Based on your observations in this experiment, tell what you should observe via the following tests:                                                             Octane                  1-Hexene A. Water solubility B. Ligroin solubility C. Density versus water D. Bromine test E. Permanganate test
A student has two compounds in two seperate bottles but with no labels on either one....
A student has two compounds in two seperate bottles but with no labels on either one. One is an unbranched alkane, C8H18; the other is 1-hexane, and unbranched alkene, C6H12. What should you see in the following tests:                                                           Octane                              1-Hexane A. Water Solubility B. Ligroin Solubility C. Combustion D. Density vs water E. Bromine Test F. Permanganate Test
The Crown Bottling Company has just installed a new bottling process that will fill 16-ounce bottles...
The Crown Bottling Company has just installed a new bottling process that will fill 16-ounce bottles of the popular Crown Classic Cola soft drink. Both overfilling and underfilling bottles are undesirable: Underfilling leads to customer complaints and overfilling costs the company considerable money. In order to verify that the filler is set up correctly, the company wishes to see whether the mean bottle fill, μ, is close to the target fill of 16 ounces. To this end, a random sample...
The Crown Bottling Company has just installed a new bottling process that will fill 16-ounce bottles...
The Crown Bottling Company has just installed a new bottling process that will fill 16-ounce bottles of the popular Crown Classic Cola soft drink. Both overfilling and underfilling bottles are undesirable: Underfilling leads to customer complaints and overfilling costs the company considerable money. In order to verify that the filler is set up correctly, the company wishes to see whether the mean bottle fill, μ, is close to the target fill of 16 ounces. To this end, a random sample...
The Crown Bottling Company has just installed a new bottling process that will fill 16-ounce bottles...
The Crown Bottling Company has just installed a new bottling process that will fill 16-ounce bottles of the popular Crown Classic Cola soft drink. Both overfilling and underfilling bottles are undesirable: Underfilling leads to customer complaints and overfilling costs the company considerable money. In order to verify that the filler is set up correctly, the company wishes to see whether the mean bottle fill, μ, is close to the target fill of 16 ounces. To this end, a random sample...
The Crown Bottling Company has just installed a new bottling process that will fill 16-ounce bottles...
The Crown Bottling Company has just installed a new bottling process that will fill 16-ounce bottles of the popular Crown Classic Cola soft drink. Both overfilling and underfilling bottles are undesirable: Underfilling leads to customer complaints and overfilling costs the company considerable money. In order to verify that the filler is set up correctly, the company wishes to see whether the mean bottle fill, μ, is close to the target fill of 16 ounces. To this end, a random sample...
The Crown Bottling Company has just installed a new bottling process that will fill 16-ounce bottles...
The Crown Bottling Company has just installed a new bottling process that will fill 16-ounce bottles of the popular Crown Classic Cola soft drink. Both overfilling and underfilling bottles are undesirable: Underfilling leads to customer complaints and overfilling costs the company considerable money. In order to verify that the filler is set up correctly, the company wishes to see whether the mean bottle fill, μ, is close to the target fill of 16 ounces. To this end, a random sample...
The Local Bottling Company has just installed a new bottling process that will fill 16-ounce bottles...
The Local Bottling Company has just installed a new bottling process that will fill 16-ounce bottles of the popular Paradise Classic Cola soft drink. Both overfilling and underfilling bottles are undesirable: Underfilling leads to customer complaints and overfilling costs the company considerable money. In order to verify that the filler is set up correctly, the company wishes to see whether the mean bottle fill, μ, is close to the target fill of 16 ounces. To this end, a random sample...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT