Background. In an RPG game, I've found that the weapon can destroy each object $i$ in a characteristic number of hits. When upgraded, the weapon can destroy each object $i$ in fewer hits. I am trying to account for this behavior in terms of a consistent system of hit points and damage: each weapon deals a certain amount of damage, and each object $j$ has a number of hit points, such that when the object is hit an appropriate number of times (and no fewer), the cumulative damage exceeds its total hit points.
This turns out to be an integer programming problem. I can solve it numerically in Python, but I'm having difficulty understanding the qualitative behavior: for some combinations of objects and weapons, the problem is unsolvable— I'm unable to find a pattern. I am looking for help expressing the problem or its solution in terms that clearly expose when the problem is infeasible.
Problem statement. In a certain RPG game:
- You have one weapon.
- Each object $i$ can be destroyed in a certain number of hits $k_i$, no less.
- Your weapon can be upgraded; with an upgraded weapon, each object $i$ takes one fewer hit to destroy. That is, $(k_i-1)$ hits, no less.
- In fact, your weapon might be upgraded multiple times. When your weapon is upgraded $j$ times, each object $i$ can be destroyed in $j$ fewer hits. That is, $(k_i-j)$ hits, no less.
You can express this as an integer programming problem:
Given a list of $m$ objects $\vec{k} = [k_1, k_2,\ldots, k_m]$ (represented as the number of hits required to destroy them with the basic weapon), and supposing your weapon can be upgraded $n$ times:
Find integer hit point values $[C_1, \ldots, C_m]$ and damage values $[d_0, \ldots, d_n]$ that account for the observed number of hits required to destroy each object: $$(k_i - j -1) d_j \leq C_i - 1 \qquad i=1,\ldots,m,\quad j=0,\ldots, n$$ $$(k_i - j -0) d_j \geq C_i - 0 \qquad i=1,\ldots,m,\quad j=0,\ldots, n$$
Explanation of the constraints.
The constraints enforce the number of hits $x$ required to destroy each object. The first constraint says that $x-1$ hits aren't enough. The second constraint says that $x$ hits are enough.
For an object $i$, the required number of hits is $k_i$ by default, but each upgrade decreases the number of required hits by one. Hence if there are $j$ upgrades, the required number of hits is $x\equiv k_i-j$.
The total damage dealt by a weapon with $j$ upgrades is the weapon's damage $d_j$ times the number of hits with the weapon. That damage destroys object $i$ if it meets or exceeds that object's hit points $C_j$.
For example, suppose I have objects that can be destroyed in 3, 4, and 9 hits, respectively, with the basic weapon. The weapon can be upgraded once $(n=1)$.
Hence we must find hit points for these objects $C_3, C_4, C_9$ and damage dealt by each weapon $(d_0, d_1)$ such that:
Each object $i$ can be destroyed in $i$ hits by the basic weapon: $$3 d_0 \geq C_3$$ $$4 d_0 \geq C_4$$ $$9 d_0 \geq C_9$$
...but no fewer:
$$2 d_0 < C_3$$ $$3 d_0 < C_4$$ $$8 d_0 < C_9$$
And upgrading the weapon $d_0\rightarrow d_1$ decreases the number of required hits by 1: $$2 d_1 \geq C_3 > 1d_1$$ $$3 d_1 \geq C_4 > 2d_1$$ $$8 d_1 \geq C_9 > 7d_1$$
One possible solution to this system is: \begin{align*} d_0 &= 4\\ d_1 &= 5\\ C_3 &= 9\\ C_4 &= 13\\ C_9 &= 36\\ \end{align*}
Indeed, note that an object with $C_i$ hit points can be destroyed by exactly $i$ hits from weapon $d_0$, no fewer, and exactly $i-1$ hits from weapon $d_1$, no fewer.
As another example, suppose two upgrades are allowed $(n=2)$. The problem is feasible if the objects can be destroyed in 4 and 8 hits:
\begin{align*} d_0 &= 7\\ d_1 &= 8\\ d_2 &= 11\\ &\\ C_4 &= 22\\ C_8 &= 56 \end{align*}
but the problem apparently becomes infeasible in a setup where the objects can be destroyed in 4 and 9 [!] hits instead.
I can solve this problem numerically. I can see why, if $n=0$ (no weapon upgrades) or $n=1$ (one upgrade), the problem is always solvable. But I'm surprised that for $n>1$, the problem is sometimes unsolvable. Have I made a mistake? Is there intuition (perhaps a picture) to explain why or when this happens?
Each weapon upgrade introduces new constraints on weapon damage. These constraints can be expressed as upper and lower bounds on weapon damage, often purely as functions of $k_{min}$ and $k_{max}$—the number of hits required to destroy the least and most robust objects in your collection.
(These bounds arise because if $C_k$ must lie within two intervals $a < C_k \leq b$ and $c < C_k \leq d$, then we automatically know that $a < d$ and $c<b$, eliminating $C_k$.)
In particular,
When there are zero upgrades, there are no constraints on the $k_i$ values; you can always get a solution by setting $\delta_0 \equiv 1$, $C_i\equiv k_i$. From now on, let's assume, without loss of generality, that we remove a degree of freedom by putting $\delta_0=1$.
When there is one upgrade, we find that: $1 < \delta_1 \leq \frac{k_i}{k_i-2}$ for each $i$. Because the ratio on the right is monotonically decreasing in the range of interest, the bound is tightest when $k=k_{max}$.
$$1 < \delta_1 \leq \frac{k_{max}}{k_{max}-2}$$ Now, this expression accounts for all of the constraints in the problem, and the ratio on the right is always strictly greater than one in the range of interest. Therefore, we can always find a value of $\delta_1$ (and corresponding hp values $C_1,\ldots, C_m$ to solve the one-upgrade problem.
For example, we can put $\delta_1$ at the midpoint of this nonempty range: $\delta_1 \equiv \frac{k_{max}-1}{k_{max}-2}.$
When there are two upgrades, suddenly we have upper and lower bounds that depend on $k_{max}$ and $k_{min}$, respectively, and which therefore may become incompatible. This is why two-upgrade problems are sometimes unsolvable. In particular, we find that for all $k_i$: $$\delta_2 > \delta_1 $$ $$\delta_2 > \frac{k_i-1}{k_i-2}$$ $$\delta_2 \leq \frac{k_i}{k_i-3}$$
$$\delta_2 \leq \frac{k_i-1}{k_i-3}\cdot \delta_1$$
Note that the expressions dependent on $k_i$ are again monotonic so we can replace $k_i$ with $k_{min}$ or $k_{max}$, whichever makes the bound tightest. Altogether, we have that, in the range of interest: $$\frac{k_{min}-1}{k_{min}-2} < \delta_2 \leq \frac{k_{max}}{k_{max}-3}$$ which incidentally establishes a limit on the range of allowed $k_i$ values: if $k_{min}$ is specified in advance, then we can arrange the above inequality to show that $k_{max}$ must be strictly less than $3(k_{min}-1)$ in order for the problem to be feasible. Because the inequality accounts for all the constraints, this condition is both necessary and sufficient. $$k_{max} < 3(k_{min}-1)$$ As a specific example, when $k_{min}=4$, $k_{max}$ must be strictly less than 9. This is exactly what we found above, numerically. Now we have a simple algebraic expression for it.