The Math Factor Podcast

15 Comments »

1. Stephen Morris said,

   March 30, 2009 at 6:01 pm

   I’m going to take a bite at that there gold coin.

   [spoiler]

   The key point is that most of the coins are gold.  We can throw away coins with abandon as long as we know that no more than half of them are gold.  Most of the remaining coins will still be gold.

    

   The choices for the first pass are entirely arbitrary.  We simply group coins into arbitrary pairs.

   If a pair is different then we discard it on the basis that we are discarding at least as many non-gold coins as gold coins.  We will still have a majority of gold coins.

   This leaves us with only matched pairs.

    

   For the second pass we can take one coin from one of these matched pairs and compare it to a coin from another matched pair.  If they are different we discard both pairs, we know that we are discarding at least as many non-gold coins as gold coins, so we will still have the majority of the coins being gold.

   Now we have groups of four coins which are matched.  Each group has two coins which have not been compared in the second pass.  Again we take a coin from each group of four and compare it to a coin from another group of four.   Again we throw away groups which do not match.

   Now we have groups of eight coins which are matched.  Each group has two coins which have not been matched in the second pass.  Etcetera, etcetera….

    

   We can keep matching groups until we run out of groups of the same size.  Since the size of each group is a power of two the largest group will be all gold.

    

   We have only used two passes.

   [/spoiler]

    

   Is this the most efficient way to find a gold coin in terms of the number of comparisons?

   How many comparisons would be needed to find every gold coin?

2. strauss said,

   March 31, 2009 at 2:44 pm

   That’s a neat solution! I used twice as many passes, but sorted all the coins out into three piles, one of each kind. All the gold coins are then in the largest pile. 

   So, assuming there are the least number of brass coins, and the most coins are gold,  [spoiler] in four passes[/spoiler] you can work out exactly which coins are gold, which are silver, which are brass.

3. Stephen Morris said,

   April 1, 2009 at 12:26 pm

   It makes a difference how you interpret ‘the majority of the coins are gold’.  I took it to mean that more than half of the coins are gold.   

   You could also take it to mean ‘there are more gold coins than either silver or brass coins’.  This makes the puzzle much harder.

   Sticking with my interpretation and solution I thought the following was neat.

   [spoiler]  After completing the comparisons you have grouped the remaining coins into the binary representation of the number of coins.  So if there are seven coins left you will have groups of four, two and one coin.  If there are nine coins left you have groups of eight and one coin.[/spoiler]

4. jyoak said,

   April 1, 2009 at 3:31 pm

   I did intend that there more than 50% of all coins are gold.  My solution requires that as well.

   This solution is better than the one that I intended to offer!  Mine requires three passes.

   The first step I had envisioned is identical to the one above. Arbitrarily line up coins and compare adjacent pairs, discarding any pairs that don’t match. In the second pass you compare one coin from each pair with a coin of each adjacent pair. (Any odd coin on the end is ok with this strategy.) You have now grouped all adjacent like pairs.

   As the final step in this approach, you compare a coin from each group with a coin in the group two away. Since you know the adjacent ones are different, identifying whether the groups two away are like or different is enough to collect all remaining groups with like groups.

   That’s three passes and more comparisons to boot.

5. Stephen Morris said,

   April 2, 2009 at 11:52 am

   This is a great puzzle jyoak, is it original?  

   If you don’t throw away the unmatched pairs then I think your method sorts all of the coins into three piles in four passes, which is the number Chaim used.

   I can prove that four passes is the minumum to sort all the coins in general, that is without using the fact that the majority of coins are gold.

   Putting the coins in a line the number of possible arrangements is (3^n)/6.  The 6 is because if we relable the coins the pattern is essentially the same 

   (e.g. you could relable the gold coins as silver, silver coins as brass and brass coins as gold).

   This increases exponentially with n with a base of 3.

   The number of comparisons in one pass is at most n/2.  With p passes it is pn/2.  The number of possible results is at most 2^(pn/2).

   This increases exponentially with n with a base of 2^(p/2).

   If p passes is sufficient then we need the number of results to increase at least as quickly as the number of arrangements.  

   So we need 2^(p/2) >= 3

   Squaring gives 2^p >= 9

   Which gives p > 3.

   So 4 passes is the minimum that will always work.

6. jyoak said,

   April 2, 2009 at 12:08 pm

   Stephen, It isn’t original and I don’t know the source.  Puzzles of this sort are common as interview questions for computer programmers and the culture tends to appreciate them and continue to pass them around.  This is one such I heard around the water cooler of a programming shop. Another such puzzle that’s been on the site before was in DX.  http://mathfactor.uark.edu/2008/05/13/dx-dumb-robots/  This one is anecdotally ascribed to originating from a Microsoft interview question, though I don’t have strong evidence of that.

7. czarandy said,

   April 20, 2009 at 8:41 pm

   A variant of this is that you can make arbitrary comparisons and want to minimize their number. This is basically the “majority element” problem.

   In the worst case, I believe you need n-1 comparisons (for n elements).

   You could also do the standard probabilistic approach:
   1. Pick C random coins (with replacement).
   2. Find the majority among them.
   3. Output that as the answer.

   Unfortunately if you have just slightly more than half of one type and just slightly less than half of the other, this doesn’t work so well. But if you know that there is a fixed proportion of the gold coins (e.g., 50.01%) then you only need to make a *constant* number of comparisons.

