1
$\begingroup$

In the pebbles problem, you are given $n$ number of pebbles that has one of the $n$ weigh less. If you are given a balence that you can you $k$ times, what is the minimum amount of $k$?

Conjecture:$k=\big\lceil \log_3(n)\big\rceil$

Theory:We can split the pebbles into 3 groups. Then, we weigh 2 of the groups against each other on the balence. If they are equal, we are left with the remaining group of $\big\lceil\frac n3\big\rceil$, and if they are not, we are left with thethe group of $\big\lceil\frac n3\big\rceil$ on one of the sides of the scale. Then we keep repeating this process.

Example: We receive 27 pebbles. We put 9 on the scale's left, 9 on the right, and 9 on the ground. When we weigh the pebbles, we can find that the number of pebbles that might be lightweight is 9. Then we repeat the process, and we are left with 3. Again, and we find the lightweight pebble.

However, when we try with 28 pebbles, split into 9,9,10, and we weigh the 9's against each other and find that the lightweight pebble is in the 10 pile, we split the 10 into 3,3,4 and weigh the 3's. If they are equal, then the remaining one most be in the 4. Now we split the 4's into 1,1,2 and we weigh the 1's. If the lightweight one is left in the 2 pile, we need to use the balance 4 times.

I would like an algebraic proof of this concept.

$\endgroup$
1
$\begingroup$

You've proven there exists an algorithm for $k = \lceil \log_3(n)\rceil$, but still need to show that there isn't some better algorithm out there. Here's a hint: suppose you had an optimal weighing algorithm. Write down that algorithm as a tree, where each node is a partitioning of the pebbles into three sets, which has three children, one for each possible result of the weighing.

The algorithm can then distinguish between $l$ possible initial pebble states, where $l$ is the number of leaf nodes. You must have $l\geq n$ to always detect the special pebble. Now relate $l$ to the maximum depth $k$ of the tree.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.