Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose you have 100 coins. 96 of them are heavy and 4 of them are light. Nothing is known regarding the proportion of their weights. You want to find at least one genuine (heavy) coin. You are allowed to use a weight balance twice. How do you find it?

Assumptions:

Heavy coins all have the same weight; same for the light coins.

The weight balance compares the weight of two sides on the balance instead of giving numerical measurement of weights.

share|improve this question
6  
As we keep telling you: Please indicate the source of your problems! Despite all the discussion about your behaviour you continue to do the same thing. It's ok if you don't know the original source, just say where you got it. (In this case, this problem is from the 2010 Euler math Olympiad in Russia given to eighth graders. Ten students solved it during the competition.) –  ShreevatsaR Aug 31 '10 at 18:51
    
Is it true that in the worst case every coin must be weighed? –  Dan Brumleve Sep 1 '10 at 0:41
    
@Dan: Obviously not. E.g., any set of five coins will contain a heavy one. –  Christopher Creutzig Sep 1 '10 at 7:52
2  
@ShreevatsaR: As, i keep telling you again and again, its not always possible to indicate the source, and i honestly didn't know that it was a part of the Euler OLympiad question! –  anonymous Sep 1 '10 at 14:07
5  
@Chandru1: even if the source is "I heard it from a friend", that is useful information, because that makes it less likely to be correct than a source of the form "it appears in book X" or "is from olympiad Y". If the problem is from a less reliable source, math.SE users have an interest in knowing that when determining whether to spend time trying to answer the question. See my answer, especially item 3. It is easy to indicate your source whether or not that is the ultimate or original source. –  T.. Sep 2 '10 at 0:54
show 3 more comments

6 Answers

up vote 5 down vote accepted

I think this works.

Divide the coins into three groups: $A$ with $33$ coins, $B$ with $33$ coins and $C$ with $34$ coins.

Weigh $A$ and $B$ against each other.

Now if $A$ is heavier than $B$, then $A$ cannot have two or more light coins, as in that case, $A$ would be lighter (or equal to $B$). Now split $A$ into groups of $16$ plus one odd coin. Weigh the groups of $16$ against each other. If they are the same, then any of those coins is heavy. If not, then any of the heavier 16 coins is heavy.

Consider the case when $A$ and $B$ are equal.

The possibilities for $A$, $B$ and $C$ are:


+-----------+------------+-----------+
|  A        |   B        |  C        |
+-----------+------------+-----------+
|  33H      |  33H       |  30H + 4L |
|           |            |           |
|  32H + L  |  32H + L   |  32H + 2L |
|           |            |           |
|  31H + 2L |  31H + 2L  |  34H      |
+-----------+------------+-----------+

Now move one coin from $A$ to $B$ (call the resulting set $B'$) and weigh it against $C$.

If $B' > C$, then the coin you moved from $A$ is a heavy coin.

If $B' = C$, then the coin you moved from $A$ is a light coin and the remaining coins in $A$ are heavy.

If $B' < C$, then all the coins in $C$ are heavy.

share|improve this answer
    
The solution by the original proposer (Shapovalov) was the same. See "solutions of the problems of the final phase" at translate.google.com/… –  T.. Aug 31 '10 at 19:32
    
@T..: Interesting! So that guarantees that it is correct :-) –  Aryabhata Aug 31 '10 at 20:47
1  
[INCREASE bayesian-confidence; DEMOTE proof-verification-priority] –  T.. Sep 2 '10 at 1:05
add comment

To avoid wasting readers' time when posting puzzles, it is useful (and will improve the upvote/downvote ratio) to provide:

  1. an indication of the difficulty level. Was this puzzle in a math-is-fun book for children, or is it a generalization of a problem from the final round of a national olympiad? Having schoolchildren attempt a question that (they were not told) is the $n=100$ specialization of a combinatorial lemma from a research paper, is a waste of time. Having mathematicians spend time on (what might look like) a coin weighing puzzle from the literature, but is really an easy task the high school students could solve with some patience, is a waste of resources.

  2. the source, if known. This helps those who want to evaluate the difficulty before taking time to attempt a solution, or who would like to look up hints or answers.

  3. indicators of whether the problem is correct or solvable as stated. Problems from a book, a competition or a journal are likelier to be correct and unambiguously formulated. Questions invented, circulated and (believed to be) solved among friends or students are more likely to have pitfalls that were missed in setting or solving the problem.

  4. clear definitions. In this case, coin weighing problems involve at least two very different interpretations of "use a weight balance". Weighing can mean comparison or numerical measurement and what is possible is completely different in those settings. Not specifying which is meant can waste the time of users who try to solve the problem in the wrong interpretation.

