# The Witch's Tower

**Computer Science**Level 5

For nearly a thousand years, Grifelda, in her shrivelled, frog-stained robes, has toiled away in her fortress most forboden, in the pursuit of a potion to grant her powers great enough to earn the awe, terror, and jealousy of every spellcaster in the land. Unfortunately for her, as it goes for all great villains crafting their magnificent doomsday devices... a hero would arrive, at the eleventh hour, to vanquish her, and banish her potion to the chasms.

Grifelda was not without her defenses, though, for at the top of her tower she stood, on the one-hundred and first floor, no less. Below her was a floor with but a single door, and below that, a floor with two doors, and below that, a floor with three... and so on, floor after floor, until the base floor of the tower, with a hundred doors.

Normally, these doors were quite reasonable and predictable in their purposes, but not today, for today was Grifelda's day! Upon the hero's arrival, she cast a great spell, which transformed each and every door into a one-way portal to some other floor, completely unbound by the laws of physics and Euclidean Geometry.

Each door looked exactly the same as every other door, and there was no way to tell to which floor it led without stepping through. She was, however, bound as all villains are bound, not to cheat the hero of his chance at victory. No matter what the hero did, no matter which path he took, she had to leave a way for him to eventually reach the top floor and confront her, lest her defense be dishonorable.

The hero arrives on the bottom floor with one hundred doors just after the spell upon them all is cast. With no distinguishing features to go by, no way to mark the enchanted doors for memory's sake, and no knowledge of the layout of the massive tower, the hero has no choice but to simply enter a single door at random, step onto the floor it opens to, and repeat ad infinitum, until he eventually reaches Grifelda.

Grifelda is, naturally, a perfect mathematician, and so the spell she casts on the doors is optimal, in the sense that it maximizes the expected amount of time it would take for the hero to reach her lair, given that he walks through doors at a constant rate. If \(D\) is the expected number of doors the hero must walk through before reaching Grifelda's lair, what is the decimal digit sum of \(\lfloor D \rfloor\)?

Details (Clarifications):

- All of the doors are one-way. This is not to say, however, that there are no pairs of doors which are 'complimentary', in the sense that one door goes from floor \(X\) to floor \(Y\), and the other from floor \(Y\) to floor \(X\).
- Doors are permitted to open to the same floor they are on - that is, from floor \(X\) to floor \(X\).