18
$\begingroup$

You are given 99 coins which consists of 30 fake ones. You also have a digital balance scale with perfect precision that shows how much difference between weighs you put on. For example, if you put 10 g on the left side and 20 g on the other side, it will show -10, otherwise +10.

You are asked to find a fake coin among given 99 coins:

  • You know that all genuine coins have the same weight but you do not know their weights.
  • You also know that every fake coin is heavier or lighter by 1 gram than any genuine coin.

EDIT: The intended question was to not allow a mix of heavier and lighter coins. Since all answers were based on this assumption, changing this requirement now would invalidate them all. I'll leave this question as is (and allow a mix) but don't know an optimal solution myself.

So, what is the minimum amount of weighing which guarantees to find any fake coin you are looking for? (The fake coin you are going to find might be heavier or lighter, it does not matter, you just need to find any fake one.)

Note: You may assume weights are positive integers, but it is not supposed to change the result.
You may also weigh one or more coins against nothing to get their total weight (originally asked and answered in comments.)

$\endgroup$
  • 2
    $\begingroup$ Yes, it matters. One thought I had was to weigh the whole lot. If the weights are natural I can determine in one weighing the weight of a good coin and the weight of a fake because the sum will be a multiple of $99$ plus or minus $30$. I don't know that is the best approach, but I want to know if it is available. $\endgroup$ – Ross Millikan Jan 6 '17 at 20:59
  • 3
    $\begingroup$ @RossMillikan Even so, 15 coins could be W-1, and 15 could be W+1, which would yield 99 W $\endgroup$ – Chris Cudmore Jan 6 '17 at 21:07
  • 1
    $\begingroup$ I had assumed all the fakes were the same. Thinking on it some more. $\endgroup$ – Ross Millikan Jan 6 '17 at 21:12
  • 4
    $\begingroup$ @Oray do you have a clever solution for this or did you come up with this puzzle on your own without a solution? The more I turn this around in my head, the less I can see how there could be any solution asking less than a number of tries above 60. The problem being that, since we have an even number of fakes, they could be half lighter, half heavier, and then any stack of coin we make of more than 2 coins could possibly also contain as much heavy than light fakes, meaning they'd never stand out as fake ones or real ones as long as we don't weigh them one by one... $\endgroup$ – Dorian Fusco Jan 19 '17 at 16:47
  • 1
    $\begingroup$ Note that OP in this comment answered "yes" to @Oriol's question, "can some fake be lighter and some fake be heavier?" - I think that locks in the question as originally interpreted by the older answers. In any case, changing a question after it's gotten answers is inappropriate—it can make those answers wrong, and adversely affect the reputation of those who answered. To ask a different question, create a new post and ask it there; the original question can then be linked back to if needed for reference. $\endgroup$ – Rubio May 4 at 6:16
7
$\begingroup$

THIS IS A PARTIAL ANSWER. It identifies a real coin within 9 weighs. I'm posting it here because I believe it covers concepts that could be useful in creating the optimal solution.

Here's the most important algorithm in my solution:

CLAIM: If we know that a group of $n$ coins has an odd number of reals, in one weighing we can identify a group of less than or equal to $(n/2)+1$ coins (I know that's not always an integer, hence less than or equal to), that also contains an odd number of reals.
PROOF: Let $2x$ be the largest even number less than or equal to $n/2$. Put $x$ coins on either side of the scale.
CASE 1: The scale reads an even amount. In this case, we KNOW that out of our $2x$ coins, we have an even number of fakes. This is easy to show by perturbation - imagine starting with $x$ real coins on each side, and changing a coin to a fake requires changing another coin to a fake to keep the scale reading even. So if there are an even number of odds in our $2x$ coins, there are an even number of reals. This means there are an ODD number of reals in the coins we didn't weigh, which is at most $(n/2)+1$.
CASE 2: The scale reads an odd amount. For similar reasoning to above, we have an ODD number of fakes in our $2x$ coins, and an ODD number of reals in our $2x$ coins. This amount is less than or equal to $n/2$.

So you can see that we can identify a MUCH smaller sample space with an odd number of real coins.

Even cooler to note is that this algorithm works with coin roles reversed.

However, we need to iron out some details.

If the number of coins with an odd number of reals, $n$, is 0 mod 4, then $x$ will be $n/4$. So our weighing, without a doubt, will lead to identifying a group of $n/2$ coins with an odd number of reals.
If the number of coins with an odd number of reals, $n$, is 1 mod 2 (i.e. 1 or 3 mod 4), then we KNOW we can split it into two groups that differ in size by only 1. One of these groups is even, in which case we set that to be $2x$. So, if $n$ is 1 mod 4, we know our weighing will lead to EITHER $(n+1)/2$ or $(n-1)/2$.
Last case is $n$ is 2 mod 4. $n=4z+2$. Set $x$ to be $z$. So we will either identify a group of size $2z$, or $2z+2$, i.e. $(n/2)+1$ or $(n/2)-1$.

Apply the important algorithm, and use that second paragraph to find out all possible cases.

START: 99 coins have odd no. of reals.
ONE WEIGH: We have identified a group of size 48 or 49 with odd no. of reals. If you identified 49, stop and skip to THE ANNOYING CASE.
TWO WEIGHS: Identified group of size 24 or 25 with odd no. of reals.
THREE WEIGHS: Found group of size 12 13 with odd reals.
FOUR WEIGHS: Found a group of size 6 7 with odd reals.
FIVE WEIGHS: Found a group of size (2 or 3 or 4) with odd reals.

The bolding will make sense later.

Alright, so now we need to do some sneaky stuff.

SIXTH WEIGH: Put ALL THE COINS on one side of the scale. If a real coin weighs $w$ grams, then we will get a number $99w+-$(offset by fakes). We know the offset of the fake coins is even, since there's an even number of fakes! So, we now KNOW the decimal residue of $99w$ mod 2, call it $r$.
$99w$ mod 2 = $r$.
$99(w+-1)$ mod 2 = $r+-99$.
99 is odd, so a 99 fake coins would have a different mod residue to $r$, which we have already identified from our weighing. (Note - i know that 99 fake coins do not necessarily have the same direction of wrong weighting, but the disposition is odd, anyway, making a different residue)

Now apply this knowledge:

NINE WEIGHS FINISH: If you identified a group of 2 coins, one is real and one is not. Just weigh one, see what its residue is MOD 2, multiply by 99, and if you get residue r, the other one is fake, and if you don't get residue r, it's fake, and you're done in seven weighs.
If you identified a group of 4 coins, weigh three of them one by one, and similar logic to above to determine if real or fake, and you're done in nine ways worst case.
You can't have identified 3 coins, because each bolded item in that list can only be reached by the bolded item above, and I said to stop if you identified 49. However, to identify a REAL coin, it doesn't matter if you keep going at 49 coins and get down to 3, at which you can identify a real in 8 weighs.

THE ANNOYING CASE is one in which identifying a real is easy by the same method, but identifying a fake suddenly becomes a lot more work. I'll leave off this partial here. I think that:

Residues, and parity of scale display

Are two important concepts that are fairly high powered. Hopefully someone has the insight to use these concepts in a more watertight fashion.

$\endgroup$
  • 3
    $\begingroup$ You can actually find a real coin in 2 steps. $\endgroup$ – Brandon_J Apr 25 at 22:51
7
$\begingroup$

I found a way to guarantee finding a fake coin after the following number of weighings:

35

EDIT: Explanation modified again to also allow fractional weight of a real coin. The algorithm itself remains the same.

First some variables:

$w_r$ = the weight of a real coin
$W_{a|b}$ = number shown on the scales with "a" coins on left side and "b" coins on right side.
$F^+_i$ = number of heavier fakes on left side + lighter fakes on right side on the $i^{th}$ weighing.
$F^-_i$ = same as $F^+_i$ but with lighter and heavier reversed.
These last 2 show how many grams the scales show more/fewer because of the fake coins.

This means at each weighing we can write the result as

$W_{a|b} = (a-b)w_r + F_i^+ - F_i^-$

Algorithm

Weighing 1

Put 1 coin besides the scales and put the remaining 98 coins on the left side on scales. Result:
$W_{98|0} = 98w_r + F_1^+ - F_1^-$

Before each new weighing we do 2 things.

1) Take 1 coin away from the left side.
This will reduce either $F_i^+$ or $F_i^-$ by 1 if it's a fake coin.

2) Move 1 coin from left side to right side.
Moving a heavier fake coin will move 1 from $F_i^+$ to $F_i^-$ and the other way around for a lighter fake coin.

Weighing 2

$W_{96|1} = 95w_r + F_2^+ - F_2^-$

