3
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Oops, I misunderstood the question when I edited. $\endgroup$
    – mathlander
    Jan 16, 2023 at 0:06
  • 1
    $\begingroup$ No problem, that is fine. $\endgroup$ Jan 16, 2023 at 0:09
  • 1
    $\begingroup$ If there are more than 2000 coins on the scale when the flip to "$\ge N$" occurs, then you know the weight is $N$: at least one coin weighs 1 gram and the first possibility you describe is impossible, since there are too many coins to all weigh 2 grams. $\endgroup$ Jan 16, 2023 at 0:18
  • 2
    $\begingroup$ You say you add 1 piece at each new test. You may consume a lot of tests, for very small benefice. 1st test, you should start with 2000 coins. 2nd test : 1000 or 3000 coins, depending of the previous result. 3rd test : 500 or 1500 or 2500 or 3500, depending of previous result. Each new step, you divide the gap by 2 (dichotomy). At each step, you need to clearly identify the coins that were in previous test, and the pieces that you add/remove. $\endgroup$
    – Lourrran
    Jan 16, 2023 at 0:19
  • $\begingroup$ Hi Brian thanks for the feedback. However, I don't think the first possibility is impossible because what if N was 99 and I added 50 coins that weigh 2 grams each. In that case, we are dealing with the first possibility. $\endgroup$ Jan 16, 2023 at 0:21

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ What if the first batch has 1900 coins, all of which are 2s? Then we cannot make any other piles out of the remaining 2100 coins which even come close to a sum of around 3800 $\endgroup$ Jan 16, 2023 at 0:50
  • $\begingroup$ Then you know the second pile has some $1$s in it because the $2100$ coins sum to less than $N$. We don't know that the first batch is all $2$s because we didn't go looking. Add coins from the first pile to find $N,N+1$ and make all the coins you pull off come from the $2100$ $\endgroup$ Jan 16, 2023 at 0:51
  • $\begingroup$ Suppose $N$ is 3799 and suppose our first pile somehow has all 2s. We know that the second pile has 2100 coins and some of which are 1s, but how would we identify which of these coins are 1s? I can certainly find which are 1s by bruteforcing, but that would take too many weights. $\endgroup$ Jan 16, 2023 at 0:55
  • 1
    $\begingroup$ Our second pile will then have $2000\ 1$ gram coins and $100\ 2$ gram coins, totaling $2200$ grams. We will add $800$ coins from the first pile to get to $N+1$. Now do your removing trick, removing only coins that started in the second pile. You will find a $1$ in short order. We won't know that the first pile was all $2$s-it could have some $1$s in it and have $N$ be lower. Just the fact that the $2100$ coins weigh less than $N$ says there are some $1$s among them. $\endgroup$ Jan 16, 2023 at 1:00
0
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ "then we can mark all the blank coins on the scale with an X and repeat", wouldn't there only be one blank coin on the scale to mark because we are replacing them one at a time? or are we replacing multiple at a time? $\endgroup$ Jan 16, 2023 at 1:29
  • $\begingroup$ I edited to clarify the meaning. $\endgroup$
    – mathlander
    Jan 16, 2023 at 1:30
  • $\begingroup$ After the first round of replacement, if the weight goes under n, how do you know that the original set of coins weighed exactly n? $\endgroup$ Jan 16, 2023 at 1:35
  • $\begingroup$ We just backtrack one step. We don't go all the way back to the original. $\endgroup$
    – mathlander
    Jan 16, 2023 at 1:36
  • $\begingroup$ Wait so we are just replacing one coin at a time right? $\endgroup$ Jan 16, 2023 at 1:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .