Weighing (Editorial)

Divide all the balls into three groups that are as equal in size as possible. If the number $n$ is not divisible by $3$, the sizes of the groups will differ by at most one ball. Two groups of equal size are placed on the pans of the balance. As a result of one weighing, we determine in which of the three groups the heavy ball is located.

Thus, after one weighing, the problem with $n$ balls is reduced in the worst case to a problem with $\lceil n/3\rceil$ balls. Therefore, ⌈log_3n⌉ weighings are sufficient to guarantee the detection of the heavy ball.

Second solution. Let $p$ be the largest exponent for which the inequality 3^p < n holds. Then the minimum number of weighings required to guarantee the detection of the heavy ball is p + 1.

Example

For $3$ balls, a single weighing is sufficient. If the pans of the balance are in equilibrium, then the heavier ball was not placed on the balance.

In the case of $9$ balls, we divide them into $3$ groups of $3$ balls each. By placing one group on each pan of the balance, a single weighing allows us to determine which group contains the heavy ball.

If there are $8$ balls, divide them into three groups as follows: $3,3$, and $2$ balls. In this case, the two groups of $3$ balls are placed on the pans of the balance.

Algorithm implementation

Read the number of balls $n$.

scanf("%d",&n);

Compute and print the answer.

res = ceil(log(n) / log(3));
printf("%.0lf\n",res);  

Algorithm implementation – loop

Read the number of balls $n$.

scanf("%d",&n); 

Compute and print the answer.

res = 0; p = 1;
while (p < n)
{
  p = p * 3;
  res++;
}

printf("%d\n",res);  

Java implementation

import java.util.*;

public class Main
{
  public static void main(String []args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();   
    double res = Math.ceil(Math.log(n) / Math.log(3));
    System.out.printf("%.0f\n",res);
    con.close();
  }
}    

Python implementation

Read the number of balls $n$.

n = int(input())

Compute and print the answer.

print(int(math.ceil(math.log(n) / math.log(3))))