Jump to content
Science Forums

Tough wieghing problem


Recommended Posts

found this an interesting challange.

you have a standard balance scale, x number of coins, 2 of which are heavier than the rest.(the two heavy coins are equal in wieght)

you have 4 wieghings. what's the maximum number of coins you can have and still identify the two heavy coins?(you must consider worst case senario on each wieghing)

if you can get 10, you're fairly kowledgeable. 12, very clever. 13, genius.

i was able to get 12 after about 45 minutes. i never got 13.

Link to comment
Share on other sites

This problem is similar to the “find the heavier or lighter item” problem discussed in last year’s thread 13083. Rather than asking for an algorithm to find 1 out of n items that is greater or less than the others, this asks for an algorithm to find 2 out of n items that are greater than the others.

 

We never found an algorithm for finding algorithms – the “meta-algorithm” for the “find 1 greater or less” problem described in “Extremely Difficult Logic Problem”, except for the special case where [math]n=2^{m+1}-1[/math] which generates an algorithm needing no more than [math]m[/math] tries (weighings with the balance scale).

 

After a couple of hours, the best systematic approach I’ve found generates algorithms for the special case of [math]m=3, 4, 6, 9, 13, 19, \dots[/math] that can find the 2 coins in 9 coins in no more than 4 tries, in 13 coins in no more than 5, in 19 in no more than 6, etc. – not good enough even to be “fairly knowledgeable” by the criteria in post #1. :(

 

In the notation described in “An algorithm for generating algorithms for solving the 2^n -1 pencil puzzle”, for 3 coins:

(1-2 2,3 1,2 1,3)

For 4 coins:

(1-2
(2-3 3,4 2,3 2,4)
(1+2-3-4 3,4 err 1,2)
(1-3 3,4 1,3 1,4))

For 6 coins:

(1+2-3-4
(3-4 (4-5 5,6 4,5 4,6) (3+4-5-6 5,6 err 3,4) (3-5 5,6 3,5 3,6))
(1-2 (2-3 3,4 2,3 2,4) 5,6 (1-3 3,4 1,3 1,4))
(1-2 (2-5 err 2,5 2,6) (1+2-5-6 5,6 err 1,2) (1-5 5,6 1,5 1,6)))

For 9 coins:

(1+2+3-4-5-6
(4+5-6-7 (6-7 (7-8 8,9 7,8 7,9) (6+7-8-9 8,9 err 6,7) (6-8 8,9 6,8 6,9)) (4-5 (5-6 6,7 5,6 5,7) 8,9 (4-6 6,7 4,6 4,7)) (4-5 (5-8 err 5,8 5,9) (4+5-8-9 8,9 err 4,5) (4-8 8,9 4,8 4,9)))
(1+2-3-4
 (3-4 (4-5 5,6 4,5 4,6) (3+4-5-6 5,6 err 3,4) (3-5 5,6 3,5 3,6))
 (1-2 (2-3 3,4 2,3 2,4) (7-8 8,9 7,8 7,9) (1-3 3,4 1,3 1,4))
 (1-2 (2-5 err 2,5 2,6) (1+2-5-6 5,6 err 1,2) (1-5 5,6 1,5 1,6)))
(1+2-3-7 (3-7 (7-8 8,9 7,8 7,9) (3+7-8-9 8,9 err 3,7) (3-8 8,9 3,8 3,9)) (1-2 (2-3 3,7 2,3 2,7) 8,9 (1-3 3,7 1,3 1,7)) (1-2 (2-8 err 2,8 2,9) (1+2-8-9 8,9 err 1,2) (1-8 8,9 1,8 1,9))))

As I lamented in “Extremely Difficult Logic Problem”, it’d be nice to have a general algorithm for “knowledge management” puzzles of this sort, but to date, I’ve neither read of one, nor written, one, only seen and written a lot of special case ones.

 

:QuestionM I curious, Phillip – what algorithm (rule) did you use for 12 coins? While I’ve not got a meta-algorithm for finding these, I do have an automatic rule-checking program that can confirm that a rule actually works, so can at least check your result.

Link to comment
Share on other sites

here's the algorithm for 12 in 4 wieghings.

