¿Cuántos pasos se necesitan para convertir una "a" en al menos 100,000 "a"s usando solo las tres funciones de "seleccionar todo", "copiar" y "pegar"?

Question

Supongamos que al principio hay un documento en blanco y se escribe una letra "a" en él. En los siguientes pasos, solo se pueden utilizar las tres funciones de "seleccionar todo", "copiar" y "pegar".

Encuentra el número mínimo de pasos para alcanzar al menos $100,000$ a's (cada una de las tres operaciones de "seleccionar todo", "copiar" y "pegar" se cuenta como un paso). Si el número de destino no está especificado, y quiero obtener la cantidad exacta de "a"s, ¿existe una fórmula general?

Esta es una pregunta fascinante. Mi amigo y yo la discutimos durante mucho tiempo ese día, pero no logramos resolverla.

Lo que comencé a pensar fue: Si los pasos de "seleccionar todo", "copiar" y "pegar" se cuentan aproximadamente como un paso. Cada paso hace que el número $\times2$, por lo que es una progresión geométrica con una razón común de 2.

Sea $a_{n}100000 \: (n\in \mathbb{N})$, donde $a_{1}=1$.

De acuerdo con la fórmula general de progresión geométrica: $a_{n}=a_{1}\times q^{n-1}$

Podemos obtener: $n=17$

Entonces, si las tres operaciones de "seleccionar todo", "copiar" y "pegar" se cuentan cada una como un paso, hay un total de $17×3=51$ pasos

Pero esto ignora un problema: ¿podemos pegar todo el tiempo?

Entonces, esto parece ser un problema de optimización interesante, y necesitamos encontrar una estrategia para minimizar el número de pasos de una "a" a cien mil "a"s.

1. Seleccionar todo + copiar + pegar: Estas tres operaciones duplican el número de "a"s. Si actualmente hay $n$ "a"s, entonces habrá $2n$ "a"s después de la operación.

2. Pegar: Esta operación agregará el número de "a"s igual al contenido del portapapeles. Si hay $k$ "a"s en el portapapeles, entonces habrá $(n+k)$ "a"s después de la operación.

Definimos una función $f(n)$ que representa el número mínimo de pasos requeridos para alcanzar $n$ "a"s. Inicialmente, tenemos una "a", así que $f(1) = 0$.

Si elegimos la operación de duplicar, $f(2n) = f(n) + 3$.

Si elegimos la operación de pegar, entonces $f(n+k) = f(n) + 1$, donde $k$ es el número de "a"s en el portapapeles.

Entonces comencé a confundirme porque me di cuenta de que parecía que cada paso enfrentaba una optimización, y parecía ser complicado. Empecé a usar la comparación de funciones para obtener $n=14$ como el valor mínimo, pero me di cuenta de que solo se optimizaba una vez.

Answer 1

S=seleccionar
C=copiar
P=pegar

SS, SP, CS, PC o CC no tienen sentido, por supuesto. Así que después de una S debe haber una C, después de una C debe haber una P, y después de una P debe haber otra P o una S.

SC$k$P es SC y $k$ pega, por ejemplo SCPPPP=SC$4$P.

SC$k$P es $k+2$ pasos y multiplica el número de caracteres por $k+1$.

Entonces, después de $a_1$ SC$1$P, $a_2$ SC$2$P, etc, el número de caracteres es $$\prod_{k=1}^\infty (k+1)^{a_k}$$ y el número de pasos es $$\sum_{k=1}^\infty (k+2)a_k$$

Tenga en cuenta que solo un número finito de $a_k$ son positivos.

A grandes rasgos, SC$k$P multiplica el número de caracteres por $\sqrt[k+2]{k+1}$ en cada paso. El máximo de $\sqrt[k+2]{k+1}$ para $k$ entero es en $k=3$, pero $k=2$ está muy cerca de él. (Para $k$ real no es $e$, por si acaso estás adivinando). Por lo tanto, es mejor elegir SC$2$P o SC$3$P siempre que sea posible.