share|improve this answer
8  
This isn't an answer but it's too verbose to be a comment. The best option to present this type of information is to pose it to meta for discussion and reference. –  Robert Cartaino Aug 31 '10 at 17:54
    
note to the downvoter: see related discussion at math.stackexchange.com/questions/2632/… and on the meta. –  T.. Aug 31 '10 at 17:56
2  
@Robert: the points raised in this answer have manifested quite precisely in this thread: (1) the question did come from the final stage of a national olympiad, where it was an unusually difficult problem (all others were solved by many competitors); (2) solutions of the question are online and can be found knowing the source; (3) not disclosing the source led to a math.SE user taking the time to reinvent the official solution; (4) the question was ultimately revised to take into account the unclear definition of "weighing". –  T.. Aug 31 '10 at 19:46
1  
Yeah, this is a general comment rather than an answer, and ideally should not be here, but things aren't ideal here… I guess one wishes to upvote this out of frustration with the history of the user posing such questions. :-) –  ShreevatsaR Aug 31 '10 at 21:34
add comment

If you pay me 95 of the coins in advance I'll show you how ;-).

share|improve this answer
    
@whuber: You didn't use the weight balance, twice :) –  anonymous Aug 31 '10 at 17:32
3  
What's the down vote for? This answer is a strong hint intended not to spoil an easy puzzle. (If you remove 95 coins you've reduced the problem to finding one heavy coin out of five coins containing at least one heavy one.) –  whuber Aug 31 '10 at 18:03
1  
Please elaborate. –  Aryabhata Aug 31 '10 at 19:04
1  
@Moron: Yaser Sulaiman's explanation looks clear and helpful to me. –  whuber Aug 31 '10 at 21:01
3  
@whuber: Yaser's answer misses one case. Where we get H+L vs H+L giving us equal on the first weighing. I am afraid it might not be that easy, as we recently discovered that this was one of the final problems in a Russian Math Olympiad. –  Aryabhata Aug 31 '10 at 22:17
show 1 more comment

Update: It seems that Moron has a valid objection (see the comments) that renders my solution incorrect:

Two sides are equal: You could have 2 heavy and 2 light. Either all light or all heavy is incorrect.

In other words:

Yaser's answer misses one case. Where we get H+L vs H+L giving us equal on the first weighing.

At first, I thought that even if this was the case, one could still find a heavy coin with only one more weighing. Alas, in every weighing scheme I could think of in the context of my solution, there was a situation where one weighing does not give the necessary information to guarantee selecting a heavy coin. Perhaps there's some twisted weighing scheme I didn't think of that would guarantee a correct selection, but I really doubt that (don't take my word for it though.. it's left as an exercise to the reader.)

Moron's solution seems to be a correct one, especially that it is, according to T.., the same as the solution by the original proposer (Shapovalov). I still have to check it out, but it's getting late and I'm quite exhausted. For now, I think it's time for me to get some sleep and to accept the downvotes. Be gentle!


Let me elaborate on whuber's answer by putting it in a slightly different form.

Let's randomly choose 5 coins out of the 100. Let's denote this set of coins by . Since there are only 4 light coins, we are absolutely sure that contains at least one heavy coin. Now, the problem is reduced to simply finding one heavy coin in by using the weight balance twice.

Now stop for a moment and see if you can solve the new reduced problem on your own.

Can't figure it out? Well, choose any 4 coins and put 2 on one side of the balance and 2 on the other. Now, what are the possible outcomes?

  • The two sides are equal. This means that the 4 coins we put on the balance are either all light or all heavy (Update: This is not true. See the update at the beginning). In this case, pick any coin from the balance and compare it with the one we left out. If one is heavier, it would be trivial to select it as a heavy coin. If both are equal, then all of the coins in our initial were actually heavy, so just select any!
  • One side is heavier. This implies that at least one of the 2 coins on this "heavier" side is a heavy coin. Take these 2 coins and compare them with each other. Now selecting a heavy coin is trivial (if they are of equal weight, then they are both heavy, so just select one!)

