Let's say we have 6 balls, where all of them have different weight.
Find and describe the least weighings you need on scales to find second lightest ball and second heaviest ball.
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
The least number of (two-pan) weighings required is
10
The flowchart below details how to perform the weighings; an unlabelled poset represents all knowledge gathered of the relative weights of the balls. At each step the two black balls are compared, and the situation advanced one step to the right depending on its result.
The code that proved the optimality of this scheme can be found here.
-
1$\begingroup$ Are you assuming you can only put one ball on each side of the balance? It probably is a correct assumption given that the weights can be anything, not necessarily evenly spaced. $\endgroup$ Nov 21, 2022 at 10:32
-
1$\begingroup$ @JaapScherphuis Yes. If say I have two balls a side, there is no information to imply that the pans can or cannot balance. $\endgroup$ Nov 21, 2022 at 11:21
$\begingroup$
$\endgroup$
A possible way:
- Divide the balls into two groups of three. Measure any two of the same group against each other. You'll get something like $A>B>C$ and $D>E>F$ (6 weighings).
- Weigh $A$ against $D$. Let $A>D$ (1 weighing).
- Weigh $B$ against $D$. The heavier one is the second-heaviest (1 weighing).
- Repeat it for the bottom to identify the two lightest (2 weighings). This makes 10.
Generalization:
Divide the balls into groups of 3 to better sort them out to find the four balls. Weigh all the balls in each group against each other. If there's $n$ balls, you spend $n$ turns for the initial sorting, and $n/3-1$ turns each to find the four balls. The sum is $7n/3-4$ weighings.