split them into 3 groups of 4, label the groups A,B,C.

wiegh A agianst B.

if one is side is heavier, thel lighter side is all normal, and the other side either has 1 or 2 heavy coins. split group C into 2 groups of 2, and wiegh.

//if both sides are equal, then all four coins are normal, and both heavy coins are in the remaining gorup of 4.

////wiegh 1 coin against 1 coin, if they are equal; then either they are both normal or both heavy, it will take one more wiehging to determine which, if one side is heavy, then you have two coins left and one wieghing left.

//if one side is heavy then you have his setup HN HNNN; wiegh 1 coin from the two group against one coin from the four group.

////if they are equal, then either they are both heavy or both normal, move the coin over the left side, and wiegh agianst two coins from the four group.

if the left side is heavy then both coins are heavy, if not, then all for coins are normal and the two remaining coins are heavy.

////if one side is heavy then you can easily eliminate the remining heavy coin in one more wieghing.

 

if both sides are equal in the intail 4v4, then split the A group into 2 groups of 2 coins and wiegh, and you'll either be back to the hn hnnn setup, or have two heavy coins in group C.

 

 

i do have the solution for 13 coins as well if your interested. though i never solved it myself, i know someone who did.

Link to comment
Share on other sites

//if both sides are equal, then all four coins are normal, and both heavy coins are in the remaining gorup of 4.

////wiegh 1 coin against 1 coin, if they are equal; then either they are both normal or both heavy, it will take one more wiehging to determine which, if one side is heavy, then you have two coins left and one wieghing left.

 

Hi Phillip1882,

 

If there is one heavy coin on each side then you have to use 2 weighings on each side to determine which are the heavy coins. In this worst case the minimum number of weighings is 5 (and that doesn't include the tests required to determine that the remaining group doesn't actually have the two heavy coins).

Link to comment
Share on other sites

aperently you did not understand my post, though i admit i did make a "small" mistake in my logic. here's what it should be.

 

label coins 1-12.

let's assume 4 and 7 are heavy.

step 1 whiegh 1-4 aginst 5-8. they will be equal.

step 2 wiegh 1,2 aginst 3,4. 3,4 will be heavy.

you now have NH NNHN

wiegh 3 and 5 aiagnst 4 and 6.

4 and 6 will be heavy. this means 4 must be heavy, and either 6 7 or 8 are heavy.wiegh 7 agianst 8. 7 will be heavy. done.

if 3 and 5 and 4 and 6 had been equal that means that either 3 and 6 or 4 and 5 are heavy. it takes one wieghing to determine which. if 3 and 5 had been heavy, then 3 must be heavy and either 5 7 or 8 is heavy.

Link to comment
Share on other sites

here's the algorithm for 12 in 4 wieghings…
Thanks, Phillip.

 

It’s hard to write these algorithms precisely in words. Why don’t you try using the notation described in “An algorithm for generating algorithms for solving the 2^n -1 pencil puzzle” and used in my examples in post #2? Not only does it give a way of exactly describing the algorithm, as I mentioned before, I have a small program into which I can just paste text in this form, that will check it against all possible arrangements of coins (there are 66 arrangements for the 12 coin puzzle, too many to easily and reliably do by hand). Without checking against all cases, it’s very easy to think you have a correct algorithm when you don’t.

 

Here’s an explanation of the notation, taking the simple example of finding 2 heavies in 6 coins in 2 or 3 tries:

(1+2-3-4
 (3-4
   (4-5 err 4,5 4,6)
   3,4
   (3-5 err 3,5 3,6))
 (1-2
   (2-3 err 2,3 2,4)
   5,6
   (1-3 err 1,3 1,4))
 (1-2
   (2-5 err 2,5 2,6)
   1,2
   (1-5 err 1,5 1,6)))

The expression “1+2-3-4” means “weight 1 and 2 against 3 and 4” (or “find the weight of 1 plus the wight of 2 minus the weight of 3 minus the weight of 4”) If 1 & 2 are heavier than 3 & 4 (1+2-3-4<0) take the first item following “1+2-3-4”. It they’re the same (1+2-3-4=0), take the second. It 1 is heavier (1+2-3-4>0) take the 3rd and last item. If an item is an expression followed by 3 items within ()s, perform it and continue, until you get just 1 item, such as “3,4” or “err”. A result of “err” (or any other odd word you want to use) means something is wrong – the balance didn’t work correctly, or you don’t have exactly 2 heavies, etc.

 