Whuber's answer/hint (look in the comments) put me on the right track to this solution, so don't forget to vote his answer up!

share|improve this answer
    
Thank you, Yaser. I hope people notice that your explanation not only is detailed and complete but also is the shortest one so far. –  whuber Aug 31 '10 at 21:02
2  
Two sides are equal: You could have 2 heavy and 2 light. Either all light or all heavy is incorrect. –  Aryabhata Aug 31 '10 at 22:15
add comment

Pick any four coins and weigh two against two. If they are imbalanced then at least one of the two coins on the heavier side is heavy and they can now be weighed against each other to identify one or both as heavy. Otherwise replace the two coins on either side of the balance with two other coins. If they are now imbalanced then both coins on the heavier side are heavy, and if they are still balanced then all six coins are heavy.

share|improve this answer
1  
Does not work. First weighing H+L vs H+L. Second weighing H'+L' vs H+L. –  Aryabhata Sep 1 '10 at 0:34
    
Ack, I made the same mistake! Is it required to weigh all coins? –  Dan Brumleve Sep 1 '10 at 0:37
    
Um.. we'll still face a problem if the weight balance is balanced the first time by having a heavy coin and a light one on each side. Suppose that in this case I followed the proposed solution and replaced the coins on one side with 2 other coins. There's a possibility that these 2 new coins are the remaining 2 light ones. Now, how can I tell which of the coins in the other heavier side is the heavy one? –  Yaser Sulaiman Sep 1 '10 at 0:50
    
No idea :-( –  Aryabhata Sep 1 '10 at 0:50
    
Yaser, indeed my answer has the same flaw as yours. It seems like a bit of a paradox that all coins must be weighed even though the total number of coins (100) is irrelevant (or is it?). –  Dan Brumleve Sep 1 '10 at 0:56
add comment

[Edit] As pointed out by longway, there's a hole in this.

My assumptions:

  • Your heavy coins all have the same weight; same for the light coins.

  • The weight balance compares the weight of two sides on the balance instead of giving numerical measurement of weights.

Method: Divide the 100 coins into 2 groups A and B, each comprises 49 coins. The remaining 2 coins are labelled C and D.

  1. Weight A and B.

1.1 A > B (which also handles symmetrically B > A)

Divide A into 24 + 24 + 1 coins, and weigh 24 vs 24.

1.1.1 If the two sides are equal, all of them are genuine.

1.1.2 Otherwise the heavier side contains all genuine coins.

1.2 A = B

Divide A into 24 + 25 coins, add C to the 24 side, and weigh 25 vs 25. Call the side containing C the C-side.

1.2.1 If the C side is heavier, then C is genuine.

1.2.2 If the C side is equal to the other side, then C side minus C are all genuine.

1.2.3 If the C side is lighter, then the other side contains all genuine coins.

Explanation: Divide the 100 coins into 2 groups A and B, each of 49 coins, and label the remaining 2 coins as C and D.

  1. Weight A and B.

1.1 A > B, it means that B has more fake coins than A. Clearly this means that A has either 0 or 1 fake coins.

Divide A into 24 + 24 + 1 coin, and weigh 24 coins against the other 24 coins.

1.1.1 If they are equal, then they must all be genuine since there's at most one fake coin.

1.1.2 If they aren't equal, the heavier side contains all genuine coins.

The case where B > A is symmetric.

1.2 A = B, it means that A and B have same number of fake coins. This number could be 1 or 2.

Divide A into 24 + 25 coins, and add C to the 24 portion, and weigh these 25 coins against the other 25.

  • If A and B both have 1 fake coin only, that means both C and D are fake.

  • If A and B both have 2 fake coins, that means both C and D are genuine.

That means

  • if A has 1 fake coin, then the C side is

    • equal to the other side when C-side minus C are all genuine coins, and the other side contains one fake coin.
    • lighter than the other side when C-side contains the other fake coin as well. In this case the other side contains genuine coins.
  • if A has 2 fake coins, then the C side is

    • lighter than the other side when both fake coins are on the C-side. In this case the other side contains genuine coins.
    • heavier than the other side when some fake coins are on the other side. In this case, C must be genuine anyway since A has 2 fake coins.

So

  • if the C side is heavier, then C is genuine.
  • if the C side is equal to the other side, then C side minus C are all genuine coins.
  • if the C side is lighter, then the other side contains all genuine coins.
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.