17
$\begingroup$

In a RPG game, your three characters A, B and C fight a boss. The boss has $1000$ hp. The attacks are sequential: A attacks then B attacks then C attacks then A attacks again, etc. Character A can do any integral amount of damage between $25$ and $50$ with equal probability. Character B can do any integral amount of damage between $30$ and $70$ with equal probability. Character C can do any integral amount of damage between $10$ and $80$ with equal probability. Assuming that the boss is not strong enough to kill any of the characters before it dies, what is the probability that player A will be the one to deliver the final blow and kill the boss? Same question for players B and C.

Unfortunately I don't even know how to get started on this problem, any hint would be helpful.

$\endgroup$
3
  • 5
    $\begingroup$ Nice problem. I think in the limiting case the boss has a very large "power," the relative probabilities depend upon the average damage by $A$, $B$, or $C$ on any turn. But in this finite case, the problem is trickier. $\endgroup$ – David G. Stork Feb 10 at 1:58
  • 2
    $\begingroup$ I haven't even read a word of your problem description yet; I just wanted to give you props for the best subject line I've seen so far this year. $\endgroup$ – Trevor Feb 13 at 13:41
  • $\begingroup$ And what is the answer if you go and compute all possibilities? $\endgroup$ – Aatmaj Feb 15 at 11:25
4
+500
$\begingroup$

Here is yet an other answer, targeting the exact fractions that give the needed probabilities, it combines simple combinatorics and simple coding (sage is my weapon of choice), based on the fact that there is a (very) limited amount of complete turns $N$ till the total of $1000$ points can be randomly reached.


The player $A$ wins in a situation like $(ABC)^N\;A$, i.e. there are $N$ complete turns, then $A$ plays and the total sum of points so far is for the first time $\ge 1000$. We denote by $P(A,N)$ this probability.

Similarly, $B$ wins in a situation like $(ABC)^N\; AB$, and we denote by $P(N,B)$ the corresponding probability, and $C$ wins with the remained probability, but for the check, let this be in a situation like $(ABC)^N\; ABC$, and we denote by $P(N,C)$ the corresponding probability.

Now we compute. The first one who can win is $C$, since $5(50+70+80)=1000$, but the corresponding probability $$ P(5,C)= {\underbrace{\left(\frac 1{26}\right)}_p\ }^5 {\underbrace{\left(\frac 1{41}\right)}_q\ }^5 {\underbrace{\left(\frac 1{79}\right)}_r\ }^5 $$ is tiny. We have denoted by $p=1/26$,$q=1/41$, $r=1/79$ the corresponding probabilities for each individual result for $A$, $B$, respectively $C$. After this warming up, let us start.


Now let $N$ be fixed (between $4$ and $15$). Consider the polynomials (possibly taken modulo $x^{1001}$): $$ \begin{aligned} Q_A &= p(x^{25}+\dots+x^{50})\ ,\qquad Q_A(1) =1\ ,\\ Q_B &= q(x^{30}+\dots+x^{70})\ ,\qquad Q_B(1)=1\ ,\\ Q_C &= r(x^{10}+\dots+x^{80})\ ,\qquad Q_C(1)=1\ ,\\[3mm] % F_A(N) &= Q_A^N\; Q_B^N\; Q_C^N\ ,\\ F_B(N) &= Q_A^{N+1}Q_B^N\; Q_C^N\ ,\\ F_C(N) &= Q_A^{N+1}\; Q_B^{N+1}\; Q_C^N\ ,\\[3mm] % &\qquad\text{ and isolate relevant coefficients:}\\ F_A(N) &= \dots + a_{950} x^{950} + a_{951} x^{951} + a_{999} x^{999} + \dots\\ F_B(N) &= \dots + b_{930} x^{930} + b_{931} x^{931} + b_{999} x^{999} + \dots\\ F_C(N) &= \dots + c_{920} x^{920} + c_{921} x^{921} + c_{999} x^{999} + \dots\qquad \ . \end{aligned} $$ Above, the $a$, $b$, $c$ - coefficients in some degree $k$ are probabilities to reach $k$ short before being self on fire. Then the probability to get on or over $1000$ after turn $N$ for $A,B,C$ is respectively $$ \begin{aligned} P_A(N) &= p(a_{950} + 2a_{951} + 3a_{952} + \dots + 25 a_{974}) \\ &\qquad\qquad+ ( a_{975} + a_{976}+\dots+a_{999})\ , \\[2mm] P_B(N) &= q(b_{930} + 2b_{931} + 3b_{932} + \dots + 40 b_{969}) \\ &\qquad\qquad+ ( b_{970} + b_{971}+\dots+b_{999})\ , \\[2mm] P_C(N) &= r(c_{920} + 2c_{921} + 3c_{922} + \dots + 70 a_{974}) \\ &\qquad\qquad+ ( c_{990} + c_{991}+\dots+c_{999})\ . \end{aligned} $$ These sums can be calculated. Let us get the explicit fractions.

