Weigh [1, 2, 3, 4 and 5, 6, 7, 8]:
 if left heavier then 
  Weigh [3, 8, 9 and 4, 6, 7]:
   if left heavier then 
    last weighting [1, 7, 8, 9 and 2, 4, 5, 6]:
     if left heavier then fake is 6
     if left lighter then fake is 7
     if equal then fake is 3
   if left lighter then 
    last weighting [1, 7, 8, 9 and 2, 3, 5, 6]:
     if left lighter then fake is 8
     if equal then fake is 4
   if equal then 
    last weighting [1, 7, 8, 9 and 2, 3, 4, 6]:
     if left heavier then fake is 1
     if left lighter then fake is 2
     if equal then fake is 5
 if left lighter then 
  Weigh [3, 8, 9 and 4, 6, 7]:
   if left heavier then 
    last weighting [1, 7, 8, 9 and 2, 3, 5, 6]:
     if left heavier then fake is 8
     if equal then fake is 4
   if left lighter then 
    last weighting [1, 7, 8, 9 and 2, 4, 5, 6]:
     if left heavier then fake is 7
     if left lighter then fake is 6
     if equal then fake is 3
   if equal then 
    last weighting [1, 7, 8, 9 and 2, 3, 4, 6]:
     if left heavier then fake is 2
     if left lighter then fake is 1
     if equal then fake is 5
 if equal then fake is 9