Problem A. 893. (December 2024)
A. 893. In a text editor program, initially there is a footprint symbol (L) that we want to multiply. Unfortunately, our computer has been the victim of a hacker attack, and only two functions are working: Copy and Paste, each costing \(\displaystyle 1\) Dürer dollar to use. Using the Copy function, we can select one or more consecutive symbols from the existing ones, and the computer memorizes their number. When using the Paste function, the computer adds as many new footprint symbols to the sequence as were selected in the last Copy. If no Copy has been done yet, Paste cannot be used. Let \(\displaystyle D(n)\) denote the minimum number of Dürer dollars required to obtain exactly \(\displaystyle n\) footprint symbols. Prove that for any positive integer \(\displaystyle k\), there exists a positive integer \(\displaystyle N\) such that \(\displaystyle D(N)={D(N+1)}+1={D(N+2)}={D(N+3)}+1={D(N+4)}=\ldots ={D(N+2k-1)}+1={D(N+2k)}\).
Based on a problem of the Dürer Competition
(7 pont)
Deadline expired on January 10, 2025.
Let's divide the steps into blocks: a block starts with a Copy and ends just before the next Copy, meaning each block contains exactly one Copy as its first step. First, we show that for any \(\displaystyle n\), it is possible to reach \(\displaystyle n\) footprints with \(\displaystyle D(n)\) steps such that every block has a maximum size of 3.
Assume indirectly that this is not true, and there exists a number \(\displaystyle n\) for which any sequence achieving \(\displaystyle n\) footprints with a cost of \(\displaystyle D(n)\) contains at least one block of size 4 or more. Consider a sequence that produces \(\displaystyle n\) footprints in \(\displaystyle D(n)\) steps, where the longest block has minimal length \(\displaystyle k \geq 4\).
Take a block of length \(\displaystyle k\), consisting of one Copy followed by \(\displaystyle k-1\) Pastes. Instead, perform the Copy as before, but only \(\displaystyle k-3\) Pastes (where \(\displaystyle k-3 \geq 1\)), then Copy twice as many characters as initially copied in the block and Paste once. This uses the same number of steps and results in the same number of footprints but splits the block into two shorter blocks. Applying this to all blocks of length \(\displaystyle k\) reduces the maximum block length, leading to a contradiction. Thus, we conclude that from now on, we can assume every block has at most length 3.
Based on this, we show that \(\displaystyle D(n)\) satisfies the following recursion for \(\displaystyle n \geq 2\).
\(\displaystyle D(n)=\min\left(2+\min_{n/2 \leq k <n} D(k), \ \ 3+\min_{\substack{n/3 \leq k <n \\ 2 \mid n-k}} D(k)\right). \)
This holds because when expressing \(\displaystyle n\) with blocks of at most length 3, the last block is either of length 2 or 3. In the first case, before the last block, we must have at least \(\displaystyle n/2\) footprints, and with two additional steps, we can produce the remaining footprints. In the second case, achieving exactly \(\displaystyle n\) footprints with a block of length 3 requires at least \(\displaystyle k \geq n/3\) footprints beforehand and that \(\displaystyle 2 \mid n-k\) to be able to reach exactly \(\displaystyle n\) footprints with Pasting the same number of footprints twice.
By examining small cases, we can conjecture the general formula for \(\displaystyle D(n)\), valid for \(\displaystyle n \geq 4\). Let \(\displaystyle k\) be the unique positive integer such that \(\displaystyle 3^k + 1 \leq n \leq 3^{k+1}\). We further partition this interval:
- If \(\displaystyle 3^k + 1 \leq n \leq 3^k + 3^{k-1}\), then \(\displaystyle D(n) = 3k + 1\),
- If \(\displaystyle 3^k + 3^{k-1} + 1 \leq n \leq 2 \cdot 3^k\), then \(\displaystyle D(n) = 3k + 2\),
- If \(\displaystyle 2 \cdot 3^k + 1 \leq n \leq 2 \cdot 3^k + 2 \cdot 3^{k-1}\), then \(\displaystyle D(n) = 3k + 3\),
- If \(\displaystyle 2 \cdot 3^k + 2 \cdot 3^{k-1} + 1 \leq n \leq 3^{k+1}\), then \(\displaystyle D(n) = 3k + 3\) if \(\displaystyle 2 \nmid n\), and \(\displaystyle D(n) = 3k + 4\) if \(\displaystyle 2 \mid n\).
It is evident that in the last case, \(\displaystyle 3k + 3\) and \(\displaystyle 3k + 4\) alternate. Hence proving this formula for \(\displaystyle D(n)\) would complete the solution.
Using the recursive formula, proving the formula by induction on \(\displaystyle k\) is straightforward. For the base case, we verify \(\displaystyle D(1) = 0\), \(\displaystyle D(2) = 2\), \(\displaystyle D(3) = 3\), \(\displaystyle D(4) = 4\), \(\displaystyle D(5) = D(6) = 5\), \(\displaystyle D(7) = D(8) = D(9) = 6\), confirming the statement for \(\displaystyle k=1\), i.e., when \(\displaystyle 3^1 + 1 \leq n \leq 3^2\).
Now assume the formula holds for all \(\displaystyle n \leq 3^k\) and prove it for \(\displaystyle 3^k + 1 \leq n \leq 3^{k+1}\).
- If \(\displaystyle 3^k + 1 \leq n \leq 3^k + 3^{k-1}\), then \(\displaystyle 3^{k-1} + 3^{k-2} < \frac{n}{2} \leq 2 \cdot 3^{k-1}\), which shows that if we want a construction where the last block has length two, the best we can achieve is \(\displaystyle 3k + 1\). Furthermore, since \(\displaystyle 3^{k-1} < \frac{n}{3} \leq 3^{k-1} + 3^{k-2}\), even with a block of length three at the end, we cannot achieve better than \(\displaystyle 3k + 1\). Therefore, in this case, \(\displaystyle D(n) = 3k + 1\) holds.
- If \(\displaystyle 3^k + 3^{k-1} + 1 \leq n \leq 2 \cdot 3^k\), then \(\displaystyle 2 \cdot 3^{k-1} < \frac{n}{2} \leq 3^k\), which implies that if the last block has length two, we cannot achieve better than \(\displaystyle 3k + 2\). This value can indeed be reached by first creating \(\displaystyle 3^k\) footprints in \(\displaystyle 3k\) steps and then performing one Copy-Paste operation to generate the remaining required footprints. Moreover, since \(\displaystyle 3^{k-1} + 3^{k-2} < \frac{n}{3} \leq 2 \cdot 3^{k-1}\), even with a final block of length three, achieving better than \(\displaystyle 3k + 2\) is impossible. Thus, \(\displaystyle D(n) = 3k + 2\) in this case.
- If \(\displaystyle 2 \cdot 3^k + 1 \leq n \leq 2 \cdot 3^k + 2 \cdot 3^{k-1}\), then \(\displaystyle 3^k < \frac{n}{2} \leq 3^k + 3^{k-1}\), and also \(\displaystyle 2 \cdot 3^{k-1} < \frac{n}{3} \leq 2 \cdot 3^{k-1} + 2 \cdot 3^{k-2}\). Similarly to the previous cases, neither a final block of length two nor three can achieve fewer than \(\displaystyle 3k + 3\) steps, but this value is attainable with a final block of length two. Therefore, \(\displaystyle D(n) = 3k + 3\) in this case.
- Finally, if \(\displaystyle 2 \cdot 3^k + 2 \cdot 3^{k-1} + 1 \leq n \leq 3^{k+1}\), then \(\displaystyle 3^k + 3^{k-1} < \frac{n}{2} \leq 2 \cdot 3^k\), so with a final block of length two, the best achievable value is \(\displaystyle 3k + 4\). Additionally, since \(\displaystyle 2 \cdot 3^{k-1} + 2 \cdot 3^{k-2} < \frac{n}{3} \leq 3^k\), if \(\displaystyle n\) is odd, one can generate \(\displaystyle 3^k\) footprints in \(\displaystyle 3k\) steps and then use an additional block of length three to reach exactly \(\displaystyle n\) footprints in \(\displaystyle 3k + 3\) steps. However, if \(\displaystyle n\) is even, even with a final block of length three, \(\displaystyle 3k + 4\) steps are necessary, since every even number at least \(\displaystyle \frac{n}{3}\) requires at least \(\displaystyle 3k + 1\) steps. Thus, this case also confirms the desired formula, completing the proof.
Statistics:
15 students sent a solution. 7 points: Aravin Peter, Bodor Mátyás, Czanik Pál, Holló Martin, Keresztély Zsófia, Kocsis 827 Péter, Minh Hoang Tran, Morvai Várkony Albert, Szakács Ábel, Varga Boldizsár, Wágner Márton, Xiaoyi Mo. 5 points: 1 student. 0 point: 2 students.
Problems in Mathematics of KöMaL, December 2024