p, q, r = 1/26, 1/41, 1/71
R.<x> = PowerSeriesRing(QQ, default_prec=1001)
QA = p*sum([x^k for k in [25..50]]) 
QB = q*sum([x^k for k in [30..70]])
QC = r*sum([x^k for k in [10..80]])
Q = QA * QB * QC + O(x^1000)

def PA(N):
    QAN = Q^N + O(x^1000)
    return p * sum([ (k-949) * QAN.dict().get(k, 0) for k in [950..974]]) + \
               sum([           QAN.dict().get(k, 0) for k in [975..999]]) 
           
def PB(N):
    QBN = Q^N * QA + O(x^1000)
    return q * sum([ (k-929) * QBN.dict().get(k, 0) for k in [930..969]]) + \
               sum([           QBN.dict().get(k, 0) for k in [970..999]]) 
           
def PC(N):
    QCN = Q^N * QA * QB + O(x^1000)
    return r * sum([ (k-919) * QCN.dict().get(k, 0) for k in [920..989]]) + \
               sum([           QCN.dict().get(k, 0) for k in [990..999]]) 
           
pa = sum([PA(N) for N in [0..16]])
pb = sum([PB(N) for N in [0..16]])
pc = sum([PC(N) for N in [0..16]])

print(f"p_A &= {latex(pa)}\\\\&\\approx {pa.n(200)}\\ ,\\\\[2mm]")
print(f"p_B &= {latex(pb)}\\\\&\\approx {pb.n(200)}\\ ,\\\\[2mm]")
print(f"p_C &= {latex(pc)}\\\\&\\approx {pc.n(200)}\\ .")

Let us print the obtained values explicitly in an aligned block: $$ \begin{aligned} p_A &= \frac{334033901864090379613127803175076008061329503244624264537089105546493539}{1178392443307351590334920499763343901461744782823432598226397490500042752}\\&\approx 0.28346575350277151214602996031038557893379483738585896702069\ ,\\[2mm] p_B &= \frac{6309830943686662816904113123282509708706840969580727479884347191047819}{16597076666300726624435499996666815513545701166527219693329542119718912}\\&\approx 0.38017724871382680616769939159810617375709726053541809298534\ ,\\[2mm] p_C &= \frac{604208147014494132197561989078063573296081662711244943014511790227369}{1796329944066084741364208078907536435155098754304013107052435198932992}\\&\approx 0.33635699778340168168627064809150824730910790207872293999396\ . \end{aligned} $$

$\square$


A final check:

sage: pa + pb + pc
1
$\endgroup$
2
  • 1
    $\begingroup$ The final check is indeed a check, since the probabilities pa, pb, pc were computed separately, without "any knowledge of each other". Note that the true value for $$p_A\approx 0.283465753502771512146\dots$$ corrects already on the marked fourth position after the decimal point w.r.t. the good, intuitive, but approximative value $$ \frac{37.5}{37.5+50+45}\approx 0.283\color{red}{018867924\dots}$$ from the answer of @karl ... $\endgroup$ – dan_fulea Feb 19 at 3:26
  • $\begingroup$ The exact result reveals maybe more structure, the denominator for $p_A$ is$$2^{15} \cdot 13^{14} \cdot 41^{15} \cdot 71^{15}\ ,$$the denominator of $p_B$ is $$2^{15} \cdot 13^{14} \cdot 41^{15} \cdot 71^{14}\ ,$$ and the denominator of $p_C$ is $$2^{11} \cdot 13^{14} \cdot 41^{14} \cdot 71^{15}\ .$$ $\endgroup$ – dan_fulea Feb 19 at 3:43
14
$\begingroup$

Here's a way to think about it: imagine initializing a "total damage counter" as $D_0=0$, and on the $n$th turn, when $d_n$ damage is done to the boss, increment it to $D_n=D_{n-1}+d_n$ and color the interval $(D_{n-1},D_n]$ according to which player attacked. If we allow this to continue forever, it will color the whole number line with a random pattern of three colors.

Notice that the player who kills the boss is the one whose color covers the point 1000. Since this point is far away from 0, we can think of it as being randomly aligned with our color pattern, so it's as though we're picking a random point on the number line and asking what color it is. This only depends on the ratio of paint colors that our pattern uses, and (by the law of large numbers) this is approximately just the ratio among the expected values of the players' attacks. So e.g. the probability that player A kills the boss is about $37.5/(37.5+50+45)$.

$\endgroup$
9
$\begingroup$

I think this problem can only be solved either approximately (asympotically exact) or numerically. Karl's approximation is the most natural answer, and I'd go for it. If you instead want an exact result, here's an efficient numerical procedure (computer assisted, though).

Letting $g_A(n)$ be the probability that player $A$ wins given that the boss has power $n$, we have the recursion

$$ g_A(n) = \sum_{j=n}^\infty p_A(j) + \sum_{j=1}^{n-1} p_{ABC}(j)g_A(n-j)$$

where $ p_A(j)$ is the probability mass function of the damage inflicted by player $A$ and $p_{ABC}(j)$ is the same for the three players summed.

Solved numerically in Octave (or Matlab) this gives

$$g_A(1000) = 0.28347$$ pretty near Karl's approximation ( $0.28302$)

The graph shows that that approximation is quite good after $N\approx 900$

enter image description here

Code:

pa = [1:100];
pa = pa >= 25 & pa <= 50;
pa = pa/sum(pa);
pb = [1:100];
pb = pb >= 30 & pb <= 70;
pb = pb/sum(pb);
pc = [1:100];
pc = pc >= 10 & pc <= 80;
pc = pc/sum(pc);
pab = [0, conv(pa,pb)];
pab = [0, conv(pa,pb)];
pac = [0, conv(pa,pc)];
pbc = [0, conv(pb,pc)];
pabc = [0, conv(pab,pc)];
N=1000;
pabc(N)=0;
ga = zeros(1,N);
ga(1)=1;
for n=2:N
  ga(n) = sum(pa(n:100)) +  flip(ga(1:n-1)) * pabc(1:n-1)';
endfor
ga(N)

For completeness, here are the other probabilities

enter image description here

gb = zeros(1,N); % prob of B winning, if B has next turn
gb(1)=1;
 for n=2:N
 gb(n) = sum(pb(n:100)) +  flip(gb(1:n-1)) * pabc(1:n-1)';
endfor
gbb=zeros(1,N);  % prob of B winning, if A has next turn
pa(N)=0;  % extend pa size
for n=2:N
 gbb(n)= flip(gb(1:n-1)) * pa(1:n-1)';
endfor
gcc = 1 - (ga+gbb);

Notice that the period of the quasioscillations is around the mean value of the whole turn : $(25+50+30+70+10+80)/2 = 132.50$

$\endgroup$
1
  • $\begingroup$ It's cool that the player order is visible in the phase differences among the oscillations in the second graph. I wonder how close the curves are to simple sine waves (after correcting for the amplitude decay and nonzero offset) or if there's a useful "frequency domain" way of looking at this. $\endgroup$ – Karl Feb 19 at 0:27
3
$\begingroup$

