The Witch's Tower

This problem has a mind-bogglingly enormous solution space, in terms of the number of distinct spells that could be cast by the Witch. The challenge of even counting the number of possible spells she could cast, is, in and of itself, a difficult combinatorics problem! Fortunately, we are searching for spells that have a specific property we wish to maximize, and that turns out to be enough to make the problem tractable.

---

The difficulty of this problem rises from the fact that Grifelda is an honorable villain - if she weren't, the answer would trivially be $\infty$ , for she could just route all the doors on the bottom floor back to the bottom floor, preventing the hero from ever reaching her lair. So, if we are to maximize the expected time for the hero to reach her lair, we must first get a grasp on the space of spells she might cast, and narrow it down to the optimal one as efficiently as possible.

While the solution actually turns out to be mostly intuitive, with a small little 'gotcha' cherry on top, getting there rigorously is actually a fairly onerous process. I'll present the TL;DR version in the next paragraph with the answer, with the following paragraphs rigorously proving the assertions in the first one.

---

TL;DR Version

Any optimal spell has the following property:

Choose any ordering $\{t_n\}_{n=1}^{101}$ of the floors in the tower, with $t_{101}$ equal to Grifelda's lair, subject to the constraint $D(t_n, t_{101}) \geq D(t_{n+1}, t_{101})$ for all $n < 101$ , where $D$ is the shortest-path distance function in the graphical sense (where $t_n$ are nodes, and doors are directed edges).

It must be the case that, if $d_n$ is the number of doors on floor $t_n$ , then $t_n$ must have $(d_n - 1)$ doors that point directly to $t_1$ , and just one door that points to $t_{n+1}$ , except for $t_{101}$ , which has no doors.

Now, for a given $\{t_n\}$ , let $E(t_n)$ be the expected number of doors to be opened by the hero before he reaches $t_{101}$ , given that he starts on floor $t_n$ . Subject to the constraint that $d_k = 100$ for some fixed $k$ , $E(t_k)$ is maximized when $d_a < d_b$ for all $1 \leq a < b \leq 100$ , $a, b \neq k$ . It can be computed that $E(t_k)$ is maximal when $k = 59$ , and for that unique configuration, we have:

$E(t_{59}) = 253686955560127297415270748212280220445147578566298142232775185987449253908386439848985416819725524700704346767443420494669394362627027809872591382996377454219$

$E(t_{59}) \approx 2.536869555601273 \cdot 10^{158}$

And the digit sum of $E(t_{59})$ is $\boxed{755}$ .

---

Long Version

Let's first reduce the problem to mathematical terms so that we can rigorously reason about it. Let the floors in the tower be $\{F_k\}_{k=1}^{101}$ , where floor $F_k$ has precisely $k$ doors, with the exception of Grifelda's lair, $F_{101}$ , which has no doors. Let the spell on the doors be arbitrary to start, and let $E(F_k)$ be the expected number of doors the hero must open to get to Grifelda's lair, given that he is currently on floor $F_k$ .

---

Lemma 1: All floors must be accessible to the hero, and Grifelda's lair should be accessible from all floors.

Let $k$ such that Grifelda's lair is not ultimately accessible from $F_k$ . $F_k$ must then not be accessible to the hero from his initial location on $F_{100}$ , otherwise, upon entering, he would never be able to reach Grifelda's lair, which violates the villain's honor code.

Now take $F_k$ , and set all of it's doors to point to Grifelda's lair. Take all doors that previously pointed to Grifelda's lair, and point them at $F_k$ instead. This has the effect of making all doors that opened directly to Grifelda's lair in the previous graph now count as $2$ doors instead of one, which increases $E(F_k)$ by one for all accessible $F_k$ in the previous graph. So the previous graph could not have been optimal. Therefore, any optimal graph must render all floors accessible to the hero, and so Grifelda's lair must be accessible from all floors.

---

Lemma 2: Every floor should have exactly one door to its topological successor, and all remaining doors should point to the topological root of the tower.

For an arbitrary spell, we can construct an ordering $\{t_m\}_{m=1}^{101}$ , consisting of all floors in $\{F_k\}$ , starting with $F_{101}$ , and continuing backwards in breadth-first order of the reverse graph of the doors (that is, the directed graph of floors connected by doors, with each door edge reversed), such that every $t_m$ , for $m < 101$ , has at least one door opening to a floor $t_k$ , with $k > m$ . For floors in the same tier, we can sort them descending with respect to the number of doors in each floor, which renders $\{t_m\}$ unique for any spell.

