You are given an empty blackboard. Once a minute, you are allowed to do one of the following:
Here is an example of six possible moves: $$ empty\to 1,1 \to 0,2\to 0,2,1,1\to 0,2,0,2\to 0,1,0,3\to -1,1,1,3\to\cdots $$
What's the shortest time it takes to write $100$ on the board?
The shortest amount of time it takes to write the number $100$ is
$164275$ minutes. xnor has already described a process for reaching $100$ in $164275$ minutes, so here I will argue that it cannot be done faster.
I will need to following fact.
Claim: Let $k$ be a non-negative integer. If there has ever been an integer $n>k$ written on the board, then for any interval of $k+1$ consecutive positive integers less than or equal to $n$, there are at least $k$ integers from that interval currently written on the board.
The special case $k=1$ was observed by xnor (once a number has appeared, at least one of every pair of consecutive smaller numbers must always be on the board).
Proof: Induction on $k$. The base case $k=0$ is vacuously true.
Now, let $k$ be arbitrary, and assume the claim holds for $0,1,\ldots,k-1$. Suppose some integer $n>k$ has appeared on the blackboard at some point. Let $I=\{a+1,\ldots,a+k\}$ be a set of $k$ consecutive positive integers, with $a+k\leq n$. At some point in time $a+k$ must have been written on the board, and at that time there were at least $k$ numbers from $I$ written on the board: the integer $a+k$, along with $k-1$ integers from $\{a+1,\ldots,a+(k-1)\}$ (here we use the inductive hypothesis).
Given that $k$ integers on the board were in $I$ at some point, we can argue that $k$ integers on the board are in $I$ at all times. The only time that the number of integers on the board that are in $I$ decreases is when we replace two copies of $a+k$ by $a+k+1$ and $a+k-1$, or when we replace two copies of $a+1$ by $a$ and $a+2$. However, in the first case, there were already $k-1$ integers on the board from the interval $\{a+1,\ldots,a+k-1\}$ before the replacement (by the inductive hypothesis), so along with the new $a+k-1$, that makes a total of $k$ integers $I$. The second case is identical.
This completes the proof of the claim.
Suppose $100$ is written on the blackboard. Then the blackboard must also contain: at least one number from $\{99,98\}$, at least two numbers from $\{99,98,97\}$, and so on, up through $98$ numbers from $\{99,98,\ldots,1\}$. This means that the smallest possible value for the sum of the squares of the numbers on the board is $$ 100^2+98^2+97^2+96^2+\ldots+1^2=328549. $$ As xnor has explained, the sum of the squares of the integers on the blackboard increases by $2$ each minute, so the number of minutes required is at least $$ \left\lceil\frac{328549}{2}\right\rceil=164275. $$ This is what we needed to show.
So far I have a lower bound of
$85850$
and an upper bound of
$164275$
For the upper bound, consider the following simple strategy:
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:
$164275$ 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
$85850$
by
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.