Con un poco de prueba y error, he encontrado que $$3^3\cdot 4^6=110592>10^5$$ lo que arroja $3\cdot 4+6\cdot 5=42$ pasos.

Por otro lado, para obtener exactamente 100,000 caracteres, dado que $10^5=2\cdot 4^2\cdot 5^5$, el número de pasos es $$3\cdot1+5\cdot 2+6\cdot 5=43$$

No sé si es posible lograr $41$ o menos pasos, pero no creo que sea así.

EDIT
Para mostrar un ejemplo a @badjohn, si quieres obtener exactamente 100,001 caracteres, deberías factorizar $100001=11\cdot 9091$, por lo que la mejor manera de obtenerlo es 1SC$10$P y 1SC$9090$P, es decir, $12+9092=9104$ pasos.

Para 99,999 es $99999=3^2\cdot 41\cdot 271$. Dado que $3^2$ es relativamente pequeño, intentamos

• 2SP2C+1SP40C+1SP270C$=8+42+272=302$ pasos.
• 1SP8C+1SP40C+1SP270C$=10+42+272=304$ pasos.

EDIT2

La fórmula de los pasos mínimos para obtener exactamente $n$ caracteres es la siguiente:

Factoriza $n$ de esta manera: $$n=2^{\alpha_2}4^{\alpha_4}\prod_{p\text{ primo impar}}p^{\alpha_p},$$ donde $a_2$ debe ser $0$ o $1$ y $a_k\ge 0$ para $k\ge 3$.

Entonces, el número mínimo de pasos es $$\sum_{p=4\text{ o $p$ es primo}}\alpha_p(p+1)$$

---

Algunas notas:

1. Encontrar el máximo de $\sqrt[k+2]{k+1}$ con cálculo involucra una ecuación no elemental que resolví con software. Afortunadamente, no es esencial, es solo una pista.

2. Los puntos esenciales de mi razonamiento es que el número mínimo de pasos $S(n)$ para obtener exactamente $n$ caracteres, depende únicamente de cierta factorización de $n$, que implica $4$, números primos impares y $2$ solo si es necesario.

El número de pasos para alguna factorización (no necesariamente con factores primos) $$\prod_{n}n^{\alpha_n}$$ es $$\sum_{n}(n+1)\alpha_n$$

Para obtener la mejor factorización podemos comenzar desde la factorización prima y luego ver si 'combinando' algunos factores, podemos obtener una mejor.

Combinando un factor $p^{\alpha}$ con un factor $q^{\alpha}$, ($p,q\ge 2$, por supuesto) ,obtenemos el factor $(pq)^{\alpha}$. El número de pasos para esos factores va desde $$\alpha(p+q+2)$$ hasta $$\alpha(pq+1)$$ así que la pregunta es si $p+q+2$ es mayor o menor que $pq+1$. Combinar obtiene un menor número de pasos si $p+q+2>pq+1$.

Así que asumamos por ejemplo que $p+q+2>pq+1$. Las siguientes desigualdades son equivalentes a esta: $$p+q+1>pq$$ $$p(q-1) Dado que $q-1>0$,$$ p<\frac{q+1}{q-1}=1+\frac2{q-1}$$ Esto es verdad solo para $p=q=2$, así que 'combinar' obtiene mejores resultados solo al hacer un $4$ a partir de dos $2$'s.

Es decir, SC3P es mejor que 2SCP. Pero repetir P en lugar de hacer un nuevo SC es peor en cualquier otra situación. O igual para SCPPSCP y SC5P. (Es decir, para multiplicar el número de caracteres por 6 debes realizar 7 pasos, sin importar qué).

3. El problema es mucho, mucho más difícil si deseas obtener al menos $n$ caracteres, porque implica la factorización de cada número $\ge n$.

Answer 2

Profundizando en la respuesta de @ajotatxe, podemos mostrar en realidad cuál es el número mínimo de pasos necesarios.

