Extremely Difficult Logic Problem

[User2983]

You have 12 pencils. 11 of them are exactly the same weight and the other one is either HEAVIER or LIGHTER. Determine which one is the odd pencil by using a balance beam only 3 times. HINT: for the first balance, use four on each side.

 

I cannot figure this one out to save my life and I've been working on it for a while.:evil::shrug:

[Inter.spem.et.metum]

If you don't an equal weight on both sides with the first eight pencils it won't work. If you do, then you have four pencils left with one being the pencil you are looking for. Then label the four pencils according to the side you put it on. For example, A1 and A2, and B1 and B2. Weigh the four and remember which side weighs less. Take off A1 and B1. If one of the sides still weigh less, then you have your answer. If not, whichever side weighed less than the other before you removed first two pencils was the side that held the lighter pencil.

[User2983]

If you don't an equal weight on both sides with the first eight pencils it won't work. If you do, then you have four pencils left with one being the pencil you are looking for. Then label the four pencils according to the side you put it on. For example, A1 and A2, and B1 and B2. Weigh the four and remember which side weighs less. Take off A1 and B1. If one of the sides still weigh less, then you have your answer. If not, whichever side weighed less than the other before you removed first two pencils was the side that held the lighter pencil.

 

but you don't know if the pencil is lighter or heavier :evil:

[Erasmus00]

First, measure 4 and 4. If they weigh the same, you have narrowed the special pencil down to 4, which also gives you 8 control pencils.

 

Now, measure 2 of the remaining 4 against two control pencils. After this weighing, you have narrowed the special pencil down to one of two. Measure on of these remaining pencils against one of the control pencils. This will allow you to determine the special pencil.

 

Now, if the original 4 did not weigh the same, then you again have control pencils, but you have 8 uncertain pencils. However, we have extra info- 4 of these pencils weighed "heavy" and 4 weighed "light."

 

Take 3 heavy pencils and 3 light pencils and weigh them against controls. If its heavier, you know that a. the special pencil is heavier, and b. one of your three heavy pencils is the special one. Hence, the third weighing is one of the heavy pencils against one of the other heavy pencils. If they are teh same, the odd man out is special, else the heavier pencil is special. Same thing if it weighed lighter then the controls.

 

The last case is you get the same thing when you do this second weighing. So now we have 1 heavy pencil and 1 light pencil. Take either one and weigh it against a control.

-Will

[Inter.spem.et.metum]

Yes you would.

 

Side A (A1...A2) (B2....B1) B Side

Weight 1.00 Weight 0.99

 

Take off A1 and B1.

 

IF:

 

Side A (A2) (B2) B Side

Weight .50 Weight .50

 

Then B1 is the lighter pencil.

 

IF:

 

Side A (A2) (B2) B Side

Weight .50 Weight .49

 

Then your answer is obvious. How would this not work?

[User2983]

Yes you would.

 

Side A (A1...A2) (B2....B1) B Side

Weight 1.00 Weight 0.99

 

Take off A1 and B1.

 

IF:

 

Side A (A2) (B2) B Side

Weight .50 Weight .50

 

Then B1 is the lighter pencil.

 

IF:

 

Side A (A2) (B2) B Side

Weight .50 Weight .49

 

Then your answer is obvious. How would this not work?

 

No, you're right. That would work. I just read it wrong.

[LaurieAG]

You have 12 pencils. 11 of them are exactly the same weight and the other one is either HEAVIER or LIGHTER. Determine which one is the odd pencil by using a balance beam only 3 times. HINT: for the first balance, use four on each side.

 

Hi User2983,

 

This puzzle is a variant of the old 9 gold coins with one 'dud', determined from 2 weighings of a beam balance (note the dud is lighter than gold).

 

1. Separate into groups of 3 and compare 2 on the beam balance. If one of these 2 groups goes higher than the other select it, otherwise select the third untested set.

 

2. of the selected set compare two of the coins on the balance. If they both balance the third untested coin is the dud, otherwise the coin that goes higher is the dud.

[CraigD]

Everything seemed OK with Erasmus’s approach until the second weighing when the first 4 and 4 weighing wasn’t the same

… Take 3 heavy pencils and 3 light pencils and weigh them against controls.

This would work if I had 6 control pencils, but I only have the 4 not used in the first weighing.

 