This problem can be modelled as a Markov chain and we can use known results about hitting probabilities to calculate the exact answer. I will first explain how to model it as a Markov chain and then give the exact answer as implementation in matlab.

Let $S$ denote the set of states: For each player $P$ and each possible HP value $x$ of the boss (between $0$ and $1000$) we add the state ($P$, $x$) to $S$ (note that $0$ is representative of any HP value less or equal to $0$ here). The random variable $X_i$ is the state of the system after $i$ rounds. The state transition probabilities (i.e. the probability $P[X_{i + 1} = (P, x) | X_i = (P', x')]$) are now given by the problem description.

As an example, assume we know already that $X_i = (A, 1000)$ and we want to compute the (conditional) probability that $X_{i + 1} = (B, x)$. Since $A$ can do damage between $25$ and $50$ we have that $P[X_{i + 1} = (B, x) \, | \, X_i = (A, 1000)] = \frac{1}{26}$ for $x \in \{950, \dots, 975 \}$ and it is $0$ for other values of $x$. Of course, the probability of reaching any state with player $C$ next is $0$.

The hitting probability of a state $(P, x) \in S$ is the probability that we ever reach $(P, x)$ in this random process. Thus the hitting probability of the state $(A, 0)$ is exactly the probability that $C$ delivered the killing blow. Similarly, the hitting probability of $(B, 0)$ and $(C, 0)$ are the probabilities of $A$ and $B$ respectively delivering the killing blow.

These probabilities can be computed as the solution of a linear system of equations. I have coded this up in matlab, see below. States are represented as numbers from $1$ to $3003$. If a state $s$ satisfies $s =_3 0$ it is a state where $A$ attacks next. Similarly, $B$ and $C$ are associated with states in residue classes $1$ and $2$ respectively.

The HP of the boss in state $s$ is encoded as $ \lceil s / 3 \rceil - 1$. For example, state $3003$ is a state where $A$ attacks next and where the boss has $1000$ hitpoints.

Matlab has a built-in function for finding hitting probabilities which I use here. If you run the code below, it will tell you that we get probabilities $0.2835, 0.3494, 0.3671$ for players $A, B$ and $C$ respectively.

Let me know if you have any questions.

% build transition matrix P for N hitpoints
N = 1000;
P = zeros(3*(N + 1), 3*(N + 1));
% states 1, 2, 3 are endstates (i.e. random process loops there)
for i = 1:3
    P(i, i) = 1;
end
% all other transitions
for i = 4:(3*(N + 1))
    % player A
    if mod(i, 3) == 0
        for j = 25:50
            P(i, max(2, i - 1 - (3 * j))) = P(i, max(2, i - 1 - (3 * j))) + 1/26;
        end
    % player B
    elseif mod(i, 3) == 1
        for j = 30:70
            P(i, max(1, i + 2 - (3 * j))) = P(i, max(1, i + 2 - (3 * j))) + 1/41;
        end
    % player C
    else
        for j = 10:80
            P(i, max(3, i - 1 - (3 * j))) = P(i, max(3, i - 1 - (3 * j))) + 1/71;
        end
    end
end
% build markov chain from transition matrix
mc = dtmc(P);
% find hitting probabilities for player A, B, C
C = hitprob(mc, 1);
A = hitprob(mc, 2);
B = hitprob(mc, 3);
% output
A(3*(N+1))
B(3*(N+1))
C(3*(N+1))
$\endgroup$
3
$\begingroup$

Extra assumptions:

  1. attack damage > HP left means kill.
  2. all damage ranges include both edge values, so e.g. for Character A the damage value $d_A \in [25, 50]$.

With problems like this, if you want to obtain a definite answer, you probably want to start from the end and proceed by backward induction. Here, this means that you begin by considering HP values in the "kill range" of the current attacker. I am going to sketch out the main points of a precise solution, but I will not give you a closed-form answer. I hope that my "sketch" will be clear enough for you to come to the answer you want.