Como él mencionó, los únicos movimientos sensatos son $M_k : =\textrm{SC}$k$\textrm{P}$, es decir "seleccionar todo, copiar y luego pegar $k$ veces" donde $k \ge 1$.

Cada vez que aplicamos $M_p$, multiplicamos el número por $(p+1)$ y usamos $(p+2)$ pasos. Llamemos $C(M_p) = p+2$ el costo del movimiento y $U(M_p) = p+1$ la utilidad del movimiento. Para una secuencia de movimientos $\bar{M} = (M_{p_1}, \ldots, M_{p_k})$, las funciones de costo y utilidad son respectivamente $$C(\bar{M} ) = \sum_{j=1}^k (p_j +2) , \ \ \ U(\bar{M}) = \prod_{j=1}^k (p_j+1)$$ Digamos que una secuencia de movimientos $\bar{M}$ es peor que otra secuencia $\bar{N}$, denotada como $\bar{M} \prec \bar{N}$, si $C(\bar{M}) \ge C(\bar{N})$ y $U(\bar{M}) \le U(\bar{N})$. En la práctica, casi siempre compararemos secuencias con el mismo costo. Una secuencia de movimientos $\bar{M}$ se llama óptima si es máxima con respecto a $\prec$. Por otro lado, notemos que $\prec$ es solo un preorden, es decir que podemos tener secuencias diferentes con igual utilidad y costo.

Afirmo que los únicos movimientos sensatos son $M_1, M_2, M_3, M_4$. Mostraré este hecho con el siguiente Lema. Si una secuencia de movimientos $\bar{M}$ contiene $M_k$ con $k \ge 5$, entonces existe $\bar{M} \prec \bar{N}$ con $\bar{N}$ no conteniendo $M_k$ para $k \ge 5$.

Prueba. Dado que la composición de movimientos es multiplicativa en la utilidad y aditiva en el costo, es suficiente mostrar que $M_k$ para $k\ge 5$ es peor que una secuencia de movimientos hechos únicamente de $M_1, M_2, M_3, M_4$. Para $k =5$ tenemos $M_5 \preceq (M_2, M_1)$, mientras que para $k \ge 6$ afirmo que $M_k \prec (M_{k-5}, M_3)$. De hecho, $k+1 \le 4k - 16$ siempre que $k \ge 17/3 \approx 5.67$.

La segunda observación es que $M_3$ tiene la mejor utilidad-por-costo; esto se puede ver al comparar el factor $\sqrt[k+2]{k+1}$ para $k=1,2,3,4$: $$\alpha_1 = \sqrt[3]{2} \approx 1.26, \ \ \ \alpha_2 = \sqrt[4]{3} \approx 1.316, \ \ \ \alpha_3 = \sqrt[5]{4} \approx 1.319, \ \ \ \alpha_4 =\sqrt[6]{5} \approx 1.308$$ Como resultado, tenemos lo siguiente:

Lema. Una secuencia óptima contiene $M_1$ y $M_4$ a lo sumo una vez y $M_2$ a lo sumo cuatro veces. Además, $M_2$ y $M_4$ no pueden aparecer juntos. En particular, todos menos 5 movimientos en una secuencia óptima son movimientos de $M_3$.

Prueba. Supongamos por contradicción que $M_2$ aparece cinco veces en una secuencia óptima. Notemos que $$C(M_2, M_2, M_2, M_2, M_2) = 20 = C(M_3, M_3, M_3, M_3)$$ La utilidad de $M_2$ cinco veces es $U(M_2)^5 = \alpha_2^{20}$, mientras que la utilidad de $M_3$ repetido $4$ veces es $\alpha_3^{20}$, concluyendo el argumento.

Para demostrar que $M_4$ y $M_1$ pueden aparecer a lo sumo una vez, notemos que $(M_4, M_4) \prec (M_2, M_2, M_2)$ y $(M_1, M_1) \prec M_4$. La última afirmación sigue de $(M_2, M_4) \prec (M_3, M_3)$.

