Optimal number of weightings in marble problem

Question

Consider $N$ pieces of marble. The pieces of marble look identical to one another. One of the pieces is heavier than the other. In other words, out of the $N$ pieces, $N-1$ have the same weight and $1$ is heavier.

We are given a traditional balance scale with two pans. The goal is to determine which piece of marble is the heavy one using the scale. Denote $u_N$ the minimal number of weightings required to find out the heavy piece of marble.

Intuitively, the number of required weightings should increase with the number of pieces. That is to say that $(u_N)_{N \geq 2}$ should be an increasing sequence of $N$. How do we prove it?

Most strategies to compute $(u_N)$ are based on the recursive division of the pieces in three groups and the weighting of the first group against the second. However, this strategy implicitly uses the fact that $(u_N)_{N \geq 2}$ is increasing. Hence my question.

Answer 1

"Most strategies to compute $(u_N)$ are based on the recursive division of the pieces in three groups and the weighting of the first group against the second. However, this strategy implicitly uses the fact that $(u_N)_{N \geq 2}$ is increasing."

I think I have a proof which circumvents this problem.

$\def\ceil#1{\lceil #1 \rceil}\def\floor#1{\lfloor #1\rfloor}$After performing $k$ weighings, there are $3^k$ possible results of the weighings. If $n>3^k$, then by the pigeonhole principle there would be two marbles being heavy which resulted in the same results, so in that case we cannot deduce the heavy one. Therefore, we need $n\le 3^{u_n}$, which implies $u_n\ge \ceil{\log_3 n} $.

We then prove the corresponding upper bound by strong induction on $n$. Given $n$ marbles, divide them into three groups whose sizes are as close together as possible. Each group will either be of size $\lfloor n/3\rfloor$ or $\ceil{n/3}$, so there will be two groups of the same size. Weighing those against each other will allow you to eliminate all but one group. If that group is of size $\ceil{n/3}$, then applying the optimal method for $\ceil{n/3}$ marbles to that group, $$ u_n \le 1+u_{\ceil{n/3}}\stackrel{1}\le 1+\ceil{\log_3 \ceil{n/3}}=\ceil{\log_3 3\ceil{n/3}}\stackrel{2}{\le} \ceil{\log_3 n} $$ Otherwise, you are left with $\lfloor n/3\rfloor$ marbles, so $$ u_n \le 1+u_{\floor{n/3}}\stackrel{1}\le 1+\ceil{\log_3 \floor{n/3}}\stackrel{3}\le 1+\ceil{\log_3 \ceil{n/3}}\le \dots{\le} \ceil{\log_3 n} $$

1. This is the induction hypothesis.

2. To prove $\ceil{\log_3 3\ceil{n/3}}{\le} \ceil{\log_3 n}$, you just need to show that for any integer $m$ for which $\log_3 n\le m$, you also have $\log_3 3\ceil{n/3}\le m$. I leave the details to the reader, they are not bad.

3. This follows because the function $f(x)=\ceil{\log_3 x}$ is increasing.

Finally, we conclude $u_n=\ceil{log_3 n}$, which is increasing. $\square$

Answer 2

So here is another take on the answer:

First we will use induction: assume that for some $N$, $(u_k)_{2\leq k\leq N}$ is (non-strictly) increasing.

What is the purpose of a weighing?

If we have an unequal number of balls on each side, it's potentially useless since having the side with more balls being heavier than the other side gives us no information. So we can assume that there are an equal number of balls on either side.

If so, the weighing allows us to split the balls into 3 groups, two of the same size, and determine which has the ball.

So now how do we complete our proof?

It suffices to show that if we have a strategy for weighing with $N+1$ balls, we can convert into a strategy for $N$ balls with the same number or fewer weighings.

Let's split into a couple of cases as follows:

Consider the three groups we split the $N+1$ balls into initially for its strategy, suppose they have sizes $a$, $a$ and $b$.

Case 1: $b>0$

Then we can solve $N$ balls by weighing the same groups with sizes $a$, $a$ and $b-1$ initially, since the previous strategy takes $\geq 1+\max(u_a,u_b)$ turns and this one takes $1+\max(u_a,u_{b-1})\leq 1+\max(u_a,u_b)$ turns by our induction.

Case 2: $b=0$

Then we can solve $N$ balls by weighing groups with sizes $a-1$, $a-1$, $1$ (clearly $N\geq2$), since the previous strategy takes $\geq 1+u_a$ turns and this one takes $1+u_{a-1}\leq 1+u_a$ turns by our induction.

A small nuance:

Really we have to have $u_0$ and $u_1$ defined for this - clearly the first is impossible (so can never be an outcome of a weighing) and the second is $0$.

Another problem

As @ffao points out, there is a hole in my argument:

"the case after the first weighing is not u_a nor u_b, because you have extra information: more specifically, you have at your disposal either a+b or 2a balls that are guaranteed to have the regular weight."

However I believe it can be fixed:

We claim that if you have an arbitrary fixed number of balls of normal weight (in both cases), the amount of weighings is not affected. Clearly, you should only have "extra" balls on one side of the scale (otherwise they cancel out) so these balls allow you to check three sets of potentially different cardinality, $a$, $b$ and $c$ where we "compare" $a$ and $b$.

For the $c>0$ case things are fine, since if we could compare $a$ and $b$ before we can after. Also with $c=0$, our comparison of $a-1$ and $b-1$ is also still possible as you need the same number of extra normal balls on the lighter side to keep things equal.

Answer 3

Due to the fact that we can elimiante at most 2/3s of the marble in any one step.

The general solution to this is that with $n$ peices of marble it takes $f(n)$ weighs given by:

$$ f(n) = Ceil[log_3(n)] $$

Where Ceil[] is the ceiling (round up) function

Since we know that $log_3(x)$ is an increasing function (for $x\ge 1$) we know that the $f(n)$ is increasing.