There are some 'n' identical balls of which 1 is defective( don't know heavy or light). If you are allowed to use weighing balance 'k' times what can be the maximum value of 'n'?

Every time you use a weighing balance you get 1 bit information where the bit can take 3 values, 0,1,2.(0= equal, 1 = less, 2 = more). Now you can use weighing balance 'k' times, so you have k bits each taking 3 values and thereby can map 3^k points.

But since during heavy or light you don't know whether the defect is on left side of the pan due to light ball or on the right side due to heavy ball. So you can only map 3^k/2 points uniquely. Thus, the maximum value of n = 3^k/2

n = (3^k-3)/2 ...

ReplyDeleteThe answer should be 3^k/2.

ReplyDeleteEvery time you use a weighing balance you get 1 bit information where the bit can take 3 values, 0,1,2.(0= equal, 1 = less, 2 = more). Now you can use weighing balance 'k' times, so you have k bits each taking 3 values and thereby can map 3^k points.

But since during heavy or light you don't know whether the defect is on left side of the pan due to light ball or on the right side due to heavy ball. So you can only map 3^k/2 points uniquely. Thus, the maximum value of n = 3^k/2

Note the question only demands the defected ball. If you also want to know the type of defect, then n = (3^k-3)/2

ReplyDelete