Solving a linear system to infer damage values in an RPG

Solution 1:

You want to find integer variables $C_i$ and $d_j$ to satisfy linear constraints $$(k_i-j-1)d_j + 1 \le C_i \le (k_i-j)d_j \quad \text{for all $i$ and $j$}.$$ One approach to diagnose infeasibility is to look for an irreducible infeasible set (IIS). For your case with $k=(4,9)$ and $n=2$, the linear programming relaxation has an IIS as follows: \begin{align} 3d_0 - C_1 &\le -1 \tag1 \\ C_1 - 2d_2 &\le 0 \tag2 \\ 6d_2 - C_2 &\le -1 \tag3 \\ C_2 - 9d_0 &\le 0 \tag4 \end{align} Indeed, we can deduce from these constraints $$9d_0+3 = 3(3d_0+1) \overset{(1)}{\le} 3C_1 \overset{(2)}{\le} 3(2d_2) = 6d_2 \overset{(3)}{\le} C_2 - 1 \overset{(4)}{\le} 9d_0-1,$$ which is a contradiction.

Equivalently, multiply constraints $(1)$ and $(2)$ each by $3$ and add the resulting constraints to $(3)$ and $(4)$ to obtain the contradiction $0 \le -4$.

Solution 2:

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,

1. 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$.

2. 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}.$

3. 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.