Runtime of the binary-GCD state machine
Unless I've done this example wrong, this question is asking you to prove something that isn't true. Consider $(x,y) = (381,192) = (3\cdot 127,3\cdot 64)$. What happens when you run the algorithm?


  $(3\cdot127,3\cdot 64,1) \rightarrow (3\cdot127,3\cdot 32,1) \rightarrow \ldots \rightarrow (3\cdot 127,3,1)$
  $ (3\cdot 127,3,1) \rightarrow (3\cdot 126,3,1) \rightarrow (3\cdot 63,3,1) \rightarrow \ldots \rightarrow (3,3,1) $
  $ (3,3,1) \rightarrow (1,0,3) $  


So starting with $( 3\cdot (2^k -1), 3 \cdot 2^{k-1}, 1)$, the first set of steps applies the 5th rule $k-1$ times, resulting in $(3 \cdot (2^k-1), 3, 1)$. We then alternately apply the 7th rule and the 6th rule. Each time we do this, we go from $(3\cdot (2^j-1),3,1)$ to $(3\cdot (2^{j-1}-1),3,1)$, until we reach $(3\cdot(2^1-1),3,1)$. This takes $2(k-1)$ transitions. Finally, we apply the 1st rule once, for a total of $3k-2$ transitions. But the original value has $\log_2 \max(x,y) \approx {k}$, so we needed
$3 \log_2 \max(x,y) - C$ transitions total for some constant $C$. 

It's certainly true, and not hard to prove, that the algorithm runs in $O(\log \max(x,y))$. But the question has the constant wrong.