You can write the algorithm as a single line or break into lines and indent and align it however you like (it’s “whitespace insensitive”). For example, the above could have been written

(1+2-3-4 (3-4 (4-5 err 4,5 4,6) 3,4 (3-5 err 3,5 3,6)) (1-2 (2-3 err 2,3 2,4) 5,6 (1-3 err 1,3 1,4)) (1-2 (2-5 err 2,5 2,6) 1,2 (1-5 err 1,5 1,6)))

 

I started to write your 12 coin algorithm from the example in post #6, getting this far:

(1+2+3+4-5-6-7-8
 (5+6-7-8 (7+9-8-10 (11-12 8,12 8,10 8,11) (7-8 8,9 err 7,10) (11-12 7,12 7,10 7,11))) (?) (5+9-6-10 (11-12 6,12 6,10 6,11) (5-6 6,9 err 5,10) (11-12 5,12 5,10 5,11)))
 (1+2-3-4 
   (3+5-4-6 
     (7-8 4,8 4,6 4,7) 
     (3-4 4,5 err 3,6) 
     (7-8 3,8 3,6 3,7)))
   (?) 
   (1+5-2-6 (7-8 2,8 2,6 2,7) (1-2 2,5 err 1,6) (7-8 1,8 1,6 1,7)))
 (1+2-3-4 (3+9-4-10 (11-12 4,12 4,10 4,11) (3-4 4,9 err 3,10) (11-12 3,12 3,10 3,11))) (?) (1+9-2-10 (11-12 2,12 2,10 2,11) (1-2 2,9 err 1,10) (11-12 1,12 1,10 1,11))))

leaving “?”s where I didn’t know what to write.

Link to comment
Share on other sites

Not only does it give a way of exactly describing the algorithm, as I mentioned before, I have a small program into which I can just paste text in this form, that will check it against all possible arrangements of coins (there are 66 arrangements for the 12 coin puzzle, too many to easily and reliably do by hand). Without checking against all cases, it’s very easy to think you have a correct algorithm when you don’t.

 

Hi CraigD,

 

Especially when terms like 'worst case scenario' are used.

 

It's interesting that your algorithm data is almost laid out like a Prolog dataset without tags for text data because of the numeric nature of the problem. Does your program just test the dataset for correctness or can it be used to query the data itself, as in Prolog? (i.e. the most number of weighings possible and the least no of weighings possible)

Link to comment
Share on other sites

alright. here's my code.

(1+2+3+4-5-6-7-8
 (9+10-11-12
    (1+9-10-2
       (3-4 3,9 1,9 4,9)
       (9-10 9,2 err 1,10)
       (3-4 3,10 2,10 4,10)
    )
    (1-2
       (3-4 1,3 err 1,4)
       (2-3 1,2 err 3,4)
       (3-4 2,3 err 2,4)
    )
    (11+1-12-2
       (3-4 3,11 1,11 4,11)
       (11-12 11,2 err 12,1)
       (3-4 3,12 2,12 4,12)
    )
 )
 (1+2-3-4
    (1+9-2-10
       (11-12 1,11 1,9 1,12)
       (1-2 1,10 err 2,9)
       (11-12 2,11 2,10 2,12)
    )
    (9-10
       (11-12 9,11 err 9,12)
       (10-11 9,10 err 11,12)
       (11-12 10,11 err 10,12)
    )
    (3+9-4-10
       (11-12 3,11 3,9 3,12)
       (3-4 3,10 err 4,9)
       (11-12 4,11 4,10 4,12)
    )
 )
 (9+10-11-12
   (9+5-10-6
      (7-8 9,7 9,5 9,8)
      (9-10 9,6 err 5,10)
      (7-8 10,7 10,6 10,8)
   )
   (5-6
      (7-8 5,7 err 5,8)
      (6-7 5,6 err 7,8)
      (7-8 6,7 err 6,8)
   )
   (11+5-12-6
      (7-8 11,7 11,5 11,8)
      (11-12 11,6 err 12,5)
      (7-8 12,7 12,6 12,8)
   )
 )
)

