Repeated operations on $(a,b)$ For each pair of integers $(a,b)$, define the sequence $S_{(a,b)}$ as:
If $a_{n-1} < b_{n-1}$ then $(a_{n},b_{n}) = (2a_{n-1},b_{n-1}+1)$; otherwise if $b_{n-1} < a_{n-1}$ then $(a_{n},b_{n}) = (a_{n-1}+1,2b_{n-1})$. If $a_n = b_n$ then we are done.
In other words, at each step we double the lesser and add one to the greater of $(a,b)$. We stop when $a_n = b_n$, i.e. we reach a pair $(c,c)$.
My question is: for any $a, b$ are we guaranteed to terminate at a pair $(c,c)$?
 A: I doubt that the termination at $(c,c)$ occurs for every pair. I just started with $(4,3)$ and got the following matrix showing the trajectory of the first couple of iterations as result. Here each row is one iterate of the initial pair and the difference between the elements of the pair:
$$\small \begin{array} {rr|r}
 a & b & a-b \\
\hline
 4 & 3 & 1 \\ 
 5 & 6 & -1 \\ 
 10 & 7 & 3 \\ 
 11 & 14 & -3 \\ 
 22 & 15 & 7 \\ 
 23 & 30 & -7 \\ 
 46 & 31 & 15 \\ 
 47 & 62 & -15 \\ 
 94 & 63 & 31 \\ 
 95 & 126 & -31 \\ 
 190 & 127 & 63 \\ 
 191 & 254 & -63 \\
 \vdots & \vdots & \vdots
 \end{array}$$
The differences (in the third column) follow an obvious pattern and without analyzing this in detail I'm confident that this initial pair of numbers has an infinite trajectory.           
[update]
If we look at the numbers along the trajectory of iterations, then it seems that the following is important.
Assume $a_0 \lt b_0$ . Then let's write all iterations while $a_j \lt b_j$ as one step and we want
$$ a_1=a_0 \cdot 2^{k}  >  b_1=b_0 + k >b_0 + k-1 >  a_0 \cdot 2^{k-1} >a_0 $$
We see, that $b_1$ lies in the interval of $a_1 .. a_1/2$. The next iteration, to build $b_2 = 2^j \cdot b_1 > a_1 + j$  needs then only a $j$ smaller than $k$ and along further iterations the required exponent at $2$ converges to $1$. So in the long run the transformation reduces to $a_{k+1} = 2 \cdot a_k , b_{k+1}=b_k+1 $  and vice versa $a_{k+2} = a_{k+1}+1 , b_{k+2}=2 \cdot b_{k+1} $ .            
I think, this is the crucial observation (and should be made more rigorous: there's a smallest $k$ from where the above rule is valid if not already $a=b$)
Then proceeding on this path, writing two steps  in one this is
 $$a_{k+2} = 2^1 \cdot a_k +1 \qquad \qquad b_{k+2}=2^1 \cdot b_k+2 \\
   a_{k+4} = 2^2 \cdot a_k +3 \qquad \qquad b_{k+4}=2^2 \cdot b_k+6 \\
   a_{k+6} = 2^3 \cdot a_k +7 \qquad \qquad b_{k+6}=2^3 \cdot b_k+14 \\
  $$ 
Generalizing this gives 
 $$a_{k+2r}+1 = 2^r \cdot (a_k+1) \\
 b_{k+2r}+2=2^r \cdot (b_k+2)$$ 
and this shows, that the differences $d_k=(b_k+2) - (a_k+1)$ expand to $d_{k+2r} = 2^r \cdot d_k$ (if not $a_k - b_k=1$).
And if the differences change, then the trajectories of $(a_k,b_k)$ cannot be constant.
If $a_k - b_k = 1$ at some $k$ then all the further differences are $1$ as well.
A: If you start with a pair of the form $(a, 2^ra - r)$, then you get $(2a, 2^ra- (r-1))$, ie a pair of the form $(a', 2^{r-1}a' -(r-1))$. So repeating the operation you will get a pair of the form $(c, c)$.
I claim this is the only way. Otherwise, we would have to get a pair of the form $(a, 2^ra - r)$ from something other than $(a/2, 2^ra - (r+1))$. The only possibility for this is $(a-1, \frac{2^ra - r}{2})$. But for $r\geq 2$, $a>0$ we have $\frac{2^ra - r}{2} > a$; when $r=1$ $2^ra - r$ is not divisible by 2; and when $r=0$ it's just $(a-1, a/2)$, so not actually different to the pair we know works.
