So far I have a lower bound of
and an upper bound of
For the upper bound, consider the following simple strategy:
- Ignore 0's
- If there's two $n$'s, change them to $n-1$ and $n+1$.
- Otherwise, create two 1's.
Let's keep ignoring 0's and pretend that we can add a single 1 for half a step. We argue that at any point, each number appears once, except at most one number appears twice. We need that invariant that whenever $n$ appears twice, $n-1$ does not appear. Then, when we replace $n,n$ with $n-1,n+1$, there's at most one $n-1$, at most two $n+1$'s, and no $n$'s appear, so the invariant is maintained.
The invariant is also maintained when we create a single $1$ because there are no pairs (remember we're ignoring 0's). In reality, when we create two ones, the invariant is maintained as long as we can ignore a single 1.
So, at the end when $100$ is created, there can be at most one of each number plus an extra 1. Moreover, there cannot be a double since we just acted on $99$ and there are not two $100$'s. And, there cannot be a 99. So, at most, the numbers $1$ through $100$ can appear, with no $99$ and an extra $1$.
By the invariant argument below, this end position correspond to this number of steps:
First, a weak lower bound for the number of steps it takes is
$5000 = 100^2 /2$
We look at the statistic
the sum of squares of the numbers on the whiteboard
Each move, causes the statistic
to increase by 2. Adding two 1's clearly does so. Replacing $n,n$ with $n-1,n+1$ changes the statistic as $(n+1)^2+(n-1)^2-n^2-n^2 = 2$.
This gives the lower bound because
the statistic starts at 0 and must end at least at $100^2$ for the number 100 to be on the board.
However, this lower bound cannot be sharp because
the number 100 cannot be left on the board alone. It must also appear with 98.
We can improve the lower bound to
observing that after the blackboard contains one of $a,a+1$, that fact must be true from then on, since removing an $a$ creates an $a+1$ and removing an $a+1$ creates an $a$. Since every number must be created on the way to $100$, the minimum possible statistic at the end is $100^2 + 98^2 + ... + 2^2 + 0^2$, which is $171700$, so the number of required moves is at least half of that.