11
$\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.

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.

$\endgroup$
  • 1
    $\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
  • 1
    $\begingroup$ @Oray are we looking for the minimum number of coins we must weigh, or the minimum number of times we must weigh? $\endgroup$ – TrojanByAccident Jan 6 '17 at 23:39
  • 1
    $\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
6
$\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$
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
1
$\begingroup$

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

35

Step 1:

Put 1 coin besides the scales and put the other 98 on the left side.
Divide the given number by 98. The quotient gives the weight of a normal coin. The remainder (say R) tells us exactly about how many heavier and how many lighter coins there are.
If R is an odd number it means we put a fake coin besides the scales. Great, found one for sure after only 1 attempt. Let's call this (fact 1).
If R is even we differenciate between 3 cases. The remainder is positive, the remainder is negative and the remainder is 0.

Explanation of fact 1:

If all 30 fakes are heavier and we put them all on the left side then R=30
For each fake that is lighter instead R is 2 smaller. (-1 for not being heavier and another -1 for being lighter).
The only way to get an odd remainder is thus if we had put a fake coin besides the scales.

Case R is positive:

R gives us how many more heavier coins there are than lighter coins.
For example: If we have 16 heavier and 14 lighter fakes R = 2.
From this point on we can use the following simple strategy to find one of those heavier coins:
1. Split the pile into 2 and put those parts on separate sides of the scales.
Substract the expected weights from both sides and calculate the actual difference between both sides.
2. Discard the lightest pile. Go back to step 1 with the other until the diference is equal to the number of heavier fakes.
takes roughly 6 weighings tops. Exact number doesn't matter much as it's lower than the worst case below.

Case R is negative:

same as for positive but use -R instead and replace "heavier" with "lighter".

Case R=0 (worst case):

As far as I could tell it's impossible to split the pile in half in this case since you don't know if either side contains only reals or just an equal number of lighter and heavier coins.
Instead we're going to make a claim about 2 coins in each step.
In each step take 1 coin from the left pile and put it next to the scales. (see fact 1).
Take a second coin from the left pile and move it to the right pile.
Then calculate the new remainder.
If the remainder is odd see fact 1: we found a fake coin and put it next to the scales.
If the remainder is positive/negative we put a fake coin to the right side of the scale (found one! and done).
As long as the remainder is 0 we repeat these steps until we have 30 coins remaining in the left pile. At that point there are only fakes on the left pile.
This takes 35 weighings. (First weighing had 98 on left side, each next one reduces it by 2).

$\endgroup$
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$
  • 1
    $\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
  • 1
    $\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

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.