Exercise (Goodrich & Tamassia): Au evil king has n bottles of wine, and a spy ha
ID: 640666 • Letter: E
Question
Exercise (Goodrich & Tamassia): Au evil king has n bottles of wine, and a spy has just poisoned one of them. Unfortunately, the king does not know which bottle was poisoned. The poison is very dewily but slow-acting; a single drop iii a bottle of wine will kill anyone tasting it, but only after one month. By assigning n tasters, one to each bottle, the king can know which bottle is poisoned after one month. Design a scheme which allows him to determine the poisoned bottle within one month hut with many fewer tasters, and characterize the number of tasters ne*led as a function of n. With your scheme, what are the smallest, largest, and average number of tasters who will die on the job?Explanation / Answer
In order to test all cups with minimal amount of people, people have to drink from multiple cups. For example if there are 4 cups: P1 = {C1, C2} P2 ={C2, C3} If person 1 dies alone then it was cup 1, if person 1 and 2 dies it was cup 2, if only person 2 dies it was cup 3, if no one dies it was cup 4.
Each person will either die of live, so for 2 people we have
2*2 possible outcomes (possible drinks) which I went through above
# of drinks = 2^n or
# of tasters n = ceiling(log_2 # of drinks)
The smallest possibillity is that nobody dies
the maximum possibility is that they all die, all n found with function
Im not really sure what it means by average but I think it might be: avg= n(n+1)/(2n) = (n+1)/2
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.