Let's define our two possible moves as follows:
- A paste (P) adds the number of characters in the clipboard to the message,
taking 1 step.
- A copy (C) sets the number of characters in the clipboard to equal the number
of characters in the message, taking 3 steps (select-all, copy, select-end). (Side
note: you can do the same thing with select-all, copy, paste - you'll paste over
your selected text, replacing it with itself. Side note 2: I'm using a different
definition of "copy" than others: I'm not including the paste in the copy.)
The question is, if you start with 1 character in the message and 1 character in the
clipboard, how many steps (minimum) will it take to get at least 1000 characters in
the message?
The sequence of moves (Ps and Cs) we use is optimally going to look something like
this:
PPPCPPCPCPPPCP
(It's useless to start or end with a C, and putting two Cs next to each other is
equally useless). So, optimally, we will do $a_1$ Ps, followed by a C, followed by
$a_2$ Ps, followed by a C, etc., ending with a C and $a_m$ Ps, where each $a_i \ge 1$. The number of steps used in this way is
$$
a_1 + a_2 + \cdots + a_m + 3(m-1). \tag{1}
$$
Now, let $K_n$ be the position with $n$ characters in the message and $n$ characters
in the clipboard. From $K_n$, if we use $a$ Ps in a row followed by a C, we end up
at position $K_{n(a+1)}$. We may assume we get a free copy move at the very end (it
won't improve the number of characters in the message), so that our final position
is $K_A$, where $A$ is given by
$$
(a_1 + 1)(a_2 + 1)\cdots(a_m + 1) \tag{2}
$$
We want to maximize (2), while at the same time minimizing (1). More concretely, if
we can change the $a_i$s to both decrease (1) and increase (2), this is definitely
good. Using this idea, we observe:
- An even $a \ge 8$ should be replaced by $1$ and $\frac{a}{2}$. In (2), we improve
since $(a + 1) \le (1 + 1)(\frac{a}{2} + 1)$. In (1) we improve since $a \ge 1 +
\frac{a}{2} + 3$. (The $+ 3$ comes from $m$ increasing by $1$.)
- An odd $a \ge 7$ should be replaced by $1$ and $\frac{a-1}{2}$. We have $(a + 1)
\le (1 + 1)(\frac{a-1}{2} + 1)$ and $a \ge 1 + \frac{a-1}{2} + 3$.
- If $a$ and $a'$, with $a < a'$ are at least two apart, we should replace them with $a + 1$ and $a' - 1$. We have $(a + 1)(a' + 1) \le (a + 2)(a')$ and $a + a' \ge (a + 1) + (a' - 1)$.
The above three simplifications, when applied as many times as we need, give us a final set of $a_1,a_2,\dots,a_m$ which all belong to $\{1,2,3,4,5,6\}$ and contain no two $a_i$s two or more apart. In other words, it is optimal to use either $1$s and $2$s only, $2$s and $3s$ only, $3$s and $4$s only, $4$s and $5$s only, or $5$s and $6$s only. But we can go further. One can verify that, in the (multi)set $a_1,a_2,\dots,a_m$:
- $1,1$ can be replaced by $3$
- $1,2$ can be replaced by $5$
- $5,5$ can be replaced by $2,2,3$
- $6,6$ can be replaced by $3,3,3$
Thus, optimally, we use at most one $5$, at most one $6$ and at most one $1$.
Also, since we can't use both $1$s and $2$s, $1$s are pretty much useless (the only time $a_i = 1$ is okay is if there is only one $a_i$ total).
This throws out the case where we use only $1$s and $2$s.
Finally, using only $5$s and $6$s we can get at most $(5 + 1)(6 + 1) = 42$, which is much less than $1000$, so we'll throw out this case as well. We're left with just three cases: we use $2$s and $3$s, we use $3$s and $4$s, or we use $4$s and at most one $5$.
At this point, let's assume we use only $b$s and $b+1$s, where $b \in \{2,3,4\}$.
Let $a_i = b$ for $j$ values of $i$, and let $a_i = b + 1$ for $k$ values of $i$.
Then from (1), we need to minimize
$$
(b)j + (b + 1)k + 3(j + k - 1) = (b + 3)j + (b + 4)k - 3 \tag{3}
$$
Given that (2) is at least $1000$, i.e.
$$
(b + 1)^j (b + 2)^k \ge 1000. \tag{4}
$$
We separate into cases on $b$ to complete the work.
Case 1: $b = 2$
Here (4) becomes $3^j 4^k \ge 1000$.
Given a fixed $k$, we want to pick the smallest $j$ for which this holds true.
Also, picking $k > 5$ is pointless since $4^5 > 1000$ already.
\begin{array}{|c|c|c|}
\hline
k & \text{Smallest } j & 3^j 4^k & \text{Steps used (3): } 5j + 6k - 3
\\ \hline
0 & 7 & 2187 & 32
\\ \hline
1 & 6 & 2916 & 33
\\ \hline
2 & 4 & 1296 & 29
\\ \hline
3 & 3 & 1728 & 30
\\ \hline
4 & 2 & 2304 & 31
\\ \hline
5 & 0 & 1024 & 27
\\ \hline
\end{array}
Case 2: $b = 3$
(4) becomes $4^j 5^k \ge 1000$.
Given a fixed $k$, we want to pick the smallest $j$ for which this holds true.
Picking $k > 5$ is pointless since $5^5 > 1000$ already.
We assume $k > 0$ since $k = 0$ is encompassed in Case 1.
\begin{array}{|c|c|c|}
\hline
k & \text{Smallest } j & 4^j 5^k & \text{Steps used (3): } 6j + 7k - 3
\\ \hline
1 & 4 & 1280 & 28
\\ \hline
2 & 3 & 1600 & 29
\\ \hline
3 & 2 & 2000 & 30
\\ \hline
4 & 1 & 2500 & 31
\\ \hline
5 & 0 & 3125 & 32
\\ \hline
\end{array}
Case 3: $b = 4$
(4) becomes $5^j 6^k \ge 1000$.
We observed before that $k \ge 2$ is suboptimal.
Also, $k = 0$ was encompassed in Case 2.
Thus our table is very simple:
\begin{array}{|c|c|c|}
\hline
k & \text{Smallest } j & 5^j 6^k & \text{Steps used (3): } 7j + 8k - 3
\\ \hline
1 & 4 & 3750 & 33
\\ \hline
\end{array}
$$
* \quad * \quad *
$$
Having gone through all the cases, we can see that indeed 27 steps is the best we can do. Our strategy is PPPCPPPCPPPCPPPCPPP, and we end up with 1024 characters.
Final Comments:
The final computation was a little gross, but considerably easier than expected (and doable by hand!).
This method - reducing to the cases $b = 2$, $b = 3$, and $b = 4$, and then checking each one - should be easy to program on a computer for a general $N$ desired number of characters (we did $N = 1000$ here).
There will be about $\log_4 N$ rows in the first table, $\log_5 N$ rows in the second table, and $1$ row in the third table; hence the algorithm will take
total time $\log_4 N + \log_5 N + 1$, or simply $O(\log N)$, which is pretty much as efficient as we could ask for.
