Question about swindler-writer

Question

This question arose from my curiosity.

In one particular publishing house writer's salary depends on the amount of text he produces $-$ $p=20$ dollars for $s=1800$ symbols.

How much money can earn a swindler-writer by pressing $n=40$ buttons on the keyboard?

Writer can use Ctrl+C, Ctrl+V and Ctrl+A, but he can't copy text from other sources.

For example combination Ctrl+A Ctrl+C Ctrl+V changes nothing in text, but you waste $6$ "pressings" of buttons. Meanwhile combination Ctrl+A Ctrl+C Ctrl+V Ctrl+V doubles amount of text.

I think the best way is to type a small text, and then several times perform the following procedure: select all via Ctrl+A and copy-paste several times. The problem is to determine amount procedures and amounts of times which he should copy-paste at each procedure.

I'm also interested in solution for arbitrary values of $n$,$s$,$p$, but I think it is too hard.

Answer 1

It turns out that for $40$ button presses the maximum number of characters is $300$ (worth about $3.33), which can be achieved a number of different ways.

The recursion is $$f(n)= \max \{\,f(n-1)+1, \max_j \{j \times f(n-4-2j)\}\,\}$$ starting with $f(0)=0$ since you can type an extra character or do Ctrl-A, Ctrl-C and then Ctrl-V $j$ times.

For $n=40$, possibilities are

• abcdefghij Ctrl-A Ctrl-C Ctrl-V Ctrl-V Ctrl-V Ctrl-V Ctrl-V Ctrl-A Ctrl-C Ctrl-V Ctrl-V Ctrl-V Ctrl-V Ctrl-V Ctrl-V by typing $10$ characters and then multiplying by $5$ (14 keystrokes) and then by $6$ (16 keystrokes)
• abcdefghij Ctrl-A Ctrl-C Ctrl-V Ctrl-V Ctrl-V Ctrl-V Ctrl-V Ctrl-V Ctrl-A Ctrl-C Ctrl-V Ctrl-V Ctrl-V Ctrl-V Ctrl-V by typing $10$ characters and then multiplying by $6$ (16 keystrokes) and then by $5$ (14 keystrokes)
• abcdefghijkl Ctrl-A Ctrl-C Ctrl-V Ctrl-V Ctrl-V Ctrl-V Ctrl-V Ctrl-A Ctrl-C Ctrl-V Ctrl-V Ctrl-V Ctrl-V Ctrl-V by typing $12$ characters and then multiplying by $5$ (14 keystrokes) and then by $5$ (14 keystrokes)

Added

For large $n$ we are interested in how much exponential growth is provided by multiplying by $j$ using $4+2j$ keystrokes, in effect multiplying by $j^{1/(4+2j)}$ each keystroke; for real $j$ this is maximised by $j \approx 4.319$, but for integer $j$ by $j = 4$ in which case $f(n)=4f(n-12)$, and this turns out to apply when $n \ge 67$. So in the long run, the optimal answer is to keep multiplying by $4$ by using $12$ keystrokes

Indeed for $n \ge 67$ we have $f(n)= k \times 2^{n/6}$ where $k$ depends on the remainder after dividing $n$ by $12$ and the various $k$ lie in the range $(3.05,3.182)$.

For example if $n$ is a multiple of $12$ then $k=\frac{25}{8}=3.125$ and we can say $f(12m)=50 \times 4^{m-2}$ for integer $m\ge 2$. To get this, type $10$ characters, a multiplication by $5$ and $m-2$ multiplications by $4$; it does not matter when the multiplication by $5$ happens in the multiplications by $4$.

Answer 2

Given the restrictions, one can make the following observations:

• The only reason to select the text is to copy it, therefore one can assume that each Ctrl-A is immediately followed by a Ctrl-C. Moreover, Ctrl-C without preceding Ctrl-A is pointless.
• After Ctrl-C, the only sensible thing to do is Ctrl-V, because all other keys in that situation either change nothing or replace the text with a single letter. (The only exception would be if the copied text would be a single letter, but then the whole copy would be pointless). Moreover, that first paste doesn't change the text (because it replaces it with the copy just generated).

Therefore one can handle "Ctrl-A Ctrl-C Ctrl-V" as an atomic sequence to copy the text into the clipboard.

Since we are only interested in the length of the text, the text and clipboard can be represented by the numbers of characters.

We therefore effectively have the following three operations:

• Add letter ($t\leftarrow t+1$, cost 1)
• Copy to clipboard, includes the first non-text-changing paste ($c\leftarrow t$, cost 6)
• Paste from clipboard ($t\leftarrow t+c$, cost 2)

Now the following observation can be made: As soon as there are more than 2 characters in the clipboard, it is more effective to paste than to type a letter. Therefore typing letters is only effective until the first copy has been done (after typing at least two letters). Moreover, except for typing a letter, all operations have an even cost, so the number of letters initially types must have the same parity as the maximal number $n$ (for $n=40$, there must be an even number of key presses).

Moreover, consider the sequence "paste, copy, paste$^n$" vs. "copy, paste, paste$^n$". The first one has the effect $(t,c)\mapsto((n+1)(t+c),t+c)$, the second one has the effect $(t,c)\mapsto((n+2)t,t)$. So the second leads to a longer text if $(n+2)t>(n+1)(t+c)$, that is $t>(n+1)c$. Now if the previous copy was followed by $k$ pastes, then $t=(k+1)c$, and therefore the condition reduces to $k>n$. That is, if the sequence of pastes is decreasing, it is advanteous to shift the paste backwards. Or in other words, for the ideal sequence the number of pasts after consecutive copies never decreases. Analogously, it also should not be increasing (because then a shift to the right is advantageous).

Now let's look at the ideal "copy $k$ times" strategy. For $k=0$ there's not much to optimize; you'll always get $k$ letters. For $k=1$, you have initially $m$ letters, then a 6 key copy sequence, and then $(n-6-m)/2$ paste sequences, resulting in $m(n-m-4)/2$ letters. So we have to maximize $m(n-m-5)$ which means minimizing the difference $\left|m-(n-m-5)\right|=\left|2m+5-n\right|$. In other words, $m$ must be as close as possible to $(n-5)/2$ (however should still have the right parity). For example, with $n=14$, we get $(n-5)/2=4.5$, the closest even number to this is $4$. Therefore the optimal $k=1$-strategy is to type 4 letters, copy, and then paste 2 times, giving a total of 12 letters; here the letters-only strategy clearly wins. For $n=19$, we have $(n-5)/2=7$ which is already odd and thus the optimum. This gives 28 letters by typing 7 letters, copying, and pasting 3 times.

Now $n=19$ would also allow for copying twice. However the only reasonable sequence, type 3 letters, copy, paste, copy, paste, gives just 12 letters, far less than the 28 from a single-copy strategy.

OK, and now it's so late in the night that I'll stop here.