La determinación de la fuerza de un resumen del ejército

Question

Imaginemos que tenemos dos ejércitos, representado por las listas de pares de números positivos, como este: [($attack1$,$defence1$),($a2$,$d2$)...($an$,$dn$)] se enfrentan en combate. Las reglas de combate son las siguientes: cada unidad (pareja de ataque $a$ y de defensa,$d$) podrá en cualquier momento elegir un destino; a continuación, hace daño continuamente a su destino a una tasa de $a$ por segundo hasta que se elige otro destino o "muere" (es decir, su defensa se convierte en 0). Las unidades pueden cambiar los objetivos en cualquier momento. Cada ejército juega de forma óptima a maximizar su fuerza en el momento en que todas las unidades enemigas están muertos (si es que va a ganar) o para minimizar la fuerza del ejército enemigo (si es que va a ser enrutado). Un ejército gana matando a cada unidad en el lado opuesto. Un ejército de $A$ es de mayor fuerza que el ejército de $B$ si puede derrotar a $B$ y cualquier ejercito $B$ puede derrotar o vínculos con.

Suponemos que la función de $strength(A) = d1*(a1+a2...an) + d2*(a2+a3...an)...dn*an$ donde $(a1,d1)...(an,dn)$ son las unidades de $A$ ordenado por $(attack /defence)$ en orden descendente es una medida de un ejército de la fuerza tal que:

Si $A1$ caras $A2$$strength(A1) > strength(A2)$, entonces A1 saldrá victorioso con una fuerza restante $strength(A1) - strength(A2)$

Si $strength(A1) = strength(A2)$ después dibujan, ya sea a través de ambos se enruta o la batalla de nunca acabar. Yo no puedo probarlo. Puede usted?

Answer 1

Advertencia : no estoy afirmando que esto es una completa y rigurosa de la respuesta !

Creo que su conjetura no es cierto. Vamos a echar un vistazo a la situación de un ejército de 2 vs un ejército de 1 (el primer no-trivial caso). Denotar por $u_1$ $u_2$ de las unidades de la primera ejército y $u_3$ la unidad de la segunda ejército, y deje $u_i = (a_i, d_i)$.

En este caso, la estrategia óptima para el ejército de uno es obvia (unidad de ataque 3 hasta que muere) y la estrategia del ejército de los 2 debe ser centrarse en cualquiera de las unidades 1 o la unidad 2, y luego atacar a la otra si se las arregla para matar a la primera. Digamos ejército 2 se centrará en la unidad 1 de la primera. Nota : la elección de la unidad para participar en función de todas las variables que parece no trivial y muy interesante, pero yo no lo necesito para el propósito de este post.

Vamos a llamar a $t_i$ el momento de la muerte de unidad de $i$ : más precisamente, vamos a llamar a $t_1$ el tiempo requerido para el ejército de 2 a matar a la unidad 1 (siempre y cuando se vive lo suficiente), $t_2$ el tiempo requerido para el ejército de 2 a matar a la segunda unidad de ejército 1 y así ganar la batalla (aún vive el tiempo suficiente) y, a continuación, $t_3$ el tiempo que le toma a un ejército para matar a la unidad 3.

Es bastante sencillo que $t_1 = d_1/a_3$. También es fácil ver que $t_2=t_1 +d_2/a_3$. Finalmente, $t_3$ es un poco más complicado : $t_3$ debe verificar $$d_3 - t_1 (a_1 + a_2) + (t_3 - t_1) a_2=0$$ (desde hasta $t_1$ ambas unidades de ejército, uno de ataque y, a continuación, después de $t_1$ sólo la unidad 2).

Así ejército de los 2 va a ganar si sólo si $t_3 > t_2$. Con la aritmética básica, nos encontramos con : $$t_3 - t_2 = \frac{d_3}{a_2} - \frac{d_2}{a_3} - d_1 \frac{a_2 + a_1}{a_3 a_2}.$$

Ahora aquí es donde mi pereza muestra : no me parece para valores específicos de los parámetros que entran en conflicto con su propia fórmula, pero la expresión de dos parecen lo suficientemente diferentes y estoy convencido de que así debe de ser. En particular tengo un término que no es lineal en el$a_i$, por lo que estoy casi seguro de que no nos dan siempre las mismas predicciones.

Tenga en cuenta que para ser perfectamente riguroso no podemos elegir los parámetros completamente arbitraria, a partir del supuesto de que la estrategia óptima para el ejército del 2 al ataque de la unidad 1 de la primera, probablemente, que impone restricciones sobre los parámetros.

ANEXO : creo que su conjetura es más o menos basada en la suposición de que la mejor estrategia es centrarse en la más débil de las unidades de primer (o el más fuerte, dependiendo de cómo ordenar sus pares $(a_i, d_i)$). Creo que es más complicado que eso : podría ser el mejor para cuidar de un peso pesado en primer lugar, o si usted está seguro que va a morir, a tomar menor oponentes con usted a la tumba...

Answer 2

Eso no es una respuesta pero creo que @Glougloubarbaki está en el camino equivocado.

Para el caso de los dos ejércitos

$S(A) = d_1(a_1+a_2) + d_2a_2$

$S(B) = d_3a_3$

la conjetura es que si $S(B)>S(A)$, entonces el Ejército de B va a ganar con un residual de la fuerza de $S(B)-S(A)$ y viceversa. Que es

$$d_3a_3 - d_1(a_1+a_2) - d_2a_2$$

Si asumimos $S(B)>S(A)$, y los ataques $U_1$ primero se va a destruir $U_1$ después $d_1\over a_3$ segundos y $U_2$ después $d_2\over a_3$ segundos. Durante este período de Un Ejército va a hacer daño $(a_1+a_2){d_1\over a_3} + a_2 {d_2\over a_3}$. Por lo tanto, su fuerza residual será

$$a_3{(d_3-(a_1+a_2){d_1\over a_3} - a_2 {d_2\over a_3})}$$

la expansión de da

$$a_3 d_3-(a_1+a_2)d_1 - a_2 d_2$$

que es la misma que la conjetura.

Si los ataques $U_2$ antes de que el daño que sufre es $(a_1+a_2){d_1\over a_3} + a_1 {d_1\over a_3}$ y su fuerza residual es

$$a_3 d_3-(a_1+a_2)d_1 - a_1 d_1$$

A partir de la orden definido sabemos

$${a_1\over d_1} \ge {a_2\over d_2}$$

así

$${a_1d_2}\ge{a_2d_1}$$

así que la 2ª estrategia es manifiestamente peor para el Ejército B.

No tengo idea de cómo expandir esto a los casos más complejos. Es este susceptibles a la prueba por inducción?