Suppose that it is Character A's move, and the boss's HP is $x \leq 50$. What is the probability of dealing enough damage? It's simply $$\Pr(\text{A kills} \,|\, \text{it's A's turn and } HP = x) = \frac{50+1-x}{50-25+1} = \frac{51-x}{26}.$$ Similarly, for B and C we get, for $x \leq 70$ and $x \leq 80$ respectively, $$\Pr(\text{B kills} \,|\, \text{it's B's turn and } HP = x) = \frac{70+1-x}{70-30+1} = \frac{71-x}{41}$$ and $$\Pr(\text{C kills} \,|\, \text{it's C's turn and } HP = x) = \frac{80+1-x}{80-10+1} = \frac{81-x}{71}.$$

By now we can already write out the answer… in an implicit form: $$\Pr(\text{A kills}) = \sum_{i=1}^{50} \Pr(\text{it's A's turn and } HP = i) \times \Pr(\text{A kills} \,|\, \text{it's A's turn and } HP = i) =\\= \sum_{i=1}^{50} \Pr(\text{it's A's turn and } HP = i) \times \min\left\{ 1, \max\left\{ 0, \frac{51-x}{26} \right\} \right\},$$ and similarly for the other two characters. The $\min\left\{ 1, \max\left\{ 0, \frac{51-x}{26} \right\} \right\}$ term comes from the fact you want the probability to stay in between 0 and 1.

So the missing part now is the $\Pr(\text{it's X's turn and } HP = i)$ terms. We can write down a recurrent formula for it, no matter the character $X \in \{A,B,C\}$ — as long as the current HP is low enough for X to have had at least one attack before: $$\Pr(\text{it's X's turn and } HP = i) = \sum_{s=25+30+10}^{50+70+80} \Pr(\text{it's X's turn and } HP = i + s) \times \Pr(\text{total damage over the last round} = s).$$

You see that for the expression above to become useful, we need to know the distribution of damage per round, $\Pr(\text{total damage over the last round} = s)$, for $s \in [65,200]$ (it is zero outside that interval). This probability is $$\Pr(\text{total damage over the last round} = s) = \sum_{d_A = \max\{25,s-70-80\}}^{\min\{50,s-30-10\}} \sum_{d_B = \max\{30,s-d_A-80\}}^{\min\{70,s-d_A-10\}} \frac{1}{26} \cdot \frac{1}{41} \cdot \frac{1}{71}.$$ The fraction product up there is simply the probability of a particular damage value triplet $(d_A,d_B,d_C)$ materializing; the sum limits are trickier — let me explain them.

You have the task to deal exactly $s$ damage in three consecutive hits by character A, B, and C. Suppose that A deals $d_A$ damage. What can $d_A$ be? On the one hand, it has to be at least enough so that B's and C's strongest attacks put the total at $s$, hence $d_A \geq s - 70 - 80$. On the other hand, $d_A$ has to be low enough so that B's and C's weakest attacks do not throw you above $s$, therefore $d_A \leq s - 30 - 10$. And then you also have the limits $25 \leq d_A \leq 50$ from the rules. Applying both means that, at each of the edges, whichever limit is stricter is the one that rules. Similarly, after A's attack you have exactly $(s-d_A)$ more damage to deal, so you get $s-d_A - 80 \leq d_B \leq s-d_A - 10$ in addition to the existing rule that $30 \leq d_B \leq 70$. Finally, after both A and B have hit, C must deal exactly $d_C=s-d_A-d_B$ damage; all that remains is to check that $d_C$ is within the $[10,80]$ interval, but that always holds by construction of the sum limits.

What do we have at this point? We know the probabilities of killing the boss when within range; we also know the probabilities of ending up in a particular game situation (active character + HP count) at any time that is certainly past the first round, i.e. for $HP \leq 1000 - 50 - 70 - 80 = 800$. What remains to be calculated are the probabilities of the game situations for higher HP levels. The problem with that range is, not every combination of a character and an HP level is attainable there, so one has to be careful. Here I would probably switch to analysing the characters move by move rather than round by round as I did before.

