wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Coin weighting using discrete math
        
(Message started by: wonderful on Aug 19^th, 2008, 2:13pm)

Title: Coin weighting using discrete math
Post by wonderful on Aug 19^th, 2008, 2:13pm

There are two questions:

Q1. Given 6 idetical looking coins: A, B, C, D, E, F with corresponding weight: 1, 2, 3, 4, 5, 6.

Using a standard two-arm balance, can you design a weighting scheme to identify the weight of each of these six coins?

Q2. The same as above with 12 identical looking coins.

Have A Great Day!

Title: Re: Coin weighting using discrete math
Post by SMQ on Aug 20^th, 2008, 6:25am

Just any scheme, or the most efficient scheme? As an upper bound, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/n.gif coins with known weights can be identified in http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/n.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.giflog₂ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/n.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif weighings by simply sorting them by weight.

--SMQ

Title: Re: Coin weighting using discrete math
Post by towr on Aug 20^th, 2008, 7:38am

It would be much easier to do it without weighing.
Just take a flat piece of board, put the coins on edge next to each other and tilt the board slightly. The fastest coin is lightest, the slowest heaviest etc.

(Although it assumes some measure of uniformity in the density of the coins)

Title: Re: Coin weighting using discrete math
Post by towr on Aug 20^th, 2008, 8:12am

You could use insertion into a balanced binary tree. It's pretty close to optimal; at least if you're limited to comparing two coins at a time (I'm not sure if comparing more at a time would give more information, but it's possible)
[hide]Optimal are 10 and 30; and I get 11 and 33[/hide]

Title: Re: Coin weighting using discrete math
Post by towr on Aug 20^th, 2008, 10:23am

Using http://www.mat.unb.br/~ayala/4FordJohnson.ps I can now do it optimally. (At least anything up to 12; and up to 47 it gives the least number of comparisons known.)

Title: Re: Coin weighting using discrete math
Post by pex on Aug 20^th, 2008, 1:33pm

Modulo programming errors, question 1 can be solved in seven weightings. 8) (I haven't got to question 2 yet because MatLab won't let me store all the 12! permutations in one matrix.)

A theoretical lower bound is six, as each weighting has three possible outcomes and 3⁵ < 6! < 3⁶. Given the small slack (720 permutations versus 729 possible outcomes), I would be surprised if six were actually attainable.

Attached is the computer-generated weighting scheme. It's probably not the simplest possible, but it does seem to work.

Title: Re: Coin weighting using discrete math
Post by wonderful on Aug 21^st, 2008, 12:45pm

Thanks guys for your excellent discussion. I am particularly impressed with Pex's solution which is very nicely done.

Have A Great Day!

Title: Re: Coin weighting using discrete math
Post by Hippo on Aug 21^st, 2008, 3:34pm

on 08/20/08 at 13:33:00, pex wrote:

Does an initial weighting exist such that the biggest part is http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif3⁵=243? If not, the 7 weightings are surely optimal.

Title: Re: Coin weighting using discrete math
Post by pex on Aug 21^st, 2008, 10:35pm

on 08/21/08 at 15:34:28, Hippo wrote:

Does an initial weighting exist such that the biggest part is http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif3⁵=243? If not, the 7 weightings are surely optimal.

:-[ should've thought of this myself... Of course, you're right. And no, such an initial weigting does not exist: my program works by picking a weighting such that the largest group left is as small as possible. For the initial weighting, that's 304.

on 08/21/08 at 12:45:52, wonderful wrote:

Thanks guys for your excellent discussion. I am particularly impressed with Pex's solution which is very nicely done.

Have A Great Day!

Thanks - but it's just brute-force programming; I didn't do much work...

Title: Re: Coin weighting using discrete math
Post by towr on Aug 22^nd, 2008, 1:58am

In the case of twelve coins the initial weighing gives a maximum information gain of about 0.886567 bits. You could use that approach recursively to find a probably optimal decision tree. But after the first weighing it takes a lot more computation to find out (because you lose all the symmetry of the initial position)

The best first move seems to be weighing 2 vs 3 balls. Which split the list of permutations into two groups of 224179200 and one of 30643200.

Title: Re: Coin weighting using discrete math
Post by Grimbal on Aug 22^nd, 2008, 2:30am

And it is possible that a sub-optimal first weighing leads to groups that can better be split in the second weighing. So it is not obvious that the optimal choice at each step, in terms of smallest size of the worst case, leads to a global optimum.

PS: oops, I just realized you said probably optimal. I agree with that.