(Hopefully) new balance puzzle

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Yat
Posts: 131
Joined: Tue Feb 03, 2009 2:05 pm UTC

(Hopefully) new balance puzzle

Postby Yat » Sun Oct 28, 2012 9:53 pm UTC

I have never seen this variation of the classic balance puzzles before, so I tried to solve it and found the solution.

I am not going to tell a story around this because it is a classic type of problem, the deal is that you have 7 coins, but 2 of these coins are slighly lighter than the other 5. Of course, real coins have weight exactly the same, and the two fake coins weight the same too. You have a balance, and the right to use it 3 times, and you need to tell the weights beforehand.

How do you find the 2 fake coins ?

User avatar
dudiobugtron
Posts: 1098
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: The Outlier

Re: (Hopefully) new balance puzzle

Postby dudiobugtron » Sun Oct 28, 2012 10:35 pm UTC

Yat wrote:you need to tell the weights beforehand.

Just checking for clarification of this point. Does it mean that you know what weights both types of coins are before you start weighing them (eg: you know the real coins are (say) 30g and the fake ones are (say) 29 grams)? Or does it mean something else?
Image

Yat
Posts: 131
Joined: Tue Feb 03, 2009 2:05 pm UTC

Re: (Hopefully) new balance puzzle

Postby Yat » Sun Oct 28, 2012 10:58 pm UTC

dudiobugtron wrote:
Yat wrote:you need to tell the weights beforehand.

Just checking for clarification of this point. Does it mean that you know what weights both types of coins are before you start weighing them (eg: you know the real coins are (say) 30g and the fake ones are (say) 29 grams)? Or does it mean something else?
I'm sorry. This type of balance: http://en.wikipedia.org/wiki/Roberval_Balance
No reference weights, you just compare sets of coins.
That means you need to determine the 6 sets of coins befoire weighting the first one.

User avatar
Snark
Posts: 425
Joined: Mon Feb 27, 2012 3:22 pm UTC

Re: (Hopefully) new balance puzzle

Postby Snark » Mon Oct 29, 2012 12:49 am UTC

Coins A, B, C, D, E, F, G

Spoiler:
1 Test A+B with C+D. If equal, goto 2.1. If A+B > C+D, goto 2.2. If A+B < C+D, swap A and B names with C and D names and goto 2.2.
2.1 Test A and B. If equal, goto 3.1.1. If A > B, goto 3.1.2. If A < B, switch A and B's names and goto 3.1.2.
2.2 Test F and G. If equal, goto 3.2.1. If F > G, goto 3.2.2. If F < G, switch F and G's names and goto 3.2.2.
3.1.1 Test E and F. If equal, E and F are bad. If E > F, F and G are bad. If E < F, E and G are bad.
3.1.2 Test A and C. If equal, B and D are bad. If A > C, B and C are bad. If A < C, you've messed something up as this case is impossible.
3.2.1 Test C and D. If equal, C and D are bad. If C > D, D and E are bad. If C < D, C and E are bad.
3.2.2 Test A and C. If equal, D and G are bad. If A > C, C and G are bad. If A < C, you've messed something up as this case is impossible.
Dashboard Confessional wrote:I want to give you whatever you need. What is it you need? Is it within me?


Avatar by Matt

User avatar
ThirdParty
Posts: 337
Joined: Wed Sep 19, 2012 3:53 pm UTC
Location: USA

Re: (Hopefully) new balance puzzle

Postby ThirdParty » Mon Oct 29, 2012 3:53 am UTC

Snark: I think we're supposed to specify all three trials in advance, before we have the results of any of them.

Here's my solution, retaining your labeling of the coins as ABCDEFG:
Spoiler:
Test ABC vs. DEF, AD vs. BE, and AF vs. CD.

ABC < DEF, AD < BE, AF < CD: AG are fake
ABC < DEF, AD < BE, AF = CD: AC are fake
ABC < DEF, AD > BE, AF > CD: BC are fake
ABC < DEF, AD > BE, AF = CD: BG are fake
ABC < DEF, AD = BE, AF < CD: AB are fake
ABC < DEF, AD = BE, AF > CD: CG are fake
ABC > DEF, AD < BE, AF > CD: DG are fake
ABC > DEF, AD < BE, AF = CD: DF are fake
ABC > DEF, AD > BE, AF < CD: EF are fake
ABC > DEF, AD > BE, AF = CD: EG are fake
ABC > DEF, AD = BE, AF < CD: FG are fake
ABC > DEF, AD = BE, AF > CD: DE are fake
ABC = DEF, AD < BE, AF < CD: AF are fake
ABC = DEF, AD < BE, AF > CD: CD are fake
ABC = DEF, AD < BE, AF = CD: AD are fake
ABC = DEF, AD > BE, AF < CD: BF are fake
ABC = DEF, AD > BE, AF > CD: CE are fake
ABC = DEF, AD > BE, AF = CD: BE are fake
ABC = DEF, AD = BE, AF < CD: AE are fake
ABC = DEF, AD = BE, AF > CD: BD are fake
ABC = DEF, AD = BE, AF = CD: CF are fake