hope this helps.

if not then i give up.

Link to comment
Share on other sites

It's interesting that your algorithm data is almost laid out like a Prolog dataset without tags for text data because of the numeric nature of the problem.
I find it LISP-y. It seems a terse notation, easy both to human read and write, and handle programmatically.
Does your program just test the dataset for correctness or can it be used to query the data itself, as in Prolog? (i.e. the most number of weighings possible and the least no of weighings possible)
My program has various ad-hoc features, but its main feature is to test an algorithm by applying it to every possible coin arrangement and returning a failure if the result it returns differs from the arrangement (eg: 1,2 are the heavy coins, but the algorithm says 2,3 are). A poorly-formed algorithm (mismatched parentheses, etc.) isn’t detected as poorly formed, but usually will return an incorrect result.

 

Although the checking programs (there’s one for checking the “find 1 heavy or light coin”, another for the “find 2 heavies” puzzle) are special, the notation is completely generic. Assuming you avoid or escape parentheses and spaces in its terms, it can be used to describe any trial-based choosing algorithm where the trial result map to list item.

 

It’s written in MUMPS, using a peculiar “xecute code only” technique. Here’s the actual code, invoked by x XPZL13:

n (XPZL12) f  r !,"[1]Demo classic puzzle [2]Demo knowledge representation [3]Demo Algorithm",!,"[4]Test Algorithm [5]Interact with Algorithm: ",R q:R=""  x XPZL12(0,(R=1:1,R=2:2,R=3:3,R=4:4,R=5:5,1:"?")) ;XPZL12: various "fake coin" puzzle programs demonstrated
s A="(1+2+3+4-5-6-7-8 (1+2+5-3-6-9 (1-2 1 6 2) (7-8 8 4 7) (3-9 3 5 error)) (9+10-8-11 (9-10 9 11 10) 12 (9-10 10 11 9)) (5+6+1-7-2-9 (5-6 5 2 6) (3-4 4 8 3) (7-9 7 1 error)))" f V=6,4 f I=1:1:12 s B="5,5,5,5,5,5,5,5,5,5,5,5",(B,",",I)=V x XPZL12(1) w I,":",N," " ;XPZL12(0,1)
s K="" f  r !,"Number of coins: ",R q:R=""  w !,"#+#..-#-#...=-1|0|1" s BL=R f  R !,D q:D_K=""  s:D="" K="" i D]"" x XPZL12(11) w "  ",K ;XPZL12(0,2)
f  r !,"Number of coins: ",R q:R<1  s I9=R w !,"Algorithm:",! x XPZL12(20,1) w "# Weighings ... Result (# weighings)",! x XPZL12(20,2) w "Maximum # weighings: ",LR9,! ;XPZL12(0,3): read and demo algorithm for n-coin puzzle
f  r !,"Number of coins: ",R q:R<1  s I9=R w !,"Algorithm:",! x XPZL12(20,1) w "Testing..." x XPZL12(20,12) w (F:"Success",1:"Failure"),".  Maximum # weighings: ",LR9,! ;XPZL12(0,4): read and test algorithm for n-coin puzzle
w !,"Algorithm:",! x XPZL12(20,1) f  s N=A x XPZL12(5) q:R=""  w ?(C-1)+2,N,! ;XPZL12(0,5): Interact with Algorithm
f  w C,") ",(N," ") r "=",R,! s R=(R="":"",R?1(1"-1",1"0",.1"+"1"1"):+R,1:9) q:R-9  ;XPZL12(0,5,1)
W !,"Enter 1 or 2 or 3 or 4 or 5 or ENTER to quit" ;XPZL12(0,"?")
n (XPZL12,A,B,N,R) s N=A,R="" f  q:N'?1"(".e  s N=(N,2,(N)-1) x XPZL12(1,1),XPZL12(1,2) s I=(D<0:2,D>0:4,1:3),N=(N," ",(P,",",I-1)+1,(P,",",I)) ;XPZL12(1): apply algorithm A to object list B giving N for different (B,",",N)
s J=(N," "),R=R_(R]"":" ",1:"")_J,J=(J,"-","+"),D=0 f I=1:1:(J,"+") s JI=(J,"+",I),D=(N,((J,"+",1,I))-(JI))_(B,",",JI)+D ;XPZL12(1,1)
s P=1 f I=2:1:(N," ") s J=(N," ",1,I) s:(J,"(")=(J,")") P=P_","_I ;XPZL12(1,2)
s R="" f C=1:1 q:N'?1"(".e  s N=(N,2,(N)-1) x XPZL12(0,5,1),XPZL12(1,2) q:R=""  s I=(R<0:2,R>0:4,1:3),N=(N," ",(P,",",I-1)+1,(P,",",I)) ;XPZL12(5): apply algorithm A to interactive user input
n (XPZL12,BL,K,D) s:'((K)) (K,"+-,",BL)="+-" x XPZL12(11,1),XPZL12(11,2) ;XPZL12(11): update knowledge K about B given data D
s N=((D,"=")," "),J=(N,"-","+"),D=((D,"=",2)," "),S="" f I=1:1:(J,"+") s JI=(J,"+",I),JS=(N,((J,"+",1,I))-(JI)),(S,",",JI)=+(JS_1) ;XPZL12(11,1)
f I=1:1:BL s SI=(S,",",I),KI=(K,",",I),(K,",",I)=(D<0:(SI<0:(KI,"-"),SI>0:(KI,"+"),1:""),D>0:(SI<0:(KI,"+"),SI>0:(KI,"-"),1:""),SI:"",1:KI) ;XPZL12(11,2)
s A="" f  r R,! q:R=""  s A=A_" "_R x "f  q:(A)'="" ""  s (A)=""""","f  q:(A,(A))'="" ""  s (A,(A))=""""","f  q:A'[""  ""  s (A,""  "",1,2)=(A,""  "")_"" ""_(A,""  "",2)" ;XPZL12(20,1): cannonicize whitespaced lines
S LR9=0 f V=6,4 f I=1:1:I9 s B="",(B,"5,",I9)=5,(B,",",I)=V x XPZL12(1) s LR=(R," ") w I," ",R," ",N," (",LR,")",! s:LR>LR9 LR9=LR ;XPZL12(20,2)
S LR9=0 S F=1 f V=6,4 f I=1:1:I9 s B="",(B,"5,",I9)=5,(B,",",I)=V x XPZL12(1) s:N-I F=0 s LR=(R," ") s:LR>LR9 LR9=LR ;XPZL12(20,12)
n (XPZL13,XPZL12) f  r !,"[0]Other options [4]Test Algorithm: ",R q:R=""  x XPZL13(0,(R=0:0,R=4:4,1:"?")) ;XPZL13: various "2 heavy coins" puzzle programs
x XPZL12 ;XPZL13(0,0)
f  r !,"Number of coins: ",R q:R<1  s I9=R w !,"Algorithm:",! x XPZL12(20,1) w "Testing..." x XPZL13(20,12) w (F:"Success",1:"Failure "_(F,";",2,99)),".  Maximum # weighings: ",LR9,! ;XPZL13(0,4): read and test algorithm for n-coin puzzle
W !,"Enter 0 or 1 or ENTER to quit" ;XPZL13(0,"?")
S LR9=0,F=1,V=6 f I1=1:1:I9-1 f I2=I1+1:1:I9 x XPZL13(20,12,1),XPZL12(1) s:I1_","_I2'=N F=0_";"_B_";"_N s LR=(R," ") s:LR>LR9 LR9=LR ;XPZL13(20,12)
s B="",(B,"5,",I9)=5 f I=1:1:I9 s:I=I1!(I=I2) (B,",",I)=V ;XPZL13(20,12,1)