Notice that if we had known $w_r$ exactly we would also know if the coins handled in this step were real coins:

Moving a fake coin to the right side of the scales will change the result by 2g. So if the result changed by an odd number we know the coin we put besides the scales was a fake.
If the result is off by an even amount we know the coin we moved has to be a fake.

Can we guess $w_r$ based on the results?

Scenario 1: We have $f_a$ heavier and $30-f_a$ lighter fakes
$W_{98|0}=98w_1 -30 + 2f_a$
$W_{96|1}=95w_1 -30 + 2f_a$
Scenario 2: We have $f_b$ heavier and $30-f_b$ lighter fakes. We put a heavier/lighter fake beside the scales
$W_{98|0}=98w_2 -30 + 2f_b$
$W_{96|1}=95w_2 -30 + 2f_b \pm 1$

Combining those equations gives $f_a=f_b\pm\frac{98}{6}$.
Since both $f_a$ and $f_b$ have to be integers there are no solutions.
It does have an integer solution if we both put a heavier/lighter coin besides the scales AND move one to the other side. In that case $f_a=f_b\pm49$.
After the next weighing this gets resolved though, since it's impossible to balance that new equation.
So after 3 weighings we can figure out the exact weight of an actual coin and thus whether or not our candidate coins in each weighing were fakes or not.

Final weighing

Worst case scenario we didn't find any fakes in the first 34 weighings. At weighing 35 there's exactly 30 coins left on the left side of the scales. Since all the other coins were real we know that all 30 of those must be fakes.

Conclusion

Even for fractional weights for the real coins it's possible to find a fake one in 35 weighings. It only takes at least 3 weighings before we are sure about any of the previous candidate coins.

$\endgroup$
  • 1
    $\begingroup$ I think that this is correct. $\endgroup$ – Brandon_J Apr 26 at 13:02
4
$\begingroup$

Here's a shot:

Maximum required weighings with this solution:

51

Step one:

Weigh all 99 coins against nothing. Divide that number by 99. It is guaranteed that the weight of the legitimate coins is within 30/99 of a gram of the original weight. Total weighings: 1

Step two:

Weigh a single coin against nothing. If that coin weighs outside of that 30/99 of a gram, then you are done and you have a fake coin. Otherwise, you have identified a legitimate coin, and that will be useful later. Also, it will be trivial to determine the exact number of lighter and heavier fake coins. Total weighings: 2

Step 3A:

We still have 98 coins left. If we have determined that the number of light fake coins is unequal to the number of heavy fake coins (if not, go to 3B), then we can repeatedly weigh three coins against nothing until we run into a weighing that doesn’t equal legitimate coin weight*3 – and it’s guaranteed that we will reach that eventually OR come down to two fake, equivalent-weight coins, because we don’t have equal numbers of fake heavy and fake light coins. After reaching that point, it will only take one additional weighing to determine which of these coins is fake – and none if we’ve already gone through 96 coins. Regardless, we need at worst 34 additional weighings – although the exact number doesn’t really matter because 3B is the worst case scenario.

Step 3B:

Well, if 3A won’t work, this will, and this is the worst-case scenario. The problem is if we weigh more than one coin at a time on a single side, then we could have a heavy fake and a light fake balancing each other out and acting like two legit coins. Thus, we have to take the coins two by two - weigh one coin of each arbitrary pair against the other until we find a mismatch – and it will only take one more weighing to locate the fake coin. However, if we last through 48 weighings without finding a mismatch, we know that both of the 49th pair coins are fake, so the most additional weighing that this step would add is 48+1 = 49 for a grand total of 51 weighings.

I saw that @Imus has a solution with 35 weighings, and it's correct. I'll leave mine here for posterity.

