All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Sorting Coins II (Posted on 2012-03-28)
This is in continuation of Sorting Coins.

You have 18 coins. They are completely identical in every other respect except five of them weigh 24g, six of them weigh 25g and, the remaining seven weigh 26g. You have only a balance scale to sort them out.

What is the minimum number of weighings which guarantees all the coins to be sorted?

 No Solution Yet Submitted by K Sengupta No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 Full Solution | Comment 2 of 4 |
When I first saw this problem come up, I initially dismissed it as something KS threw together just to add a hard puzzle to the category.  However, over the last few months I have spent a lot of time working on this problem and found an elegant solution.

The puzzle No Equal Weighings was an intermediate result towards solving this puzzle.  Understanding that puzzle is the basis for solving this puzzle.  I will make use of the same notation as I used in the solution to No Equal Weighings.

Phase 1
In this phase initial weighings are made to create 'weighing pyramids' like the one in No Equal Weighings.

The first nine weighings are 1v1 weighings comparing individual coins.

Then if there are at least two unequal weighings then a series of 2v2 weighings are performed, keeping pairs of coins from the first set of weighins as pairs.  (If AvB and CvD are two weighings in the 1v1 set then the 2v2 weighing is (A+B)v(C+D).)  If there is an odd number of 1v1 unequal weighings then one of those pairs will not be used in this step.

Then if there are at least two unequal weighings of 2v2 then 4v4 weighings are made in a similar fashion.

Finally, if there are two unequal 4v4 weighings then a final weighing of 8v8 is made.

At this point the coins can be divided into two groups: coins that have been in exactly one equal weighing and coins that have been in all unequal weighings.  There must be at least two coins in the all unequal weighings group due to parity, specifically the odd 24g and odd 26g coin.  Each of the two groups contain an even number of coins.

Phase 2
In this phase the specific weights of the coins in the all unequal weighings group will be determined.

Case U1: 2 coins
These coins must be a 24g coin and a 26g coin.  No additional weighings needed.

Case U2: 4 coins
These coins are all in a single weighing pyramid.  The distribution of the coins can only be {1,2,1}.  Then by the results from No Equal Weighings no additional weighings are needed to identify the coins.

Case U3: 6 coins
These coins are in two pyramids - a four coin pyramid and a two coin pyramid (single weighing).  The possible distributions are {1,1,2}+{0,1,1} or {2,1,1}+{1,1,0}.

There is one coin in the four coin pyramid which was on the lighter side both times it was weighted, that coin must be 24g.  Similarily the coin that was on the heavier side both times must be a 26g coin.

Make one weighing comparing the known 24g+26g to the other two coins from the four coin pyramid.  If the known weight is heavier then the distribtions are {1,1,2}+{0,1,1}, otherwise a lighter result means the distribtions are {2,1,1}+{1,1,0}.

Case U4: 8 coins
These coins are in a single eight coin pyramid.  The distribtion must be {3,2,3}.  No additional weighings are needed to identify the coins.

Case U5: 10 coins
These coins are in two pyramids - an eight coin pyramid and a two coin pyramid.  The possible distributions are {3,3,2}+{0,1,1} or {2,3,3}+{1,1,0}.

An eight coin pyramid contains two for coin sub-pyramids. Then there are two 24g coins and two 26g coins which can be identified.  Make one weighing with these four coins vs the other four coins from the eight coin pyramid.  If the known weight is heavier then the distribtions are {3,3,2}+{0,1,1}, otherwise a lighter result means the distribtions are {2,3,3}+{1,1,0}.

Case U6: 12 coins
These coins are in two pyramids - an eight coin pyramid and a four coin pyramid.  The possible distributions are {3,3,2}+{2,1,1} or {2,3,3}+{1,1,2}.

Make one weighing using either the eight coin pyramid (like U5) or the four coin pyramid (like U3).  The result will be enough to identify the coins.

Case U7: 14 coins
These coins are in three pyramids - an eight coin pyramid, a four coin pyramid and a two coin pyramid.  Make both weighings described in cases U3 and U5.  Note that this time the results can be an equal weighing.

After determining the composition of the eight and four coin pyramids then the two coin pyramid will be the pair that makes the total parity of coins {1,0,1} mod 2.

