1

There are $N$ balls such that out of these balls only one ball is heavier. We have one balance scale. With it we can know which of two ball groups is heavier. Balls get damaged when weighed, so each ball can take part in a weighing at most $K$ times, where $K \geq 1$. Help find the minimal number of weighings after which we can find the heaviest ball.

Example: If $n = 19, k = 2$, the answer is 3.

Note: Balls cannot be distinguished in terms of appearance.

I know these kind of questions have appeared quite often and their answer is $\lceil log_3(N)\rceil$. But I wonder by restricting $K$ will there be any effect on the answer and why?

savvi singh
  • 293

2 Answers2

1

If $K = 1$, then you can weigh pairs of balls, one on each side of the scale, requiring up to $N/2$ (round down) weighings for $N$ balls.

For $K > 1$, you could use the standard technique of dividing the balls into 3 groups and weighing one group against another until you have narrowed it down to a set that can only be weighed one more time each. Then you must weigh those pairwise.

The optimization is different. For example, you can differentiate up to $9$ balls in $2$ weighings if $K \geq 2$, but if $K = 1$, you can only differentiate up to $5$ balls in $2$ weighings. Plan:

  • Weigh #$1$ vs. #$2$.
  • If different, the heavier one is the one.
  • If same, weigh #$3$ vs. #$4$.
    • If different, the heavier is the one.
    • If same, #$5$ is the one.

Likewise, you can differentiate up to $27$ balls in $3$ weighings if $K \geq 3$, but if $K = 2$, you can only differentiate up to $19$ balls. Plan:

  • Weigh $5$ balls on each side.
  • If different, proceed with plan for weighing $5$ balls with $K=1$, $W=2$, as above.
  • If same, weigh $9$ remaining balls as for $W=2$ and $K \geq 2$ (standard technique).

The maximum number of balls you can differentiate in $W$ weighings will be between $3^K$ and $3^W$.

Recursive formula for max number of balls you can differentiate in $W$ weighings for a given $K$:

$$ M(K,W) = \begin{cases} 1, & K=0\\ 3^W, & K \geq W\\ M(K,W-1) + 2\cdot M(K-1,W-1), & K < W \end{cases} $$

user3294068
  • 1,272
0

Given a number of weighings $K$ the maximum number of balls $N$ is: $$ N = \frac{3^K - 3}{2} $$