A modified problem of finding the heaviest ball

174 Views Asked by At

The Original problem states:

"There are 9 identical looking balls all weighing the same except one(heavier than other)and a physical beam balance is provided. What is the minimum no. of times that the balance can be used to detect the odd one?"

Well , answer is only two times.

Firstly 6 random balls are selected and divided into two groups of three, let us say $G1$ and $G2$

Case 1: If $G1$ and $G2$ are balanced then the odd one is in the remaining three balls group $G3$ (say).

From $G3$ two balls are selected randomly and weighed against each other.

Subcase$(i)$ If one of them is heavier , we would easily see that.

Subcase $(ii)$ If the beam is balanced then the remaining one is odd.

Case $(1)$ ends.

Case $(2)$ If $G1$ and $G2$ are not balanced, let us say $G2$ got heavier. Then we repeat the process for $G2$ as we had done for $G3$.

In any case ,no. of times balance is used is $2$

Now, I am trying to solve a twisted version of the question.

What if a digital weighing machine was provided instead of the beam balance.? (Other informations remain the same)

What would be the minimum answer in this case?

Will it be $4$ since as opposed to beam balance comparing two weights using once only, we have to use the machine two times for the same purpose?

There is the advantage of getting the readings but I couldn't come up with a way to take advantage of that.

Do you have any clever ideas?

2

There are 2 best solutions below

3
On

Four weighings are required

Two weighings will allow you to split the balls into at most 4 groups (weighed first only, weighed second only, weighed twice, and not weighed). Since there are 9 balls, at least one of those groups must have at least 3 balls. We have to assume the heavy ball is in the worst-case group of 3. You cannot find one heavy ball among 3 in only one weighing, it requires 2 weighings to do so. Therefore, we cannot find the heavy ball in only three weighings - you can only do it in four.

0
On

Here is an alternate proof that $4$ weighings are required.

Imagine you know in advance the exact weight of one of the $8$ identical balls. This variant problem is clearly not harder than the original problem. However this variant still requires $4$ weighings, by a simple binary tree argument. Therefore the original problem also requires $4$ or more weighings. (And we already know $4$ weighings suffice.)