8. Phil Ryan said,

   September 18, 2009 at 10:30 am

   A slight problem with the 2 pass solution, if you have an odd number of coins then you are not guarenteed to have more than 50% gold coins after 1st pass. Eg if have 5 coins, 3 of them gold, 2 silver- what happens after your 1st pass with 2 matches?

9. jyoak said,

   September 18, 2009 at 12:11 pm

   Phil,

   I don’t see the objection.  Could you provide specifics?  Perhaps lay out the five coins in order assuming you match from left to right.  For instance, one combination is:

   GGSSG which has the two matches.  You’d match the first two and retain.  You’d match the second two and retain.  And you always retain the odds.  So you have a majority of gold.

   To finish the algorithm, you’d then match pair one (GG) to pair two (SS) and they don’t match so you’d discard them.  At this point, you have one coin and you know it is gold because in removing you removed at least as many non-gold as gold and you started witha  gold majority.

   I know this doesn’t necessarily ansswer your objection as you may have a different ordering in mind.  Show us how.

10. gold coins said,

    January 1, 2010 at 3:10 am

    This puzzle is very confusing if you can touch the coin you can tell by the weight.   The gold coins will always be the heaviest.  The gold coin should look different to the others so maybe that would be the best way to distinguish them.

11. american eagle gold coin said,

    January 2, 2010 at 7:40 pm

    I would take a bite out of it . otherwise this puzzle is very confusing i must say

12. lunaticg said,

    January 10, 2010 at 10:17 pm

    What is the answer or solutions?
    I am not very good at math but this sound interesting.

13. Parallel Minded said,

    January 17, 2013 at 10:33 am

    Stephen’s 2-pass solution, and his 4-pass extension of Jeff’s solution, depend on a loophole in the problem statement.  Jeff’s 3-pass solution does not use the loophole.

    The problem statement refers to “passes”, for which certain properties are listed (sounding like clarifications rather than an exhaustive list of properties). A very natural unlisted property for a pass would be that the comparisons in a pass are essentially simultaneous, so in particular you cannot use results from the “first part” of a pass to decide what coins to compare “later” in that same pass.  This property is natural if you think of a pass as being done in one step on a parallel computer, and of course you want to minimize the number of passes because comparisons take a long time and you want to minimize the time of the parallel algorithm.  Indeed, without this property, it seems much less natural to want to try to minimize the number of passes.  (Do you have a data structure that decays each time it gets compared?)

    (If I were to ask this question in an interview, and the applicant used this loophole, I would ask them for an example of when their interpretation could be relevant!)

    In any event, Stephen’s nice and tight analysis prompts the non-loophole version of the same question:

    How many parallel passes does it take to separate all the coins by type into three piles?

14. Stephen Morris said,

    January 18, 2013 at 6:48 pm

    Parallel Minded: Yes, you make a good point, why would you be concerned about the number of passes if each pair is compared sequentially?  Unless the coins were affected by the machine maybe?  Seems unlikely.  For the record the problem talked about a machine that took two coins at a time but I agree that then we should be looking at the number of comparisons. Now for your question, [spoiler] I think straus already answered it with four passes.  Arrange the coins in a circle.  Use two passes to compare each coin with it’s immediate neighbours.  We now have contiguous groups of like coins, each group known to be different to the neighbouring groups.  We use two more passes to compare each group to the groups which are one away.  Label one group as A and work clockwise.  The next group we label B.  Going round the circle we can identify each group as A, B or C.[/spoiler]  It’s a fun part of these types of puzzles to try different variations and see what difference they make to the answer.  One obvious change is to get rid of passes altogether and just think about how many pairs we should compare.  Or we could look at the average number of comparisons, rather than the maximum.   In my answer above I have assumed we can take knowledge from one pass and use it to define the next pass, but what if we can’t?  What if we must define the comparisons in each pass before we start? (maybe this was your intention) I don’t know the answer to these questions! 

15. Parallel Minded said,

    January 29, 2013 at 1:34 pm

    Stephen: Ah, nice!  I hadn’t noticed that [spoiler]
    the 3rd and 4th rounds work fine even for groups of a single coin, because you can group the comparisons like this:

    Round 3:
    1 3
    2 4
    5 7
    6 8
    …

    Round 4:
    3 5
    4 6
    7 9
    8 10
    …
    [/spoiler]

    The last question you ask is interesting, it’s like sorting algorithms where all the comparisons need to be specified ahead of time: Sorting Networks.

    But I think it has a rather different answer… [spoiler]
    You need to compare every possible pair of coins.

    If there are any two coins A and B which are not compared with each other, then suppose all other coins (call them “class C coins”) are equal to each other but unequal to A or B. In this case you cannot know whether A and B are the same or not.
    [/spoiler]
    Would it help if you are told there is at least one of each type of coin?

RSS feed for comments on this post · TrackBack URL

Leave a Comment

You must be logged in to post a comment.