Minimum Number of Expected Weighings

Question

We all know the riddle where given $9$ coins, all being of equal weight except for one, the counterfeit, you have to show that the counterfeit coin can always be found in two weighings. I wanted to generalize the problem and find the minimum number of weighings that guarantees that you find a counterfeit coin from $n$ coins and got that it was $\lceil \log_3 n\rceil$. I was wondering what would the optimal strategy be for minimizing the expected number of weighings instead. My approach so far was this.

Let $X(n)$ be the random variable that gives the number of weighings used using the optimal strategy. Then the first weighing splits the coins into three groups of sizes $j$, $j$, and $k$. Then if the coin is in the first two groups, $X(n) = X(j) + 1$. Else, $X(n) = 1 + X(k)$. So $$E(X(n)) = 2(j/n)E(X(j)) + (1-2j/n)E(X(n-2j)) + 1$$ where $E(X(1)) = 0$ and $E(X(2)) = 1$.

I kind of got stumped after this. I wasn't sure what you could do from here to find an optimal strategy. In the original version of the problem, I solved it by getting an intuition for what the optimal strategy is and then proving that it's optimal using induction. Here though I'm not really sure if there is a pattern in where the split occurs or even if there's an explicit formula for the expected number of weighings using the optimal strategy.

Edit: (8/27/23) I made a python script for finding the expected number of weighings using the optimal strategy:

import math

import matplotlib.pyplot as plt

def expect(n):

    expectation = [0, 1]

    for i in range(2, n + 1):

        mini = float("inf")

        for j in range(1, i//2 + 1):

            mini = min((2*j/i)*expectation[j - 1] + (1-2*j/i)*expectation[i - 2*j - 1] + 1, mini)

        expectation.append(mini)

    return expectation[-1]



numCoins = list(range(1, 1000, 10))

expectations = [expect(i) for i in numCoins]

plt.scatter(numCoins, expectations)

plt.plot(numCoins, [math.ceil(math.log(i)/math.log(3)) for i in numCoins])

plt.xlabel("Number of Coins")
plt.ylabel("Average Number of Weighings")
plt.show()

And here's a scatter plot of the average minimum of weighings against the number of coins with the solid line being the number of weighings needed to guarantee that you find the counterfeit coin.

Answer 1

As I understood the question, it remains to solve the recurrence $$E(X(n)) =\min\{ 2(j/n)E(X(j)) + (1-2j/n)E(X(n-2j))\} + 1$$ with the initial conditions $E(X(1)) = 0$ and $E(X(2)) = 1$.

Put $f(0)=0$ and for each natural $n$ put $f(n)=nE(X(n))$. Then we have $f(1)=0$ and $$f(n) =\min\{ 2f(j) + f(n-2j):j=1,\dots, \lfloor n/2\rfloor\} + n.$$ Thus $\{f(n)\}=\{0,0,2,3,6,8,12,13,16,18,22,25,30,32,36,39,\dots\}$. This sequence is not in OEIS, so feel free to submit it to OEIS. I wrote a program to calculate the sequence $\{f(n)\}$ for natural $n\le 16000$. It suggests that for each natural $n$ we have $E(X(n))-\log_3 n\ge 0$ with the equality attained exactly when $n$ is a power of $3$. Below is the graph of the function $E(X(n))-\log_3 n$ in the logarithmic scale with respect to $n$, which seems to be tending to the regular oscillating pattern.