The following $100$ numbers are written on the board:$$2^1 - 1, 2^2 - 1, 2^3 - 1, \dots, 2^{100} - 1.$$ Alice chooses two numbers $a,b,$ erases them and writes the number $\dfrac{ab - 1}{a+b+2}$ on the board. She keeps doing this until a single number remains on the board. If the sum of all possible numbers she can end up with is $\dfrac{p}{q}$ where $p, q$ are coprime, then what is the value of $\log_{2}(p+q)$?
Since many of these types of questions uses invariants, I was trying to find an invariant. But I'm unable to find it. I would like someone to provide hints.
If we let $a_i$ be the numbers left on the board at any stage, then $$\Delta=\sum\limits_{i}\frac{1}{a_i+1}$$ is invariant.
Note that if $a,b$ are replaced at a stage by $\frac{ab-1}{a+b+2}$, then $\frac1{a+1}+\frac1{b+1}$ is changed to $\frac{1}{\frac{ab-1}{a+b+2}+1}=\frac1{\frac{(a+1)(b+1)}{a+b+2}}=\frac1{a+1}+\frac1{b+1}$.
What is this sum $\Delta$? It is equal to $\frac{2^{100}-1}{2^{100}}$, because it is invariant under this process and therefore, it shouldn't have changed from what we started with.
If the last no. on the board is $L$, then $$\Delta=\frac1{L+1}=\frac{2^{100}-1}{2^{100}}$$
$$\implies L=\frac{1}{2^{100}-1}=\frac p q.$$
We need $\mathrm{log}_2(p+q)$ which is $100$.
I noticed that applying $\frac{ab-1}{a+b+2}$ to $a=2^i-1,b=2^j-1$ always managed to clear the $-1$s and left me with a perfect power of $2$. So, I figured there had to be something involving $a+1,b+1$. So, I wrote the $\frac{ab-1}{a+b+2}$ as $\frac{ab-1}{(a+1)+(b+1)}$.
I also noticed that $ab-1=(a+1)(b+1)-((a+1)+(b+1))$. Using this, I wrote $\frac{ab-1}{a+b+2}+1=\frac{(a+1)(b+1)}{(a+1)+(b+1)}=\frac{1}{\frac{(a+1)+(b+1)}{(a+1)(b+1)}}=\frac{1}{\frac{1}{a+1}+\frac 1{b+1}}$.
I wrote $\frac{ab-1}{a+b+2}+1=\frac{1}{\frac{1}{\frac{ab-1}{a+b+2}+1}}$ and I knew I had the invariant. I guessed the $\Delta$ with this.