November 2023

You are currently browsing the monthly archive for November 2023.

Noxious Fumes: Certain Death in ceil((-3 + sqrt(8h + 9)) / 2) turns

Intro

There are three great deck builder card games:  Dominion, Slay the Spire, and Magic the Gathering.  There are four different characters in Slay the Spire.  My favorite is the Silent character who often uses poison to defeat the monsters.

One method of attacking with poison in Slay the Spire is to play the “Noxious Fumes” card.  The card self destructs after it is played (it cannot be played again until the you enter the next room in your quest.)   Nothing happens on the turn in which it is played.  The next turn, the monster experiences 2 damage from the poison.  The next turn after that, the monster experiences 3 additional poison damage for a total of 5 poison damage.  The next turn after that 4 additional poison damage for a total of 9 poison damage.  And so on.

Time to Death

I love Noxious Fumes. I love that once I play Noxious Fumes, the enemy will die in square root time no matter what he does and no matter what I do. In fact, every monster with $h$ or less health points will be dead in no more than
$$\mathrm{deathTime}=\mathrm{ceil}\left( \left( -3+ \sqrt{ 8h +9}\right)/2\right)$$ turns. [1][2]

Notation: $\mathrm{ceil}(x)$ is defined to be the smallest integer which is greater than or equal to $x$. For example, $\mathrm{ceil}(13) = 13$, $\mathrm{ceil}(3.2) = 4$, and $\mathrm{ceil}(\pi) = 4$.
“ceil” is an abbreviation for “ceiling” and $\mathrm{ceil}(x)$ is $x$ rounded upward.

Example

Let’s try out the formula. If the monster has 100 health points, then it will be dead in
\begin{aligned} \mathrm{deathTime}&=\mathrm{ceil}\left( \left( -3+ \sqrt{ 8\cdot 100 +9}\right)/2\right) \\ &=\mathrm{ceil}\left( \left( -3+ \sqrt{ 809}\right)/2\right) \\ &=\mathrm{ceil}\left( \left( -3+ 28.44\right)/2\right) \\ &=\mathrm{ceil}\left( 25.44/2\right) \\ &=\mathrm{ceil}\left( 12.72\right) \\ &=13\end{aligned} turns.

• If you play the Noxious Fumes on turn 4, then on turn 4+1=5, the monster will have 2 poison, and 2 total poison damage.
• On turn 4+2=6, the monster will have 3 poison, and 2+3 total poison damage.
• On turn 4+3=7, the monster will have 4 poison, and 2+3+4 total poison damage.
• On turn 4+12=16, the monster will have 13 poison and $2+3+4+\cdots+13= 90$ total poison damage.
• On turn 4+13=17, the monster will have 14 poison and $2+3+4+\cdots+14= 104$ total poison damage and hence will be dead.

Theorem

Theorem: If a monster has $h$ health points when a Noxious Fumes card is played and that monster has no way to heal or remove the Noxious Fumes, then it will be dead $$\mathrm{deathTime}=\mathrm{ceil}\left( \left( -3+ \sqrt{ 8h +9}\right)/2\right)$$ turns later. [3]

For the few of you who like proofs, here it is.

Proof:
The sum $2+3+4+\ldots+n$ is the sum of $n-1$ numbers whose average value is $\frac{n+2}{2}$, so that sum is
$$2+3+4+\ldots+n = (n-1)\frac{n+2}{2}.$$
For example,
$$2+3+4+5 = (5-1)\cdot (5+2) /2 = (4\cdot 7)/2 = 28/2 = 14.$$

$t$ turns after the Noxious Fumes card is played, the monster will have $t+1$ poison and a total poison damage of
$$\mathrm{totalPoisonDamage} = 2+3+4+\cdots+(t+1)= t (t+3)/2.$$

If the monster had $h$ health points when the Noxious Fumes card was played, then $t$ turns later the monster will be dead if
$$h\leq \mathrm{totalPoisonDamage} = t (t+3)/2.$$
Now let’s try to find the value of $t$ where the left hand side equals the right hand side. The following are equivalent
\begin{aligned} h&= t (t+3)/2 \\ 0&= \frac{t^2}{2} + \frac{3 t}{2} -h. \\ \end{aligned} According to the quadratic formula, the equation above will be satisfied by
\begin{aligned} t &= \frac{ -3/2 \pm \sqrt{(3/2)^2 – 4 (1/2) (-h) } }{2\cdot (1/2)}\\ &= -3/2 \pm \sqrt{9/4 + 2h } \\ &= \frac{-3 \pm \sqrt{9 + 8h }}{2}.\\ \end{aligned}
The solution $t = \frac{-3 – \sqrt{9 + 8h }}{2}$ can be disregarded because it is negative. So,
$$h = t (t+3)/2$$
if $t = \frac{-3 + \sqrt{9 + 8h }}{2}$. The fact that poison damage is always increasing implies that
$$h \leq t (t+3)/2\quad\mathrm{if\ }t\geq \frac{-3 + \sqrt{9 + 8h }}{2}.$$
If $t$ is an integer, then
$$h \leq t (t+3)/2\quad\mathrm{if\ }t\geq \mathrm{ceil}\left( \frac{-3 + \sqrt{9 + 8h }}{2}\right)$$
which implies the monster is dead if
$$t\geq \mathrm{ceil}\left( \frac{-3 + \sqrt{9 + 8h }}{2}\right).$$

Endnote

That’s it. Watch out for the sequel,

“Noxious Fumes+ : Guaranteed Death in <Spoiler Removed> turns or less”.

Footnotes

[1] Alright, technically this formula does not work if the monster can heal or if the monster can remove the noxious fumes. The list of monsters that can heal or remove debuffs includes: Centurion/Mystic, Spheric Guardian, Reptomancer, The Collector, the Awakened One, and the Time Eater.}

[2] It’s not too hard to show that $$\left( -3+ \sqrt{ 8h +9}\right)/2 < \sqrt{2 h}.$$  In fact, $$\frac{\left( -3+ \sqrt{ 8h +9}\right)/2}{\sqrt{2 h}} = \frac{1}{\sqrt{\frac{9}{8 h}+1}+\frac{3}{2 \sqrt{2} \sqrt{h}}} < 1.$$

[3] Possibly earlier if there is any other source of damage.