Thus, every spell which meets the conditions we have proved thus far necessarily has a unique topological order, and so it follows, that if we can prove that the optimum spell across all spells that satisfy some arbitrary topological order fits the conditions of the stated lemma, then the optimum spell across all spells in total must also satisfy the lemma.

Now, let $\{t_m\}$ be an arbitrary topological ordering of the floors, and let $\{d_m\}$ describe the number of doors on each floor correspondingly. We want to maximize $E(t_s)$ , for the starting position of the hero, $t_s$ , and if we can maximize all $E(t_m)$ while we're at it, great! We first recognize that the value $E(t_m)$ , for any $m$ , is representable as the convergent, infinite sum across all finite paths $P$ starting at $t_m$ , of the probability of such a path being taken, times the length of that path in number of doors.

Now, let $D$ be the set of doors that point to $t_{101}$ , with $|D| > 1$ . Consider $E(t_m)$ , represented as the infinite sum we just described, for some arbitrary $m$ . Then, select some arbitrary $d \in D$ , redirect it to some other floor which has ultimate access to at least one $x \in (D - \{d\})$ (to preserve Lemma 1's results), and compare this new $E(t_m)$ with the previous one. All paths originally terminating at some $x \in (D - {d})$ remain as they are, all paths that terminated at $d$ are removed.

For each such path $P$ removed, a swath of new paths are added, which are prefixed by $P$ , and terminating at some new $x \in (D - {d})$ . For each $P$ removed, the set of new paths added all occur with probabilities that sum to the probability of $P$ occurring originally, and since each new path is longer than the original $P$ , the sum of all these new addends necessarily at least matches the original addend for $P$ , and so the new $E(t_m)$ is $\geq$ the old $E(t_m)$ . Since this process can be applied repeatedly so long as $|D| > 1$ , it follows that the optimal spell must have $|D| = 1$ , and so only have one door that points to $t_{101}$ . It must be the case that $t_{100}$ houses this door.

Now, assume that, for some $k$ , $2 \leq k \leq 100$ , it is the case that all $t_m$ , $k \leq m \leq 100$ , have but one door pointing directly to $t_{m+1}$ , and that there are no other doors pointing to any $t_m$ for $k < m \leq 100$ . Let $D$ be the set of doors that point to $t_k$ , and suppose $|D| > 1$ .

For any $E_m$ , it holds that any finite path $P$ terminating at $t_{101}$ must, in fact, either be itself a suffix sequence of the doors connecting $t_m$ to $t_{m+1}$ for $k \leq m \leq 100$ , or, the path $P$ must be representable as a finite sequence of paths that terminate at some $x \in D$ , eventually terminated by the full sequence of doors that connect those $t_m$ to $t_{m+1}$ .

Select some arbitrary $d \in D$ , and redirect that door to some other floor which has ultimate access to $t_k$ . As with the preceding argument, the change between $E(t_m)$ for all $m$ before the change, and after the change, is that all paths $P$ which contained $d$ have their addends removed from the sum, and new paths, which contain the redirected $d$ , are added. We will show this change strictly increases $E(t_m)$ . Let $P_q^x$ denote the set of all finite paths which start at floor $q$ , and terminate at floor $k$ with a pass through door $x$ , having touched no other door in $D$ .

Let $P_q^{\text{final}}$ denote the set of paths starting at floor $q$ which never touch any $x \in D$ , and thus terminate in $< 101$ steps at $t_{101}$ . $Pr(p)$ denotes the probability of path $p$ being taken exactly, given the hero at the start of it, and $|p|$ denotes the length of the path, in doors. Then we have the recursive definition:

$S(q, 0, L) = \sum_{p \in P_q^{\text{final}}} \left( Pr(p) \cdot (|p| + L) \right)$

$S(q, r, L) = \sum_{x \in D} \sum_{p \in P_q^x} \left( Pr(p) \cdot S(k, r-1, |p| + L) \right)$

And the summation definition:

$E(t_m) = \sum_{r = 0}^{\infty } S(m, r, 0)$

Our first argument proved that $S(q, 1, L)$ strictly increases in value when $k = 100$ , for any $q$ , and by trivial arithmetic, and $L$ when $d$ is removed from $D$ . Because $S(k, 0, L)$ remains constant between the two spells regardless of $L$ or $k$ , it follows that $S(q, 1, L)$ increases for all possible $q$ , $k$ , and $L$ , and so, inductively onwards, $S(q, i, L)$ is strictly increased for the new spell. Since these values sum together to completely define $E(t_m)$ , $E(t_m)$ must also be increased for all $m$ by the redirected door.

The preceding paragraph allows us to apply mathematical induction to claim that the optimal spell, for our given topological order, has exactly one door from each $t_m$ to $t_{m+1}$ for all $1 \leq m \leq 100$ , and so by process of elimination, all other doors must point back to $t_1$ . Given the arguments stated in the first paragraph for Lemma 2, this is sufficient to prove that the optimal spell in general must have this property for its given topological order, and so we prove Lemma 2.

---

Lemma 3: The optimal spell has a topology that is ascending in terms of the number of doors for all floors, excepting the floor with 100 doors.

First, we'll note that Lemma 2 actually provides us a way to compute $E(t_m)$ for all $m$ in a simple, recursive expression. Recall that $d_m$ is equal to the number of doors on floor $t_m$ . Thus, for all $m$ , we have the linear equation:

$E(t_m) = 1 + \frac{1}{d_m} E(t_{m+1}) + \frac{d_m - 1}{d_m} E(t_1)$

Starting from $t_1$ , working our way up, and then plugging our way back down, we'll find that a pattern emerges. Specifically:

$E(t_m) = \sum_{i=1}^{100} \left( \prod_{j=i}^{100} d_j \right) - \sum_{i=1}^{m-1} \left( \prod_{j=i}^{m-1} d_j \right)$

Grouped another way:

$E(t_m) = \sum_{i=m}^{100} \left( \prod_{j=i}^{100} d_j \right) + \sum_{i=1}^{m-1} \left( \prod_{j=i}^{100} d_j - \prod_{j=i}^{m-1} d_j \right)$

The second form is quite useful. Suppose, in this sequence, there exist $a$ and $b$ such that $a > b$ , but $d_a < d_b$ . Observe that if we swap the values $d_a$ and $d_b$ , the value of $E(t_m)$ is guaranteed to increase. This is because, in all summands in the two summations, $d_b$ is present as a factor if and only if $d_a$ is present, and in the cases where $a$ and $b$ are on opposite sides of $m$ , swapping the values decreases the magnitude of the negative addend in the second summand, thus increasing the value of the summand.

Therefore, while in some terms, swapping $d_a$ and $d_b$ has no effect, in the rest of them, the addend increases in value. So making $d_m$ sorted ascending does in fact optimize all $E(t_m)$ individually.

However, we must be careful here, for while $E(t_{100})$ is indeed maximal when the sequence $\{d_n\}$ is fully sorted, this does not necessarily produce the best possible $E(t_k)$ for all $k$ where it could be that $d_k = 100$ . In fact, it can be shown that $E(t_m) > E(t_{m+1})$ for all $m$ on a given spell! We can only conclude that the optimal spell has $d_k = 100$ for some $k$ , and for all other $n \neq k$ , the sequence $\{d_{n \neq k}\}$ is sorted ascending. This concludes Lemma 3.

---

With Lemmas 1, 2, and 3 under our belt, we are ready to put down the pencil and paper and go to the keyboard instead, as we are, unfortunately, not quite done yet. We still need to figure out which $k$ in the constraint $d_k = 100$ yields the maximal $E(t_k)$ . Using the formula from Lemma 3, we can compute the maximal $E(t_k)$ for all possible $k$ , and we'll find that $k = 59$ yields the maximum result. As noted earlier:

$E(t_{59}) = 253686955560127297415270748212280220445147578566298142232775185987449253908386439848985416819725524700704346767443420494669394362627027809872591382996377454219$

$E(t_{59}) \approx 2.536869555601273 \cdot 10^{158}$

And the digit sum of $E(t_{59})$ is $\boxed{755}$ .

---

To put things in perspective, if the hero is able to open a new door every Planck time , and we assume that he is able to proceed in doing so from the big bang, until the projected heat death of the universe in $10^{100}$ years, the hero would need, on average, $~43\:\text{million}$ lifetimes of the universe to reach Grifelda's lair. So maybe this defense isn't so honorable after all.

---

APPENDIX

After all the analysis, the amount of code needed to get the answer is quite minimal. In it, I used an alternative, recursive representation of $E(t_k)$ to compute it.

def E(k):
  L = list(range(1,k)) + [100] + list(range(k,100))
  if k == 1:
    return D(L)
  else:
    return D(L) - D(range(1,k))

def D(L):
  if len(L) == 1:
    return L[0]
  else:
    return L[-1] * (D(L[:-1]) + 1)

m = {k: E(k) for k in range(1,101)}
maxE = max(m.values())
maxK = [k for k, v in m.items() if v == maxE]

print maxE * 1.0  # 2.5368695556e+158
print maxK        # [59]
print sum([int(x) for x in str(maxE)])  # 755