30 fake coins out of 99 coins

Question

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.)

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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 logical-deductions

- 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|~

Answer 8

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.