I found (at Analytical Puzzles - Very Difficult – the internet has made a talentless, cheating hack of me ;)) this algorithm, and tested it. Writing it in ordinary English seemed clumsy, so I used a simple code:

• “0: (1,2,3,4)-(5,6,7,8)” means “to begin, weigh pencils # 1,2,3 and 4 against 5,6,7 and 8”.
• “0,-1: (1,2,5)-(3,6,9)” means “if the right side is heavier, weigh 1,2,3 against 3,6,9”.
• Each step has the label of the previous step, followed by -1 if the right side is heavier, 0 if they balance, and 1 if the left side is heavier.
• A line with a single number following the “:” means “the answer is “ the number.

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

For example, if the odd pencil is #6, and it’s heavier, the following would be executed:

 0: (1,2,3,4)-(5,6,7,8) =-1
 0,-1: (1,2,5)-(3,6,9) =-1
  0,-1,-1: (1)-(2) =0
   0,-1,-1,0: 6

Here’s the bit of MUMPS code I wrote to read in the algorithm code and apply it to a collection of pencils represented by A(1) … A(12):

r X2,X3 ;a couple of useful bits of code xecuted by the main program
n (A,R) s B=R,R=0 f I=1:1:(B,"+") s R=R+A((B,"+",I)) ;adds a string of pencils
f I=1:1:12 s A(I)=5 ;set all 12 pencils equal
k D f  r R,! q:R=""  s R=(R," "),@("D("_(R,":")_")=(R,"":"",2)") ;read the algorithm into something easy to reference
;paste the algorithm code here, followed by a blank line
f A1=6,4 f I1=1:1:12 x X3 s A(I1)=A1 w ! s N=(D(0)) f   s V=@N w ?(N),(N,3,(N)-1),": ",V q:V  s V=(V,",()","+"),R=(V,"-") x X2 s T=R,R=(V,"-",2) x X2 s T=T-R,N=(@N@(T>0-(T<0))) w " =",T,! ;the main program – shows the algorithm executing for a heavy or light pencil in each of the 12 positions

Here’s its output:

 0: (1,2,3,4)-(5,6,7,8) =1
 0,1: (5,6,1)-(7,2,9) =1
  0,1,1: (7)-(9) =0
   0,1,1,0: 1
0: (1,2,3,4)-(5,6,7,8) =1
 0,1: (5,6,1)-(7,2,9) =-1
  0,1,-1: (5)-(6) =0
   0,1,-1,0: 2
0: (1,2,3,4)-(5,6,7,8) =1
 0,1: (5,6,1)-(7,2,9) =0
  0,1,0: (3)-(4) =1
   0,1,0,1: 3
0: (1,2,3,4)-(5,6,7,8) =1
 0,1: (5,6,1)-(7,2,9) =0
  0,1,0: (3)-(4) =-1
   0,1,0,-1: 4
0: (1,2,3,4)-(5,6,7,8) =-1
 0,-1: (1,2,5)-(3,6,9) =1
  0,-1,1: (3)-(9) =0
   0,-1,1,0: 5
0: (1,2,3,4)-(5,6,7,8) =-1
 0,-1: (1,2,5)-(3,6,9) =-1
  0,-1,-1: (1)-(2) =0
   0,-1,-1,0: 6
0: (1,2,3,4)-(5,6,7,8) =-1
 0,-1: (1,2,5)-(3,6,9) =0
  0,-1,0: (7)-(8) =1
   0,-1,0,1: 7
0: (1,2,3,4)-(5,6,7,8) =-1
 0,-1: (1,2,5)-(3,6,9) =0
  0,-1,0: (7)-(8) =-1
   0,-1,0,-1: 8
0: (1,2,3,4)-(5,6,7,8) =0
 0,0: (9,10)-(8,11) =1
  0,0,1: (9)-(10) =1
   0,0,1,1: 9
0: (1,2,3,4)-(5,6,7,8) =0
 0,0: (9,10)-(8,11) =1
  0,0,1: (9)-(10) =-1
   0,0,1,-1: 10
0: (1,2,3,4)-(5,6,7,8) =0
 0,0: (9,10)-(8,11) =-1
  0,0,-1: (9)-(10) =0
   0,0,-1,0: 11
0: (1,2,3,4)-(5,6,7,8) =0
 0,0: (9,10)-(8,11) =0
  0,0,0: 12
