La forma más rápida de conseguir un millón de dólares de dos monedas diferentes en un videojuego

Question

Esta pregunta en realidad está relacionada con un videojuego, me encontré con el escenario y me di cuenta de que no tenía ni idea de cómo ir a resolver algo así o incluso a qué rama de las matemáticas pertenece.

De todos modos, la versión simplificada es la siguiente:

Hay dos tipos de monedas, las llamaré moneda A y moneda B.

Empiezas con un ingreso de 512 de la moneda A por segundo y un ingreso de 36 de la moneda B por segundo.

El objetivo es llegar a 1 millón o más de cada tipo de moneda al mismo tiempo lo más rápido posible.

Aunque, para acelerar tu progreso, puedes invertir en cosas que te den más moneda. Las cosas en las que puedes invertir y sus ingresos de bonificación son las siguientes:

Formato: Nombre de la opción, coste, ingresos por bonificación

• A1, 33 B, +1 A/s (s son segundos)
• A2, 257 B, +8 A/s
• A3, 1025 B, +32 A/s
• A4, 4097 B, +128 A/s
• A5, 16385 B, +512 A/s
• A6, 65537 B, +2048 A/s
• A7, 262145 B, +8192 A/s
• A8, 1000001 B, +32768 A/s
• B1, 4096 A, +1 B/s
• B2, 20480 A, +6 B/s
• B3, 81920 A, +36 B/s
• B4, 262144 A, +216 B/s
• B5, 1000000 A, +1296 B/s

Utilizando estas opciones de inversión, ¿cuál es la forma más rápida de obtener 1 millón o más de la moneda A y de la moneda B al mismo tiempo?

Lo que más me preocupa es el TIPO de pregunta y la forma de resolverla, más que la respuesta en sí. Cualquier ayuda sobre esto sería apreciada.

---

Nota: Como no estoy seguro de qué rama de las matemáticas se trata he puesto optimización como etiqueta, si esta etiqueta es incorrecta agradecería que alguien añadiera la etiqueta correcta.

Answer 1

Un posible enfoque es el siguiente. Escribir un programa de ordenador que evalúe todas las estrategias posibles en el primer turno (no comprar nada, comprar A1, comprar A2, etc.). Ordene las estrategias según la siguiente relación: digamos $S_1 \leq S_2$ si la cantidad de $A$ que tienes después de $S_1$ no es más que la cantidad de $A$ que tienes después de $S_2$ ; y la cantidad de $B$ que tienes después de $S_1$ no es más que la cantidad que tienes después de $S_2$ ; y sus ingresos de $A$ después de $S_1$ no es más que su ingreso de $B$ después de $S_2$ ; y sus ingresos de $B$ después de $S_1$ no es más que su ingreso de $B$ después de $S_2$ . Intuitivamente, si $S_1 \leq S_2$ entonces $S_1$ no puede ser una estrategia mejor que $S_2$ .

Ahora tienes un preordenado conjunto de estrategias. Esencialmente se quiere tomar todos los "elementos máximos" de este conjunto. En realidad, la cuestión es más sutil, porque se puede tener un conjunto de estrategias que sean todas igual de buenas en todas las dimensiones; si se considera que "ser igual de buenas en todas las dimensiones" es una relación de equivalencia en las estrategias, entonces el conjunto de clases de equivalencia tiene una inducción natural pedido parcial . Tome un representante de cada clase de equivalencia que sea máximo en este orden; estos son sus "elementos máximos".

Esos elementos máximos son las estrategias que pasan a la siguiente ronda. En la siguiente ronda, evalúe todas las formas posibles de realizar el segundo movimiento de las estrategias dadas. Ordene estas estrategias de dos turnos como antes, y vuelva a tomar un conjunto de "elementos máximos" del conjunto resultante. Pase al tercer turno con esas estrategias. Continúe así. Cuando encuentre por primera vez una estrategia que llegue a la meta, tendrá su respuesta.

Mi esperanza es que este proceso lleve una cantidad razonable de tiempo de cálculo, porque tomar sólo las mejores estrategias de cada ronda evita que el espacio de búsqueda se dispare exponencialmente. Es decir, mi esperanza es que el conjunto de elementos máximos sea siempre razonablemente pequeño y, en particular, que no aumente exponencialmente de tamaño. Sin embargo, no estoy seguro de que esto ocurra. ¿Alguien tiene alguna idea?

Answer 2

Dejemos que $S$ sea su salario, $C$ ser el coste de las inversiones, $R$ sea el retorno, $V(t)$ sea su efectivo (una matriz de 1x2), $P(t)$ sea su cartera (una matriz de 8x2) y $I(t)$ su estrategia de inversión (una matriz de 8x2) todo a la vez $t$ . Entonces

$$S=\begin{bmatrix} 512&36\\ \end{bmatrix}$$

$$C=\begin{bmatrix} 4096&20480&81920&262144&10000000&0&0&0\\ 33&257&1025&4097&16385&65537&262145&1000001\\ \end{bmatrix}$$

$$R=\begin{bmatrix} 1&8&32&128&512&2048&8192&32768\\ 1&6&36&216&1296&0&0&0\\ \end{bmatrix}$$

$$V(0)=0_{1,2}$$

$$P(0)=0_{8,2}$$

Y

$$P(t+1)=P(t)+I(t)$$

$$V(t+1)=V(t)+S-CI(t)+R(P(t)+I(t))$$

a condición de que todos los elementos de $V(t)\ge CI(t)$ .

Ahora sólo hay que resolver esta ecuación diferencial parcial y afinar el mínimo $T$ tal que todos los elementos de $V(T)\ge1,000,000$ mientras que al menos uno de los elementos de $V(T-1)\lt 1,000,000$ .