Maximum number of weighing required to identify defective Wallets

combinatoricslogicpuzzle

There are $10$ wallets and each wallet has Ten coins. In $8$ of the wallets each coin weighs $10$gm. But there are two defective wallets where in each coin weighs $11$gm. If we are allowed to use a Digital weighing machine, Find maximum number of Displays or Weighing Required to figure out two defective wallets. Assume all coins are identical.

My try:

I will arrange the wallets in a row and number the wallets from left to right as $w_1,w_2,w_3,\cdots,w_{10}$

From $w_1$ i will Collect one coin
From $w_2$ i will collect two coins
From $w_3$ i will collect three coins

$\vdots$

From $w_{10}$ i will collect all Ten coins.

This whole collection i will place it on the digital machine. If at all there are no defective wallets then the machine will show the weight as:
$$x=10+20+30+\cdots+100=550$$

But Since there are two defective wallets and we are collecting at least one coin from each wallet the weight shown is more than $x$

Case $1.$ If the weight shown is $x+3$ Then evidently the defective wallets are $w_1,w_2$ Since $3$ can be partitioned as sum of two order independent distinct positive integers as $3=1+2$

Case $2.$ Like wise if the weight shown is $x+4$ then $w_1,w_3$ are defective wallets.

Similarly if the weight is $x+19$ and $x+18$ then $w_9,w_{10}$ and $w_8,w_{10}$ are the defective wallets respectively.

So in all the above just two displays will suffice.

So if we use this Partition logic the maximum number of partitions required is for $11$ as
$$11=1+10=2+9=3+8=4+7=5+6$$

Hence Max number of weighing required is $FIVE$

Let me know is this a valid reasoning?

Best Answer

Nice idea to take different amount of coins from different bags. After first measurement, You will have at most 5 suspected pairs as You mentioned.

Hint: if You take $i$ coins from the $i$ - th pairs and weigh them together, You will be able to tell which pair is defective. That means only TWO weighings

Edit: it does not need to be any specific number from the pairs. as long as you take different amount from different pair

Related Question