0: (1,2,3,4)-(5,6,7,8) =-1
 0,-1: (1,2,5)-(3,6,9) =-1
  0,-1,-1: (1)-(2) =-1
   0,-1,-1,-1: 1
0: (1,2,3,4)-(5,6,7,8) =-1
 0,-1: (1,2,5)-(3,6,9) =-1
  0,-1,-1: (1)-(2) =1
   0,-1,-1,1: 2
0: (1,2,3,4)-(5,6,7,8) =-1
 0,-1: (1,2,5)-(3,6,9) =1
  0,-1,1: (3)-(9) =-1
   0,-1,1,-1: 3
0: (1,2,3,4)-(5,6,7,8) =-1
 0,-1: (1,2,5)-(3,6,9) =0
  0,-1,0: (7)-(8) =0
   0,-1,0,0: 4
0: (1,2,3,4)-(5,6,7,8) =1
 0,1: (5,6,1)-(7,2,9) =-1
  0,1,-1: (5)-(6) =-1
   0,1,-1,-1: 5
0: (1,2,3,4)-(5,6,7,8) =1
 0,1: (5,6,1)-(7,2,9) =-1
  0,1,-1: (5)-(6) =1
   0,1,-1,1: 6
0: (1,2,3,4)-(5,6,7,8) =1
 0,1: (5,6,1)-(7,2,9) =1
  0,1,1: (7)-(9) =-1
   0,1,1,-1: 7
0: (1,2,3,4)-(5,6,7,8) =1
 0,1: (5,6,1)-(7,2,9) =0
  0,1,0: (3)-(4) =0
   0,1,0,0: 8
0: (1,2,3,4)-(5,6,7,8) =0
 0,0: (9,10)-(8,11) =-1
  0,0,-1: (9)-(10) =-1
   0,0,-1,-1: 9
0: (1,2,3,4)-(5,6,7,8) =0
 0,0: (9,10)-(8,11) =-1
  0,0,-1: (9)-(10) =1
   0,0,-1,1: 10
0: (1,2,3,4)-(5,6,7,8) =0
 0,0: (9,10)-(8,11) =1
  0,0,1: (9)-(10) =0
   0,0,1,0: 11
0: (1,2,3,4)-(5,6,7,8) =0
 0,0: (9,10)-(8,11) =0
  0,0,0: 12 

Notice that, with this algorithm, if the odd pencil is in position 12, it takes only 2 weighings to find it. For all other positions, it takes 3.

 

Clever and hard as this problem is, I don’t think it can be left alone until a general algorithm for generating the algorithm for a collection of any number of pencils is written. Anyone in? I am. :P

[TheBigDog]

I can use 15 pencils and find the answer in 3 weighs.

 

#1) 1234 vs 5678

 

If one side is lighter you divide it in half and proceed, otherwise you take the next four and proceed.

 

#2) 12 vs 34 -or- 56 vs 78 -or- 9A vs BC

 

If one side is lighter you divide it in half and proceed, otherwise you take the next two and proceed.

 

#3) 1 vs 2 -or- 3 vs 4 -or- .... D vs E

 

If one side is lighter that is the answer, otherwise the unweighed pencil is the answer.

 

It will always take 3 tries to find the answer.

 

Bill

[CraigD]

I can use 15 pencils and find the answer in 3 weighs.

 

#1) 1234 vs 5678

 

If one side is lighter you divide it in half and proceed, otherwise you take the next four and proceed.

 

#2) 12 vs 34 -or- 56 vs 78 -or- 9A vs BC

 

If one side is lighter you divide it in half and proceed, otherwise you take the next two and proceed.

 

#3) 1 vs 2 -or- 3 vs 4 -or- .... D vs E

 

If one side is lighter that is the answer, otherwise the unweighed pencil is the answer.

 

It will always take 3 tries to find the answer.

But will it work if you only know that one pencil has a different weight, not whether its lighter or heavier? In the original 12-pencil puzzle, you don’t have this datum.

You have 12 pencils. 11 of them are exactly the same weight and the other one is either HEAVIER or LIGHTER.

Another interesting variation is to require that you must always weight all of the pencils (only works for even numbers of pencils, of course). For example, if the odd pencil is #9, you could find this in 5 tries as follows:

1+2+3+4+5+6-7-8-9-10-11-12 = -1

1+2+3+7+8+9-4-5-6-10-11-12 = 1

1+2+3+4+5+7-6-8-9-10-11-12 = -1

