Using an old famous problem, it's obvious that by at most $\lceil \frac{n-1}{13} \rceil$ times using the balance, we can find the different bag. Any better upper bound?

Taking $1,2,\ldots,13$ coins from $13$ bags, they can be weighed since their weight is at most $7\cdot 13\cdot 10 = 910$ grams, so this fully solves the $13$ bags. When $n$ is small, for example the trivial case $n\leq 13$, this is clearly best. But for (very) large $n$, it is best to take $1,1,\ldots, 1$ coins from $100$ bags. This works much faster, until we reach a $999$ grams reading, meaning one of these bags is the one. Now these $100$ bags can be solved in $\lceil 99/13\rceil = 8$ weighings. This is clearly faster for large $n$. Can one find a common formula for small and large $n$? And there may be variations on this idea ...

I claim that for $n\ge 100$ by at most $\lceil \frac{n}{100} \rceil+3$ times of using the balance we can find the different bag. As mavropnevma pointed out, by using the balance at most $\lceil \frac{n}{100} \rceil$ times, we can find a group of at most $100$ bags for which the different bag is in it. WLOG suppose this number is exactly $100$. Now divide this $100$ bags into three groups of sizes $34,33$ and $33$. choose $1$ coin from each bag of first group, $2$ coins from each bag of second group and no coins from bags of the third group. Using the balance, we can find the group of size at most $34$ for which the bag is in it. Doing the same, we can find the group of size at most $12$ for which the bag is in it. Now using the $13$ bag case, we can easily find the different bag!

I think the best answer will be: For $1\le n \le 14$, $1$ time, For $15\le n \le 60$, $2$ times, For $61\le n \le 99$, $3$ times, For $n=100k+r\ge 100$, If $0\le r \le 60$, $k+2$ times, If $61\le r \le 99$, $k+3$ times.

goodar2006 wrote: I think the best answer will be: For $1\le n \le 14$, $1$ time, For $15\le n \le 60$, $2$ times, For $61\le n \le 99$, $3$ times, For $n=100k+r\ge 100$, If $0\le r \le 60$, $k+2$ times, If $61\le r \le 99$, $k+3$ times. i think your answers not correct! answer: $1\leq n\leqslant 14\Rightarrow 1$ $15\leq n\leqslant 60\Rightarrow 2$ $61\leq n\leqslant 140\Rightarrow 3$ $100k+40\leq n\leqslant 100k+140\Rightarrow k+3$