Since my intuitive ability to solve these puzzles, even with computer assistance, is pretty poor :hihi:, and because most of the ones of interest have fairly small algorithm spaces (number of possible algorithms), I plan next to write a brute-force algorithm finder. I’d like to eventually find (or someone else find, and tell me about) an elegant one.

Link to comment
Share on other sites

alright. here's my code. …
Excellent! Now that were using the same notation, we can communicate are algorithms exactly. :hihi:

 

My checker found some minor transposition mistakes – mostly items like “(7-8 12,7 12,6 12,8)” that should be “(7-8 12,8 12,6 12,7)”. I corrected them, rechecked, and found something more serious:

 

When are the heavies are 8,11, the algorithm reaches the following result

1) 1+2+3+4-5-6-7-8=-1

2) 9+10-11-12=-1

3) 1+9-10-2=0

4) 9-10=0

Result: err

 

You can change the “err” to “8,11”, but then the algorithm reaches a result of 8,11 when the heavies are 8,12. I can’t figure out any way to fix this without adding a 5th try.

Link to comment
Share on other sites

okay try #2

(1+2+3+4-5-6-7-8
 (9+10-11-12
   (11+5-12-6
      (7-8 12,8 12,6 12,7)
      (11-12 12,5 err 11,6)
      (7-8 11,8 11,5 11,7)
   )
   (5-6
      (7-8 6,8 err 6,7)
      (6-7 7,8 err 5,6)
      (7-8 5,8 err 5,7)
   )
   (9+5-10-6
      (7-8 10,8 10,6 10,7)
      (9-10 10,5 err 6,9)
      (7-8 9,8 9,5 9,7)
   )
 )
 (1+2-3-4
    (3+9-4-10
       (11-12 4,12 4,10 4,11)
       (3-4 4,9 err 3,10)
       (11-12 3,12 3,9 3,11)
    )
    (9-10
       (11-12 10,12 err 10,11)
       (10-11 11,12 err 9,10)
       (11-12 9,12 err 9,11)
    )
    (1+9-2-10
       (11-12 2,12 2,10 2,11)
       (1-2 2,9 err 1,10)
       (11-12 1,12 1,9 1,11)
    )
 )
 (9+10-11-12
   (11+1-12-2
       (3-4 4,12 2,12 3,12)
       (11-12 12,1 err 11,2)
       (3-4 4,11 1,11 3,11)
    )
    (1-2
       (3-4 2,4 err 2,3)
       (2-3 3,4 err 1,2)
       (3-4 1,4 err 1,3)
    )
    (1+9-10-2
       (3-4 4,10 2,10 3,10)
       (9-10 1,10 err 2,9)
       (3-4 4,9 1,9 3,9)
    )
  )
)