1+2+3+4+6+8-5-7-9-10-11-12 = -1

1+2+3+4+5+9-6-7-8-10-11-12 = 1

 

I’ve played with the general problem a bit. I’ve not started looking at the “generate an algorithm” problem yet, but have concluded that this is a knowledge-managing problem (More commonly known to the paper-and-pencil puzzle book consumer as a “logic problem”). For example, if we write what we know about the pencils as a list with “+” and “-“ in each position if we don’t know that that pencil is not either heavier or lighter than the others, finding a heavy #9 pencil looks like this:

+-,+-,+-,+-,+-,+-,+-,+-,+-,+-,+-,+-

1+2+3+4-5-6-7-8=0 : ,,,,,,,,+-,+-,+-,+-

9+10-8-11=1 : ,,,,,,,,+,+,-,

9-10=1 : ,,,,,,,,+,,,

[CraigD]

The example Bill gave in post #9 of a 15 pencil puzzle is in a special family of puzzles, those with [math]2^n-1[/math] pencils (where n is an integer).

 

Puzzles with [math]2^n-1[/math] pencils can be solved in n-1 tries if its known whether the target pencil is light or heavy, or n+1 tries if it’s not.

 

The following approach can be used to find a light target pencil in [math]2^n-1[/math] pencils in at most n-1 tries:

1. Weigh [math]2^{n-1}-1[/math] pencils against [math]2^{n-1}-1[/math] pencils, leaving 1 pencil out.
   
2. If one side is lighter (assuming we know the target pencil is light) than the other, repeat step 1 with those [math]2^{n-1}-1[/math] pencils, reducing n by 1
   
3. If the sides balance, the pencil left out is the target

By adding a check of the suspected target pencil against a control pencil, this approach can be expanded to find an target pencil that’s relative weight is unknown.

 

The code algorithm-describing code scheme in post #8 is a bit cumbersome, so I’ve replaced it with this new one:

• ”(1+2+3-4-5-6 7 8 9)” means “Weight pencil #1, 2, and 3 against #4, 5, and 6. If 1,2,3 are lighter than 4,5,6 the answer is 7. If they balance, the answer is 8. If 4,5,6 are lighter, the answer is 9.
  
• ”7”, “8”, or “9” in the above may be replaced with an algorithm, eg: “(1+2+3-4-5-6 (1-2 1 3 2) 7 (4-5 4 6 5))”
  
• Extra spaces and line breaks are ignored
  

Here’s the original 12-pencil algorithm:

(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)))

Here’s one for finding a light target out of 7:

(1+2+3-4-5-6
(1-2 1 3 2)
7
(4-5 4 6 5)) 

Here’s one for finding a target of unknown relative weight:

(1+2+3-4-5-6
(1-2 1 (1-3 error (4-5 5 6 4) 3) 2)
7
(4-5 4 (4-6 error (1-2 2 3 1) 6) 5))

Here’s one for finding an unknown relative weight target out of 15:

(1+2+3+4+5+6+7-8-9-10-11-12-13-14
(1+2+3-4-5-6
 (1-2 1 3 2)
 (1-7 error (8+9+10-11-12-13 (11-12 12 13 11) 14 (8-9 9 10 8)) 7)
 (4-5 4 6 5))
15
(8+9+10-11-12-13 
 (8-9 8 10 9)
 (8-14 error (1+2+3-4-5-6 (4-5 5 6 4) 7 (1-2 2 3 1)) 14)
 (11-12 11 13 12)))

Notice that the algorithm for [math]2^n-1[/math] is just a nesting and translation of the one for [math]2^{n-1}-1[/math], so these can be generated automatically.

 

Questions:

• Does an algorithm for finding a target in [math]2^n-1[/math] pencils better (maximum number of tries required less) exist for any n?
  
• We’ve demonstrated that for 12 pencils, a 3 maximum tries solution exists, one less that the number of tries for 8 pencils using the “half and repeat” approach. How can we generate regular algorithms for puzzles with other than [math]2^n-1[/math] pencils
  

 

PS: Here's MUMPS code that checks (x XPZL12(0,4))and demonstrates (x XPZL12(0,3)) algorithms in the new coding scheme:

