8
$\begingroup$

You have an empty blackboard. At each step, you can either write two ones on the blackboard, or erase two copies of a number n and replace them with n−1 and n+1.

What is the fewest number of steps it takes to write 100 on the board?

$\endgroup$
2
  • $\begingroup$ I assume that the [lateral-thinking] answer of having a 1, 0, and 0 side-by-side doesn't count? :) $\endgroup$ – bobble May 14 at 19:03
  • $\begingroup$ @bobble, nice idea, but right, this does not count! $\endgroup$ – ThomasL May 14 at 19:07
6
$\begingroup$

I think the answer is

$164275$.

The closed formula solution is

$a_n = \frac 1 {12}(2n^3 - 3n^2 + 13n - 3) + \frac14(-1)^{\lfloor \frac n 2\rfloor}$.

It can be shown that the following "greedy" algorithm is always the best: always take the largest two identical numbers and transform them. If there are no identical numbers $\geq $1, then add two $1$'s.
Then it is just a matter of counting the number of steps in this algorithm.

$\endgroup$
2
  • 1
    $\begingroup$ Your formula looks good. How did you find it? $\endgroup$ – ThomasL May 14 at 22:16
  • 2
    $\begingroup$ I bruteforced the first several terms and then found a linear recurrence relation. Proving it should not be much trouble. $\endgroup$ – WhatsUp May 14 at 22:38
0
$\begingroup$

Taking the algorithm of @WhatsUp for granted, counting more constructively:

We can reorder our steps to take all the steps that write two ones before any other steps (or, equivalently, suppose we have an inexhaustible supply of ones). Then consider what happens at each subsequent step to our set of numbers ignoring zeros and ones.

If we just have a consecutive sequence from $2$ to $k$, then in $k$ steps, we will produce $k + 1$ leaving behind one copy of each of $2$ to $k - 1$, but no copy of $k$. But then $k - 1$ steps will change this new initial sequence into $k$ leaving behind $2$ to $k - 2$. This will repeat until all the holes are filled, taking $T_k = 1 + \dots + k$ steps. ($T_k$ is the $k$-th triangular number.) Note, it also takes just $1 = T_1$ step to get from the empty set to just $2$.

Thus, to get from the empty set to the consecutive sequence from $2$ to $k$ takes $Te_{k-1} = T_1 + \dots + T_{k-1}$ steps. ($Te_k$ is the $k$-th tetrahedral number.)

The number of one pairs we have to write on the board to get the sequence from $2$ to $k$ is easy to count, as the other operation preserves the sum of all the numbers (and we produce no negative numbers). So the number of pairs of ones is $\lceil \frac{1}{2}(2 + \dots + k) \rceil = \lceil\frac{1}{2}(T_k - 1)\rceil = \lfloor \frac{1}{2} T_k \rfloor$.

So, to count the total number of steps to get to the first $k$, we count the number of steps to get from the empty set to all the numbers from $2$ to $k - 1$ plus the number of one pairs needed to produce this plus one more one pair plus the number of steps needed to then produce the $k$. So, our formula is $Te_{k-2} + \lfloor \frac{1}{2} T_{k-1} \rfloor + k = {k \choose 3} + \lfloor \frac{1}{2}{k \choose 2}\rfloor + {k \choose 1}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.