Por último, notemos que $(M_1, M_2, M_2) \prec (M_4, M_3)$ permite solamente un $M_2$ cuando $M_1$ aparece. Como resultado, los únicos movimientos óptimos no de $M_3$ posibles son los siguientes $7$ movimientos: $$M_1, \ \ \ M_1 M_2, \ \ \ M_2, \ \ \ M_2 M_2, \ \ \ M_2 M_2M_2, \ \ \ M_2 M_2 M_2 M_2, \ \ \ M_4$$ Es posible mostrar, con la ayuda de un programa simple, que estas son en realidad secuencias óptimas de movimientos.

Estamos listos para mostrar el teorema final:

Teorema. El número mínimo de pasos $S(n)$ para copiar y pegar un texto $n$ veces con movimientos de seleccionar todo, copiar y pegar está dado por $$S(n) = \min_{i=1, \ldots, 8} 5 \lceil \log_4(n/u_i) \rceil+c_i$$ donde $(c_i, u_i)$ varía en el conjunto $$I = \{ (0,1), (3,2), (7,6), (4,3), (8,9), (12,27), (16,81), (6,5) \}$$

Prueba. La prueba es una consecuencia directa del argumento anterior. El conjunto $I$ es el conjunto de coordenadas de costo-utilidad para las 7 secuencias de movimientos anteriores, más un octavo elemento que representa el movimiento vacío (correspondiente a solo usar $M_3$). Si usamos una secuencia inicial con costo-utilidad $(c,u)$ y luego aplicamos $k$ veces $M_3$, obtenemos un costo-utilidad total de $(c+5k, u \cdot 4^k)$. Imponiendo $u \cdot 4^k \ge n$ obtenemos $k \ge \log_4(n/u)$, por lo que la solución entera más pequeña es $k_* = \lceil \log_4(n/u) \rceil$. Sustituyendo en el costo obtenemos la fórmula reclamada.

Como aplicación, para $n= 100,000$ obtenemos el mejor valor con el movimiento inicial $M_2 M_2 M_2$, y el número asociado de pasos es... 42, la Respuesta a la Pregunta Última sobre la Vida, el Universo y Todo!! Mis felicitaciones a @ajotatxe por haber adivinado la respuesta con prueba y error.

Para el OP: a posteriori, no es sorprendente que tu y tu amigo hayan tenido dificultades para encontrar la respuesta correcta. ¡Gracias por el problema muy interesante!

Answer 3

Las otras respuestas son buenas pero pensé en comentar sobre cómo verificar computacionalmente la respuesta: Se puede utilizar búsqueda en anchura (breadth-first search) en un grafo donde cada nodo representa un estado del documento. Las operaciones SELECT, COPY y PASTE nos permiten movernos de un nodo a otro en este grafo. El programa en C++ a continuación implementa este algoritmo.

#include <iostream>
#include <queue>

enum Mode
{
    SELECT,
    COPY,
    PASTE
};

struct Node
{
    int noOfAs;
    int steps;
    int noOfAsCopied;
    Mode mode;
};

int main()
{
    std::queue<Node> q;

    q.push({1, 0, 0, SELECT});

    while (!q.empty())
    {
        Node n = q.front();
        q.pop();

        if (n.noOfAs >= 100000)
        {
            std::cout << n.steps << std::endl;
            break;
        }

        switch (n.mode)
        {
        case SELECT:
            q.push({n.noOfAs, n.steps + 1, n.noOfAsCopied, COPY});
            break;
        case COPY:
            q.push({n.noOfAs, n.steps + 1, n.noOfAs, PASTE});
            break;
        case PASTE:
            q.push({n.noOfAs, n.steps, n.noOfAsCopied, SELECT});
            q.push({n.noOfAs + n.noOfAsCopied, n.steps + 1, n.noOfAsCopied, PASTE});
            break;
        }
    }

    return 0;
}

Al ejecutar este programa se mostrará la salida 42, que es el número mínimo de operaciones para que el documento se llene con al menos 100000 a's.