$\endgroup$
  • $\begingroup$ In step 3B, the 49th weighing is not required, since you already know that the both coins of a remaining pair are fake (and so, you are identified even 2 fake coins, you don't need to determine which of them is heavier and which is lighter than the normal coin) $\endgroup$ – trolley813 Apr 26 at 10:23
  • $\begingroup$ @trolley813 not necessarily. If we find a discrepancy on trial 48 (weighing number 50) then we need another weighing to determine which one is the fake one. $\endgroup$ – Brandon_J Apr 26 at 12:43
  • 1
    $\begingroup$ Took a couple of edits to get my answer of 35 right but I think it's pretty solid now. No checkmark because OP doesn't know the answer to the question as it is posted here (mistake in formulation). Still a +1 for the clever reduction by 3 in 2 weighings. $\endgroup$ – Imus May 7 at 14:27
  • $\begingroup$ @Imus edited the end of my answer. $\endgroup$ – Brandon_J May 7 at 14:51
2
$\begingroup$

Via Linear Search

One thing I noticed is the scale will NOT tell you weight of any single coin. It will only tell you the difference between two coins. Additionally, I read the question to indicate that number of 30 fakes is known in advance, and that we only need to find ONE fake, not sort out all of them. Applying these limitations changes the procedure somewhat.

To get my coins, I would choose one coin at random as a control, and then start weighing, where each coin is sorted into possible results of -2, -1, even, +1, +2 from the control (only three of these groups will have any coins, depending on where I start. From here, there are a number of possible outcomes:

  1. I choose a fake coin as the control. In this case, I only have to weigh until I find either a +2 or -2. This could happen on my first attempt! I might only have to weigh one set of coins to get a result. However, in a worst-case scenario I might compare with as many as 30 real coins first. Additionally, if all the fake coins by chance happen to also have the same weight I might compare with as many as 29 other fake coins, for a total of 59 attempts before I find my result, meaning in the worst case scenario I might still need 60 attempts.

  2. I happened to choose a real coin as the control. In this case, I might need to compare it with as many as 30 other real coins, but as soon as that happens I know I have a real coin as the control, and any difference at all will be fake. Additionally, as soon as I've seen both a -1 and a +1 I know I'm working with a real coin as a control, and any difference must be fake. This could happen as quickly as 2 attempts, but the worst case is to compare with 29 other evens plus all 30 of the fake coins, if all but one of the coins are the same and I don't find that one until the last possible moment. In this case, I might make 60 attempts before knowing what is what. The final possibility is to weigh all 68 remaining real coins before even putting a fake on the scale.

So with this procedure, the answer is 68.

Via Binary Search

I don't have this completely worked out yet, but I suspect there is a much faster procedure this way.

Divide the coins up as evenly as possible into groups of 49 and 50, and weigh them. Note the difference. The exact difference number doesn't matter (it might even the same!), but the change in this number will matter as we continue. Remove 24 coins from each pile (48 total), and re-check the weights. If the weights are different, we know the removed coins have at least one fake coin, and we can start again with the coin supply reduced by half. Unfortunately, it doesn't prove anything if the weights are the same, because you may have just removed the same proportion of real and fake coins, and this becomes increasingly likely as the number of coins in the pool decreases. Again, I don't have that part worked out yet, but I suspect an algorithm is possible that will get this down to something approaching a binary search, which might naturally produce answer as small as 7 or 8 plus whatever additional we need to do to solve problem of not selecting a fake coin on the first attempt.

$\endgroup$
  • $\begingroup$ I actually believe your linear approach is the best one and there are no better answers. The binary search cannot always work. For example, at one step you remove 24 coins from both stacks, it's possible you removed 10 light false coin and 10 heavy false coin in one and 5 light false / 5 heavy false coin in the second, leaving you unable to see a change in any of the two stacks $\endgroup$ – Dorian Fusco Jan 19 '17 at 15:31
  • $\begingroup$ I agree with @DorianFusco that the binary aproach is unlikely to work. I do think I have found a way to do better than the 68 assuming it's allowed to put 0 coins on one side of the scales. Your linear aproach did give me the idea to at least try my solution in the first place! $\endgroup$ – Imus Dec 4 '18 at 14:26
2
$\begingroup$

This is more difficult than it looks, but I think we can reduce the answer from 51 weighings to:

48

First, we have to borrow a step from an existing solution

and find the weight W of a good coin g (thanks @Brandon_J). Weigh all 99 coins against nothing to get the total weight T. Since T is required to fall between 99W - 30 and 99W + 30, it follows that W must lie in the range T/99 -+ 30/99. Now weigh one coin and accept as good if the value W falls within that range. If not, it's fake and we can stop there. Two weighings.

In practice, as we are looking for the worst case, we can expect the 'annoying situation' of

W = T/99 exactly; in other words we have 15 lighter fakes and 15 heavier. I'll refer to those as f- and f+. This is the most difficult situation as it allows the fakes to stick together in pairs f-f+, and to look exactly like two good coins gg unless they are forced to split up.

Putting the known coin aside we have 98 remaining which we'll deal with in groups.

Take any three coins and weigh them against nothing. If the scales read anything other than 3Wthen there must be at least one fake, which is trivial to identify. If it reads exactly 3W, there are two possible options: ggg and gf-f+.

We can distinguish these two by

weighing any one coin of the group against any other. A value of zero means that we have ggg; anything else means we've found a fake. So, we've dealt with three unknown coins with a further two weighings.

Now, we can expect that the fakes are going avoid the scales for as long as possible, which means that

we will find ggg a total of 22 times until there only two unidentified good coins left out of the original 68. The next group is forced to include at least one of the 30 fakes, for example ggf+ or gf-f+ and we can definitely identify it with a further two weighings.

Final calculation:

2 + 2*[68/3] + 2 = 48

Now you might think that we could skip the first step and

infer that if we get the same result 22 times that must be 3W. But that's not the case as we could then have the situation (if all 30 fakes were f+) of the three coins being ggf+ each time, with the second weighing always being gg. That could be repeated more than 22 times.

$\endgroup$
  • $\begingroup$ Why do you suddenly go from 98 to 68 coins? How can you get your 98 coins left in 22 groups of 3 coins? $\endgroup$ – Daniel Duque Apr 28 at 22:44
  • $\begingroup$ Additionally, why is the last group forced to have at least one fake coin? You could miss all your coins in pairs with the first tests, and have only real coins at the end. $\endgroup$ – Daniel Duque Apr 28 at 22:47
  • $\begingroup$ The figure of 68 comes from the fact that, of the 98 coins we are looking at, we know from the question that 30 are fakes. We are using up three good coins at a time, so after 22 attempts - 66 good coins - we are guaranteed to find a fake in the very next group. The two weighings are designed to ensure that no fakes can slip through unseen. Remember that we're asked to consider the worst case scenario here. I've edited the answer slightly to explain where the 68 comes from. $\endgroup$ – MichaelMaggs Apr 29 at 2:52
  • $\begingroup$ According to what you just said then you are not using just 22 measurements to ensure that the first 68 coins are real. You have 22 groups of three coins, and you are using 3 measurements per group i.e. 66 measurements, same as 1 measuremen per coin. Otherwise fake coins can go through undected and it wont be guaranteed to find a fake coin after the first 68 coins $\endgroup$ – Daniel Duque Apr 29 at 8:56
  • $\begingroup$ No, just two weighings per group of three. The first weighs all three against nothing. The second any one of the three against any other of the three. Only two weighings are needed to ensure that the current group is ggg. I've tried to be quite clear in my answer, but if there's any particular language that's ambiguous, please say. $\endgroup$ – MichaelMaggs Apr 29 at 12:00
1
$\begingroup$

9 Weighings

(Note: this answer relates to the version of the question at this link, where all fake coins are of uniform weight 1 unit away from the genuine coins.)

This answer assumes you can put zero coins on the right pan and get a readout of the actual weight of the coins on the left pan.

You can determine the weight of a fake coin in 2 weighings.

Let $f$ and $g$ be the weight of a fake coin and a genuine coin, respectively.

  1. Put any coin on the left and nothing on the right. Record the weight $w$.
  2. Put all 99 coins on the left and nothing on the right. Record the weight $W$.

You have 30 fake coins and 69 genuine coins. So:

  • if $W = 99w \pm 30$ then the excess weight comes from the fakes, so $f=w \pm 1, g=w$; likewise,
  • if $W = 99W \pm 69$ then $f=w, g=w \pm 1$.

Now, you want to find any fake coin. I take this to mean that you want to identify one of the 30 fake coins in the pile of 99 coins, and it doesn't matter which fake coin you identify. Assume $f>g$ (reverse the logic if $f<g$).

Keep the right pan empty.

Put a pile of 50 coins in the left pan. The weight will be $50g + x$, where $x$ is the number of fake coins in the pan. So the other pile has $30-x$ fake coins. Choose whichever pile has the greater number of fake coins, disregard the rest, and continue.

At each iteration, place half the remaining coins on the left pan and nothing on the right. Round up or down (it doesn't matter which) to get an integer number of coins.

In the worst case, the fake coins are always split evenly between your two piles. You will weigh 50 coins (including 15 fakes), then 25 (8 fakes), 13 (4 fakes), 7 (2 fakes), 4 (1 fake), 2 (1 fake), 1 (1 fake).

The last weighing is needed because you don't know which of the 2 from the previous weighing was the fake. At the last weighing, you start with 2 coins and weigh one of them. If the weight of the weighed coin is $f$, that's the fake. If it is $g$, the other coin is fake.

That's 7 weighings. Add the initial 2 (which determined $f$ and $g$) to get 9 weighings altogether.

$\endgroup$
  • 1
    $\begingroup$ You are assuming that all fake coins have the same mass. That case is rather trivial, the real complication comes when you don't know how many coins are heavier and how many are lighter than the real coins $\endgroup$ – Daniel Duque Apr 29 at 12:37
  • $\begingroup$ @Daniel I might have misread the question, but the OP’s second dot point implies this. Fake coins are (real coin weight $\pm 1$), and all the same sign. So fake coins are all the same weight. $\endgroup$ – Lawrence Apr 29 at 13:16
  • 1
    $\begingroup$ My bad, that part was only edited 6 hours ago. The original question (1 year ago until 6 hours ago) was different, that's the reason all other answers have such large numbers as answers. $\endgroup$ – Daniel Duque Apr 29 at 15:44
  • $\begingroup$ That edit to the question was after I cleared this confusion up with the OP. The edit invalidated all answers on this 2 year old question which isn't really nice :). It's edited again and OP said he might post his intended question later in a different post. I suggest you copy paste your solution to that one instead. $\endgroup$ – Imus Apr 29 at 17:48
  • $\begingroup$ The original comments actually rule out the recent (now rolled back) edit, so unfortunately this answer is to a different question. You might want to put a note on it to that effect so people don't start downvoting it. (Or remove it and hope Oray does in fact post the alternate form of the question, so you can post this answer on that question.) $\endgroup$ – Rubio May 4 at 6:27
0
$\begingroup$

Disclaimer: This answer was based on my original assumption that you could only weigh one coin at a time.

Short Answer

Only

$70$ out of the $99$ coins are needed to $\underline{guarantee}$ that you find a fake coin.
If going by times weighed, you only need to weigh $41$ times to guarantee it.

Long Answer

Let's start with what we know.

- You have $99$ total coins.
- $30$ of these are fake.
- This leaves $69$ that are real.

Also, because we know that:

all genuine coins have the same weight

and

every fake coin is heavier or lighter by 1 gram than any genuine coin

Let's assume that:

Every genuine coin is $10$g,

and so:

Every fake coin is either $9$g or $11$g

Now, we've got some useful numbers.

- There are a total of $69$ real coins
- Each real coin has a(n assumed) weight of $10$g (the total weight is irrelevant).
- There are a total of $30$ fake coins.
- We don't know the exact (even assumed) weight of every fake coin, but each is either $9$g or $11$g

Almost done, let's use some $Ma+h$ and s

- First, think about this. You're trying to get a fake one. This means you must weigh at least the number of genuine coins there are, and then one more.
- Since there are $69$ real coins, and $69+1=70$, you must weigh at least $70$ coins. however, it doesn't stop there.
- As we know for sure that there are, at a minimum, $40$($70-30$(which is the maximum number of fakes)) real coins, and that this number is the greater number, we can simply weigh all of the coins.
- After we weigh them, we count how many were the same weight. Whichever weight showed up the most often (which we are using as $10$), those are the real coins. Anything that differed from that is a fake coin.

Last thing! Here, I'll explain how to properly weigh the coins. Doing it this way will also lead you to the results.

$1.$ Take the 70 coins, and pick any of them to start.
$2.$ Place the coin on the left side of the scale and the second coin on the right. record the amount.
If it's negative, this means that it's either real or the lower fake. Conversely, if it's positive, this means that it's either real, or the higher fake. Regardless of the sign, you need to record the amount, including the sign. If it's $0$, you just record it and move on. There's nothing you can infer with that result at this point. Repeat Step 2 until one of the following: You get two different negative values, and one positive; You get two positives and a negative; You get at least $41$ coins in. Getting $41$ coins in insures that you will have at least one fake coin in your results. After you have achieved one of these three, move on to step 3.
$3.$ Now, analyze your results. ~|Decision tree coming soon|~

$\endgroup$
  • 2
    $\begingroup$ I'm trying to understand how you found 41, but -if I understood you correctly-, in your "Almost done" spoiler, on the second dash, you just throw away 29 coins, thinking you'd still have at least a fake one, right? But then you calculate the minimum of remaining real coins, wich is 40, but shouldn't you search for the maximum number of real coin left, as this is the worst case scenario? $\endgroup$ – Dorian Fusco Jan 19 '17 at 15:42
  • $\begingroup$ @DorianFusco in other cases, maybe. however, the worst case scenario is actually with the largest number of fakes, because then it is harder to find one fake. $\endgroup$ – TrojanByAccident Jan 19 '17 at 16:44
  • 2
    $\begingroup$ How so? Step 1, you throw 29 coins, let's say you threw 29 fake coins, you have 70 coins left. You then put a single coin on one side of the scale, say a real coin and you move on to step 2. In step 2, having the worst of luck, you pick all 68 other real coins before drawing the remaining fake coins. You just weighted 69 times before finding the fake coin, didn't you? 41 coins didn't ensure you to get at least one fake coin, because your worst case scenario wasn't to throw away 0 fakes at step 1, but to throw 29 of them. $\endgroup$ – Dorian Fusco Jan 19 '17 at 17:41
  • $\begingroup$ @DorianFusco I'm not sure what you mean. I'm probably going to update with a better solution at some point, though. $\endgroup$ – TrojanByAccident Jan 19 '17 at 18:18
0
$\begingroup$

9 weighings except for the annoying case, which takes $50$ weighings.

To find the weight $g$ of a genuine coin in 2 weighings:

  1. Weigh 1 coin (say $w$).
  2. Weigh all coins (say $W$).

If the 1 coin was genuine, we would have $99w - 30 \leq W \leq 99w + 30$. Otherwise, we have $99(w \pm 1) - 30 \leq W \leq 99(w \pm 1) + 30$, where the $\pm$ on both sides are either both $+$ or both $-$.

The ranges for all 3 cases (first coin is $g$ or $g+1$ or $g-1$) don't overlap, so we can work out $g$ from two weighings, and we also know whether the first coin is good, heavy, or light.

In addition, because the weight $W$ with $x$ light coins and $30-x$ heavy coins is different for each $x$, we also know how many light and heavy coins there are.

If we don't have the same number of light and heavy coins ($x \neq 15$), then we can do a binary search by weighing half the remaining coins each time (if we have an odd number, it doesn't matter if we round up or round down). Say we weigh $k_i$ coins at round $i$ to get $W_i$. If $W_i = k_i g$ (expected weight of genuine coins), discard the weighed coins and go to the next round with the unweighed coins. Otherwise, the weighed coins go into the next round. Even if some heavy and light coins pair up, there will be at least one left over that can't pair up. This gives a total of $\lceil 2 + \log_2(99) \rceil = 9$ weighings.

If $x = 15$, leave the known genuine coin aside and weigh the remaining 98 1-vs-1, looking for a nonzero difference. In the worst case, you pick like pairs all the way until the last pair. The last pair will consist of 1 light and 1 heavy, so that doesn’t need to be weighed. Total: $2+48 = 50$ weighings.

$\endgroup$
  • $\begingroup$ Mine does the annoying case in 48, unless you've found a flaw in it. $\endgroup$ – MichaelMaggs May 4 at 16:38
  • $\begingroup$ @MichaelMaggs Thanks for the note. I’ve improved the handling of the annoying case to max 30 with a triple-weighing followed by a binary search. My triple-weighing is 2-vs-1, but on reflection probably gives exactly the same amount of information as your 3-vs-0. $\endgroup$ – Lawrence May 5 at 0:25
  • $\begingroup$ There is a flaw in your argument. When you select 69 coins assuming there will be at least one fake, there can actually be more there, all 30 even. So, if you are unlucky and get all 30 fakes in the first 69 you choose, and then when you weigh 2 against 1, it can happen that the 2 on one side are always the heavy/light pair that weighs exactly like 2 regular coins, so you will not get any information in your 23 weighings, so you won't find any fake coins and your plan fails. $\endgroup$ – Amorydai May 5 at 3:02
  • $\begingroup$ @Amorydai You’re right. I’ve reverted to the pairwise weighings for now. $\endgroup$ – Lawrence May 5 at 14:40
  • $\begingroup$ I may have missed something, but surely in your 2 vs 2 weighings you can't guarantee to end up with fake-fake or real-real pairs, can you, even if the weights are the same? You could be weighing gf+ vs gf+ orgf- vs gf-. $\endgroup$ – MichaelMaggs May 5 at 15:31

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.