Link to comment
Share on other sites

gahhhh! :singer:

try # 3.

(1+2+3+4-5-6-7-8
 (9+10-11-12
   (11+5-12-6
      (7-8 12,8 12,6 12,7)
      (11-12 12,5 err 11,6)
      (7-8 11,8 11,5 11,7)
   )
   (5-6
      (7-8 6,8 err 6,7)
      (6-7 7,8 err 5,6)
      (7-8 5,8 err 5,7)
   )
   (9+5-10-6
      (7-8 10,8 10,6 10,7)
      (9-10 10,5 err 6,9)
      (7-8 9,8 9,5 9,7)
   )
 )
 (1+2-3-4
    (3+5-4-6
       (7-8 4,8 4,6 4,7)
       (3-4 4,5 err 3,6)
       (7-8 3,8 3,5 3,7)
    )
    (9-10
       (11-12 10,12 err 10,11)
       (10-11 11,12 err 9,10)
       (11-12 9,12 err 9,11)
    )
    (1+5-2-6
       (7-8 2,8 2,6 2,7)
       (1-2 2,5 err 1,6)
       (7-8 1, 1,5 1,7)
    )
 )
 (9+10-11-12
   (11+1-12-2
       (3-4 4,12 2,12 3,12)
       (11-12 12,1 err 11,2)
       (3-4 4,11 1,11 3,11)
    )
    (1-2
       (3-4 2,4 err 2,3)
       (2-3 3,4 err 1,2)
       (3-4 1,4 err 1,3)
    )
    (1+9-10-2
       (3-4 4,10 2,10 3,10)
       (9-10 1,10 err 2,9)
       (3-4 4,9 1,9 3,9)
    )
  )
)

i can't believe i did that.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

×
×
  • Create New...