Consider $\Pr(\text{it's C's turn and } HP = i)$. Since character C is in play, it must have been B's move right before. Therefore, we have $$\Pr(\text{it's C's turn and } HP = i) = \sum_{d_B = 30}^{\min\{70,1000-25-i\}} \frac{1}{71} \times \Pr(\text{it's B's turn and } HP = i + d_B).$$ (We're talking $i \leq 1000-25-30 = 945$ as anything higher is unattainable, and the respective probability is zero.) By the same token, $$\Pr(\text{it's B's turn and } HP = i) = \sum_{d_A = 25}^{\min\{50,1000-i\}} \frac{1}{26} \times \Pr(\text{it's A's turn and } HP = i + d_A).$$ Here $i \leq 1000-25 = 975$, otherwise $\Pr(\text{it's B's turn and } HP = i) = 0$. Finally, $$\Pr(\text{it's A's turn and } HP = i) = \sum_{d_C = 10}^{\min\{80,1000-25-30-i\}} \frac{1}{72} \times \Pr(\text{it's C's turn and } HP = i + d_C)$$ with, importantly, $i \leq 1000-25-30-10 = 935$; for $i \in [935,999]$ $\Pr(\text{it's A's turn and } HP = 0$, and for $i = 1000$ it is one — that's the start of the game. This concludes the solution.


Remark: I could have left out the part that involves using the distribution of total damage per round and gone for the move-by-move induction rightaway, but I think that, first, it is useful for learning how to solve such problems, and second, it should probably save up quite some computations.

Another remark: my answer seems similar, in terms of formulae, to @leonbloy's. I would also like to reinforce the statement in @Karl's reply: the more rounds, in expectation, the boss takes to kill, the closer the result would be to the straightforward approximation $37.5/(37.5+50+45)$.

$\endgroup$
3
$\begingroup$

I will give a method for obtaining a closed form answer, and will explain why it is impractical to give an "ultimate closed form" in terms of algebraic numbers.


Short answer: if the boss starts with $N$ HP, then the probability that A kills the boss is given by the following formula:

$$p_N = 0.2830 + 2Re((0.1896 + 0.1642i)\cdot (0.9937 - 0.0458i)^N) + 2Re((-0.0017 + 0.1517i)\cdot (0.9803 - 0.0807i)^N + \dots.$$

The above is a finite sum, but has more than one hundred terms. All the numbers appearing are algebraic numbers, approximated to the fourth decimal place.

The main term is $0.2830$ and all other terms converges exponentially to zero.


The calculation:

Let $x_A, y_A$ be the min/max damage of $A$. Also let $d_A$ denote $y_A - x_A + 1$.

Thus in the original question, we have $x_A = 25, y_A = 50, d_A = 26$.

The same notations apply to B and C.

For convenience, we also write $y = y_A + y_B + y_C$, i.e. the max damage that can be done in one round. It is $200$ in the original question.

Let $p_n$ be the probability that A kills the boss, provided that the boss starts with $n$ HP.

Viewing $(p_n)_n$ as a sequence, we may establish a recurrence relation.

For any $n > y$, the boss can definitely survive the first round. For any $a \in [x_A, y_A]$, $b\in [x_B, y_B]$, $c\in [x_C, y_C]$, there is a probability of $\frac 1 {d_A d_B d_C}$ that A, B, C deal damages $a, b, c$ in the first round, respectively. When this happens, the boss will remain $n - (a + b + c)$ HP, and in the rest of the game, A will kill the boss with probability $p_{n - (a + b + c)}$.

Therefore, for $n > y$ we get the following equation: $$p_n = \sum_{a = x_A}^{y_A}\sum_{b = x_B}^{y_B}\sum_{c = x_C}^{y_C}\frac 1 {d_A d_B d_C}p_{n - (a + b + c)}.$$

This is a linear recurrence relation, and we may apply the standard solving method to it.

Thus we first look at its characteristic polynomial, which is given by: \begin{eqnarray} f(T) &=& T^y - \sum_{a, b, c} \frac 1{d_A d_B d_C} T^{y - (a + b + c)}\\ &=& T^y - \frac 1 {d_A d_B d_C}\sum_{a = x_A}^{y_A} T^{y_A - a}\sum_{b = x_B}^{y_B} T^{y_B - b}\sum_{c = x_C}^{y_C} T^{y_C - c}\\ &=& T^y - \frac 1 {d_A d_B d_C} (T^{d_A} - 1)(T^{d_B} - 1)(T^{d_C} - 1) / (T - 1)^3 \end{eqnarray}

If this polynomial only has simple roots $r_1, \dots, r_y$, then there exists $c_1, \dots, c_y$ such that $p_n = \sum_{i = 1}^y c_i r_i^n$ for all $n$.

It is easy to see that $1$ is always a root of $f$, as $(T^{d_A} - 1)/(T - 1)$ evaluates to $d_A$ at $T = 1$, and idem for B, C.

Although this polynomial looks simple, usually $T = 1$ is the only "nice" root, namely $f/(T - 1)$ is quite probably an irreducible polynomial over $\Bbb Q$, and hence the roots $r_i$ are just some algebraic number of very high degree).


From here, it seems inevitable to use some computer algebra system.

The following code can be pasted into this site to calculate the polynomial $f$.

xA, yA = 25, 50
xB, yB = 30, 70
xC, yC = 10, 80
dA, dB, dC = yA - xA + 1, yB - xB + 1, yC - xC + 1
y = yA + yB + yC

R.<T> = QQ[]
f = T^y - (T^dA - 1)*(T^dB - 1)*(T^dC - 1)/(T - 1)^3 / (dA * dB * dC)
print(f)

The polynomial $f$ looks like $T^{200} - \frac 1 {75686} T^{135} - \frac 3{75686} T^{134} - \dots$.

To check that $f$ doesn't have double roots, we calculate the $\gcd$ of $f$ and its derivative:

print(gcd(f, f.derivative()))

The result is $1$, showing that all the $200$ roots of $f$ are different.

We may also try to factorize $f$ over $\Bbb Q$:

print(f.factor())

The result is $(T - 1)(T^{199} + T^{198} + \dots + \frac 2{37843}T + \frac 1{75686})$. The second factor is irreducible, which means that the ultimate "closed formula" answer to this question will have coefficients in some huge number field, of degree at least $199$ (and probably much, much larger, up to $199!$).

This complexity is the nature of the problem, and cannot be avoided.


Now let us try to find all roots of $f$ in $\Bbb C$. We also sort the roots in decreasing order of the norm.

CC = ComplexField(200)
S.<T> = CC[]
f = S(f)
roots = [r for [r, e] in f.roots()]
roots.sort(key = norm, reverse = True)
print(roots)

The list starts with $1.0000, 0.9937 \pm 0.0458i, 0.9803 \pm 0.0807i, \dots$. Thus we see that $1$ is indeed the largest root. I now rename the roots as $r_0 = 1, r_1, r_2, \dots, r_{199}$ in the descending order.

It remains to obtain the coefficients $c_i$ from the initial values by solving a linear equation.

Here my interpretation is that the boss dies as soon as its HP is reduced to $\leq 0$.

p, q, r = [0], [1], [0]
for n in range(1, y):
    p.append(sum([q[n - j] if j < n else CC(1) for j in range(xA, yA + 1)]) / dA)
    q.append(sum([r[n - j] if j < n else CC(0) for j in range(xB, yB + 1)]) / dB)
    r.append(sum([p[n - j] if j < n else CC(0) for j in range(xC, yC + 1)]) / dC)
m = matrix([[rt^j for rt in roots] for j in range(y)])
c = m.solve_right(vector(p))

The list $c_i$ starts with $0.2830, 0.1896 \pm 0.1642i, -0.0017 \pm 0.1517i, \dots$.

This gives our final "closed form" formula $p_n = \sum_i c_i r_i^n$, in complex numbers.

The final step is to put in $n = 1000$:

N = 1000
print(c.dot_product(vector([rt^N for rt in roots])))

Result: $p_{1000} \approx 0.2834657535$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.