Coin weighing puzzle

Question

I have 4000 coins, 2000 coins weighing 1 gram and 2000 coins weighing 2 grams. I cannot tell the difference between these coins. However, I have a weighing scale (like a digital one, not a balance scale) that is fixed to some unknown integer N. 1 < N < 6001

This means that whenever I weigh a group of coins on this scale, it will show me one of two results. The first result it will show me is '$<$N' if the coins together weigh less than N. The second result it will show me is '$\geq$N' if the coins together weight at least as much as N.

How can I prove that I can find a set of coins that weigh exactly N grams? Furthermore, how can I prove that I can find this set in at most 10000 weighings?

My approach so far has been to add one coin at a time to the scale until it finally flips from '<N' to '>=N' Now, we know that the group of coins on the scale weigh exactly N grams or N+1 grams. Let us label these coins on the scale $a_1$, $a_2$, $\dots$ $a_M$. So there are M coins on the scale.

Next, remove coin $a_1$. If the scale stays at "$\geq$N", then we are done. If instead it shows <N, then we put coin $a_1$ back on to the scale. Repeat this for coins $a_2$ until coin $a_M$. If at any point the scale ever shows "$\geq$N" after removing a coin, we are done.

However, let's say that the scale never shows "$\geq$N" after removing any one of the M coins on the scale. Now, we have two possibilities.

The first possibility is that the coins on the scale sum to N+1, and that all the coins being weighed weigh 2 grams. The second possibility is that the coins on the scale sum to N.

And this is where I got stuck so I'd really appreciate some help.

Answer 1

As Lourrran points out you can save a few weighings by doing a binary search to get to $N$ or $N+1$ instead of adding one coin at a time. You will get to $N$ with less than $20$ weighings.

As Brian Hopkins points out, if you have more than $2000$ coins on the balance when you get to $N$ or $N+1$ you are guaranteed to have a $1$ coin on the balance, so your technique of removing one coin will work to find $N$. This will take at most $2001$ weighings because you will pull at least one $1$ gram coin by then.

The remaining case is that you have less than $2000$ coins on the balance when you get to the $N$ or $N+1$ case. Take that many coins out of the ones that are left and weigh them. Play around to find $N$ or $N+1$ with this batch. If the numbers of coins that get you to $N, N+1$ differ, there are some $1$ gram coins in the larger group, so try that group one by one to find one or to find you are at exactly $N$. If the numbers do not differ and add to $2000$ or less you might have all $2$ gram coins in both batches. Make another batch from what is left and repeat. You will eventually use over $2000$ coins total, so there will be some $1$ gram coins in any batch you want if they are all the same size, or in the largest batch if they are not.

Answer 2

Here's the solution.

When you know that the total weight is $n$ or $n+1$ and that an $n+1$ means that all coins are $2$ grams, you completed $t$ weighings when adding coins ($t$ is defined to be the number of coins on the scale at this stage) and $\max(t,2001)$ weighings when testing the removal of coins (we can stop after removing the $2001$st coin to get at most $6001$). Mark the coins that you know make $n$ or $n+1$ with an $O$ (there are $t$ marked coins at this stage.)

If $t$ is $1,$ since $n$ can't be $1,$ we know we're done. In the other case, start by replacing each $O$ coin by a blank coin one at a time. If the weight gets below $n$ for the first time after a replacement, then we can go back to before that replacement to get a set of coins that weighs exactly $n.$ If the weight is still above $n$ after the first round of replacement (by after the round of replacement I mean after all the previously marked coins were replaced), then we can mark all the blank coins on the scale with an $X$ and repeat, marking the coins with an $X$ for each successive round. If the initial weight was $n+1,$ then all the coins marked with $O$ are $2$ grams. Therefore, if the initial weight was $N+1,$ in each round, only a single $1-$gram coin can be marked $X,$ since marking two or more $1-$gram coins $X$ would mean that the weight dropped to $n-1$ or lower, at which point we would find a set with weight $n$ instead of marking. Since there are more $1-$gram coins that are not marked $O$ than $2-$gram coins that are not marked $O$ (if the initial weight before this process was $n+1$), at one point, we must have more $1-$gram coins on the scale than $2-$ gram coins. At this point, there are at least two $1-$gram coins on the scale, so we are done. This takes at most $4000$ weighings to reach. Therefore, an upper bound on the maximum possible number of weighings with this method is $t + t + 4000$ which is bounded above by $8000.$ If this process doesn't terminate with less than $n$ on the scale, then the original coins marked $O$ weigh exactly $n.$ Therefore, it is possible in at most $8000$ weighings.