Case U8: 16 coins
These coins are in a single sixteen coin pyramid.  The distribtion must be {5,6,5}.  No additional weighings are needed to identify the coins.

Case U9: All 18 coins
These coins are in two pyramids - a sixteen coin pyramid and a two coin pyramid.  The distribtion must be {5,5,6}+{0,1,1}.  No additional weighings are needed to identify the coins.

Phase 3
In this phase the specific weights of the coins in the one equal weighings group will be determined.  With the unequal coins all identified a known 24g coin and a known 26g coin are available.  Also, the total composition of the coins is known by subtracting the unequal coins from the total {5,6,7} composition.

Each case below corresponds to a supplementary U# case in Phase 2

Case E1: 2 coins
No weighing needed.  These must be the last two equal coins, one of 2x24g, 2x25g, or 2x26g depending on the unequal coins.

Case E2: 4 coins
These coins are either in a 4 coin pyramid or two 2 coin pyramids.  If the coins are in a 4 coin pyramid then the known remaining distribution is sufficient to identify the coins without any additional weighings.

If there are two 2 coin pyramids then one weighing needs to be made.  Take the known 24g and 26g coins as a pair and weigh those against one of the two unknown pairs.  If the unknown pair is lighter then they are both 24g coins, if equal then 25g coins, and if heavier then 26g coins.  The other pair can then be deduced from the remaining unassigned compositon.

Case E3: 6 coins
These coins are either in a 4 coin pyramid with a 2 coin pyramid or three 2 coin pyramids.  In the first case one weighing like in case E2 is needed and in the second two such weighings are needed.  This is sufficient to identify all the coins.

In general, one less weighing than there are pyramids are needed to resolve these case.

Case E4: 8 coins
If all three coins are in a single 8 coin pyramid then no additional weighings are needed.  Similar to case E2, the distribtion is known so the identities of the coins can be deduced.

If the coins are split into two 4 coin pyramids then one addtional weighing is needed.  That weighing is made by taking a known 24g coin and a known 26g coin and comparing that pair against one of the two halves of one of the 4 coin pyramids.  If the unknown pair is lighter then they are a 24g coin and a 25g coin, if equal then a 24g coin and a 26g coin, and if heavier then a 25g coin and a 26g coin.  The other pyramid can then be deduced from the remaining unassigned compositon.

The other possibilities are handled like in Case E3.

Case E5: 10 coins
Case E6: 12 coins
Case E7: 14 coins
All these cases can be resolved using the techniques metioned in the earlier cases.

Case E8: 16 coins
The total composition of coins must be {4,6,6}.  Most of the possiblilities can be resolved using the techniques metioned in the earlier cases.  The two special subcases are two 8 coin pyramids or one 16 coin pyramid.

In the case of a single 16 coin pyramid, each half of the pyramid must be a {2,3,3} 8 coin pyramid.  Those coins can all be identified so no additional weighings are needed in this subcase.

In the last case of two 8 coin pyramids, one weighing is made - the two 8 coin pyramids are compared to each other.  The lighter pyramid must consist of two halves of {1,2,1} and the heavier pyramid must consist two halves of {1,1,2}.

Counting the Weighings
The total number of weighings used in this system is 16.  The number of weighings attributed to a specific U(x) cases is equal to 2x-1.  Similarly, the number of weighings attributed to a specific E(y) cases is equal to 2y-1.  But x+y must equal 9, as U(x) and E(y) cases come in pairs totaling 18 coins (excpet the U9 case which by itself has all 18 coins).  Therefore the total number of weighings must be (2x-1) + (2y-1) = 2*(x+y) - 2 = 2*9 - 2 = 16 weighings.  (It is possible to have fewer than 16 weighings in some specific circumstances but in general 16 weighings will always be sufficient.)

I would definitely put this puzzle at D5.  It is certainly doable but took a lot of mental effort to find this solution.

 Posted by Brian Smith on 2016-06-05 00:11:37
Please log in:
 Login: Password: Remember me: Sign up! | Forgot password

 Search: Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2021 by Animus Pactum Consulting. All rights reserved. Privacy Information