Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
To clarify: The initial state is "empty text, empty clipboard", and the allowed operations are "press a letter key", "press Ctrl-C", "press Ctrl-V", "press Ctrl-A", but no other key presses are allowed (e.g. you cannot use Cursor movement keys for the side effect of unselecting the selected text). Also, the Ctrl combinations are always counted as two keypresses (so no keeping Ctrl pressed while pressing first A and then C). Moreover, if there's a current any inserting key (letter, Ctrl-V) replaces it and unselects the text. Is that right? –  celtschk Aug 8 '12 at 23:37
    
Right, but I don't get this sentence "Moreover, if there's a current any inserting key (letter, Ctrl-V) replaces it and unselects the text." –  no identity Aug 8 '12 at 23:45
    
The "current" should have been a "current selection". That is, if something (with your restrictions, always the complete text) is selected, then trying to add something instead replaces the selected text. –  celtschk Aug 9 '12 at 0:01
    
yes, exactly${}{}$ –  no identity Aug 9 '12 at 0:07

2 Answers 2

up vote 6 down vote accepted

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$.

share|improve this answer
    
Nice. Can you work out any asymptotics for $f(n)$? For larger $n$, might you achieve the maximum by typing and then multiplying by three numbers, instead of by two? –  Gerry Myerson Aug 9 '12 at 23:37
    
@Gerry: something added –  Henry Aug 10 '12 at 9:07
    
Good. Thanks!$$ –  Gerry Myerson Aug 10 '12 at 9:35

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.

share|improve this answer
1  
@AustinMohr: Your "fix" was wrong: Pasting directly after copying replaces the text with itself (as I described above), which is why I included the first paste into the vopy operation (that is, the copy operation here is the sequence "Ctrl-A Ctrl-C, Ctrl-V" and leaves the text unchanged and unselected, but changes the clipboard to a copy of the text. –  celtschk Aug 9 '12 at 8:33
    
I see my error now. Sorry for the oversight. –  Austin Mohr Aug 9 '12 at 17:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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