Question

Problem 7. (20 pts) Professor Harry Potter has devised an ingenious concoction: it looks like water, tastes like water and resembles water in any way, shape or form, and yet consuming even a single drop of this potion will cause the drinker's skin to turn bright blue for a day. However there's a delay in the effect of the potion_it takes about 45 minutes for the effect to kick in. Alas, Prof. Potter's students, showing him the same respect undergraduates show to their professors (sigh), have scraped off the bottle's label and hid it among n - 1 water bottles. So now Prof. Potter's cabinet holds n identically looking bottles, where one of them is the turn-skin-to-blue potion and the rest contain very ordinary water. To make matters worse, Prof. Potter has no more than 1 hour to find the potion before potion-class begins. Luckily, he can still call on a few of his trusted grad-students (and on you!) to assist him in finding the potion. Help Prof. Potter! Design an algorithm that finds which one of n bottles contains the special potion in a single hour, using no more than「log(n)| tasters. Prove your claims Hint: Start by thinking recursively. The cases of n = 1 or n 2 are easy. Assuming you have a "tasting scheme" for n bottles with k drinkers, devise a potion-finding tasting scheme for 2n bottles using k+1 tasters. Then "unravel" the recursion to see what bottles the j-th taster drinks from. It is OK if you think of n as a power of 2 for the purpose of finding the algorithm, but your algorithm should work for any n. (Also, it is probably a tad more convenient to number the bottles from 0 to n - 1 rather than from 1 to n

Answer 1

solution:

there could be one possible solution for all of it. it is we allow

the number of trusted students to be k and identitacl bottle to be n.

then always the number 2^k>=n (number of bottle). if this condition is satisfied then and then only we will be able to find the potion is present in which bottle.

for a example i may give you the number of bottle to be 1000 and the trusted number of student is 10 or more but less because then it will violate our rule of 2^k>=n.

now start mentioning every bottle from 1 onwards to 1000 in binary form i.e

decimal form binary form according

for no. of number of students

bottles which are trusted

------------------------------------------------------

1 = 0000000001 as there are 10 student which are trusted so we arrange

2 = 0000000010 them in a order of 10,9,8,7,6,5,4,3,2,1

3 = 0000000011

4 = 0000000100

. .

. .

and so on for 1000

now for a sample case you can see if the required bottle is 10, whose binary form in 10 bits is 0000001001 so it is tested by 1th and 4th student whose skin turns out to be bright blue.

hope this helps

regards.