Yat
Posts: 131
Joined: Tue Feb 03, 2009 2:05 pm UTC

Re: (Hopefully) new balance puzzle

Postby Yat » Mon Oct 29, 2012 10:07 am UTC

ThirdParty wrote:Snark: I think we're supposed to specify all three trials in advance, before we have the results of any of them.

Here's my solution, retaining your labeling of the coins as ABCDEFG:
Spoiler:
Test ABC vs. DEF, AD vs. BE, and AF vs. CD.

ABC < DEF, AD < BE, AF < CD: AG are fake
ABC < DEF, AD < BE, AF = CD: AC are fake
ABC < DEF, AD > BE, AF > CD: BC are fake
ABC < DEF, AD > BE, AF = CD: BG are fake
ABC < DEF, AD = BE, AF < CD: AB are fake
ABC < DEF, AD = BE, AF > CD: CG are fake
ABC > DEF, AD < BE, AF > CD: DG are fake
ABC > DEF, AD < BE, AF = CD: DF are fake
ABC > DEF, AD > BE, AF < CD: EF are fake
ABC > DEF, AD > BE, AF = CD: EG are fake
ABC > DEF, AD = BE, AF < CD: FG are fake
ABC > DEF, AD = BE, AF > CD: DE are fake
ABC = DEF, AD < BE, AF < CD: AF are fake
ABC = DEF, AD < BE, AF > CD: CD are fake
ABC = DEF, AD < BE, AF = CD: AD are fake
ABC = DEF, AD > BE, AF < CD: BF are fake
ABC = DEF, AD > BE, AF > CD: CE are fake
ABC = DEF, AD > BE, AF = CD: BE are fake
ABC = DEF, AD = BE, AF < CD: AE are fake
ABC = DEF, AD = BE, AF > CD: BD are fake
ABC = DEF, AD = BE, AF = CD: CF are fake


Seems correct!
I had to use brute force to find the solution (considering different labellings of the coins, weights order direction, there is only one!). Can I ask you what method you used?

User avatar
ThirdParty
Posts: 337
Joined: Wed Sep 19, 2012 3:53 pm UTC
Location: USA

Re: (Hopefully) new balance puzzle

Postby ThirdParty » Mon Oct 29, 2012 4:05 pm UTC

Yat wrote:Can I ask you what method you used?
Well, I started out having read the problem like Snark did, where the weighings didn't have to be pre-programmed, and I arrived at this solution:
Spoiler:
1. Test ABC against DEF. If ABC < DEF, go to 2.1. If ABC > DEF, switch the labels and go to 2.1. If ABC = DEF, go to 2.2.
2.1. Test A against B. If A < B, go to 3.1.1. If A > B, switch the labels and go to 3.1.1. If A = B, go to 3.1.2.
3.1.1. Test C against G. If C < G, fake coins are A and C. If C > G, fake coins are A and G.
3.1.2. Test AB against CG. The fake coins are whichever pair is lighter.
2.2. Test A against B. The lighter one is fake. If they're equal, C is fake. Proceed to 3.2.
3.2. Test D against E. The lighter one is fake. If they're equal, F is fake.
When I realized that the weighings had to be pre-programmed, I set out to try to merge the branches:
Spoiler:
First, observe that if the first trial (or any trial, since the trials are unordered) had only one coin on each side, there would be 11 ways for it to come out equal, and only 9 possible results of the other trials. So we know that all trials have to be either 3v3 or 2v2. Odds are that there'll be at least one of each, so I decided to keep ABCvDEF as my first trial.

The first problem is how to rescue the relabeling that feeds into 2.1. There were two possible ways to do this: make the second and third trials symmetric with each other across ABC/DEF reflections, with the second trial having A?vB? and the third having D?vE?, or do ADvBE in the second trial. (At this point we haven't distinguished A, B, or C from each other, and likewise haven't distinguished D, E, or F from each other, so something like AEvBF isn't a genuine alternative.) The first option was a dead end: the only way to make it distinct from ADvBE while retaining symmetry would be to make the second trial ACvBG and the third trial DFvEG, which obviously won't work because it can't distinguish the AD=fake, AF=fake, CD=fake, and CF=fake cases from one another. So my second trial was going to be ADvBE.

At this point I'm not too worried about handling 3.1.2, since lots of things can resolve the choice between two distinct pairs, so my next worry is how to handle 3.1.1. I need a test that's symmetric across ABC/DEF reflections and that uses either C or G. There is no symmetric test that uses G; the options here are ACvDF or AFvCD. When I tried both of these against the ABC=DEF case, I found that the latter worked.

Yat
Posts: 131
Joined: Tue Feb 03, 2009 2:05 pm UTC

Re: (Hopefully) new balance puzzle

Postby Yat » Mon Oct 29, 2012 5:26 pm UTC

Thank you for proving me that this can be solved with a non computer-enhanced brain! :wink:


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 7 guests