n (XPZL12) f  r !,"[1]Demo classic puzzle [2]Demo knowledge representation [3]Demo Algorithm",!,"[4]Test Algorithm: ",R q:R=""  x XPZL12(0,(R=1:1,R=2:2,R=3:3,R=4:4,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 !,"Enter 1 or 2 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)
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)

[Mister Mario]

Technically, this is very similar to the problem with the scale, with one fake gold coin. Couldnt you use the same method?:confused:

[CraigD]

Welcome to hypography, Mister Mario!

Technically, this is very similar to the problem with the scale, with one fake gold coin. Couldnt you use the same method?

The puzzle is the same. Usually, the objects are called coins, but User2983 started this thread calling them pencils. What they’re called is, of course, unimportant.

 

Every puzzle I’ve seen specifies a specific number of objects, and either asks just for the maximum number of trials required, or how to conduct (an algorithm) the trials. What I’ve asked is for an algorithm for generating the algorithm for finding the unique object in at most the least number of trials given any number of objects – a “meta-algorithm”, as it were.

 

I describe an obvious meta-algorithm for the puzzle when the number of objects is [math]2^n-1[/math], ie: 1, 3, 7, 15, 31, 63, 127, etc. However, I’m not sure if a better meta-algorithm exists for this case, and I haven’t explored the case of then the number of objects is something other than [math]2^n-1[/math].

 

Any experience with or insight into this question?

[Qfwfq]

Technically, this is very similar to the problem with the scale, with one fake gold coin. Couldnt you use the same method?:shrug:

A remark that you should try to generalize and keep in mind when posting in future. There are only two cases, which exhaust the possibilities:

• The method for the gold coins is already known. In this case the suggestion of using the same method for pencils is absolutely obvious.
  
• The method for the gold coins is not already known. In this case the suggestion of using the same method for pencils is totally unhelpful.
  

 

Take 3 heavy pencils and 3 light pencils and weigh them against controls.

The trouble with this is that there are only 4 neutral ones but you would need 3 + 3 = 6 of them. I worked out a quite different method for the case in which the first weigh is not even, it's a bit more subtle:

 

The problem may be stated as having 8 balls and two allowed weighs left. With two plates for each weigh, that's 2 raised to the power 2 which is only 4, less than 8, so one must fully exploit having three possible outcomes in the remaining two weighs: even, or either of the two distinct possible imbalances. In the first weigh there is obviously not the distinction between one way or the other. Not yet, that is.

 

What I do is to keep 3 from one plate and 1 from the other, for the second weigh, but putting one of the three with the 1 (making two on each plate). If this inverts the imbalance compared to the first weigh it's the ball that crossed over and you don't need the third weigh. If the imbalance is the same way as before then compare the two that remained on the same plate and the three possible outcomes decide between the three that didn't cross plate.

 

If instead the second weigh gives even then you must use the third weigh to distinguish among those removed from the plates of the first weigh. Compare two of the three that were removed from the same plate. If the result is even it's the single one removed from one plate; otherwise it's one of the other two and you can determine which by comparing the imbalance with that of the first way.

 

As I was typing the last paragraph above, I was writing something different because I was already remembering wrong from my cryptic diagram of a few minutes before. Trying to get it right, I could no longer find the line of reasoning for quite a while because it's very subtle, I became quite convinced it was a false solution and was about to call it off before I got it again. I typed the whole thing very succinctly so it might be almost as much of a puzzle to figure out my meaning. :evil:

[Qfwfq]

Nope, the line of reasoning was so subtle it relied on confusing something with something else! :hyper: Well I was only goofing around in a bit of spare time, I only realized the mistake later that evening and I worked it out properly the next morning, by thinking of why that method was no good.

 

The case in which you're left with 4 = 3 + 1 clearly can't be resolved with the one remaining weigh if the result of it is even, that's what my bad was. Now the reason this case can happen is that there is the other case in which the third weigh isn't even necessary; this means I wasn't fully exploiting the available weighs, more exactly the 8 balls from the first weigh weren't distributed optimally into three sets. The right distribution is 8 = 2 + 3 + 3, with both of the 3's being 2 + 1. So, fro the second weigh, remove a ball from one plate and only two from the other and trade two balls between the plates (and even the plates with neutral balls).

 

Now if the balance tips the same way as the first time, consider the 2 + 1 that remained where they were. If it's even, keep the 2 + 1 that were removed. If it tips the opposite way, it's the two traded ones and it's enough to compare one of them with a neutral.

 

I tried to work out a general expression for the maximum number of balls that the problem could be solved for, given any number of available weighs, but it's a bit complicated and confusing.