What is the probability of having the correct power for the next boss in 20XX?

I'm talking with a friend and trying to figure out how many levels of 20XX I'd have to beat to be guaranteed to have a weakness to a boss in 20XX.

For those unfamiliar, 20XX is a Megaman-based roguelike, which means that there are eight (initial) bosses, each one dropping a different unique power that one of the other eight is weak to. Unlike Megaman though, you're never presented with a straight stage select where you get to pick from all eight.

The first boss/level is randomly assigned from one of the eight bosses, and after beating it and taking its power, you're presented with three of the other remaining bosses to pick to fight next. These are picked entirely at random (it seems), and have no weighting towards being ones weak to your collected powers or not.

So my question is, how many different bosses would I need to get through to be guaranteed that one of those three is weak to one of the powers I already have? My gut is saying I need to beat 5, but I can't tell if that's right or not.

Solution 1:

Recap

So, there are 8 bosses. Whenever you defeat a boss, you gain their power. Each boss is weak against 1 other boss’s power.

The first boss is random. After you defeat a boss, you are given a choice of 3 bosses, so you can try to choose the boss against whom you have the right power. When you defeat the 6^th boss, you have only 2 choices instead of 3, since there would only be 2 choices left.

(To those who know the game well, I am assuming that the player is not using the destiny skull, and that they always choose to acquire the power of the boss they defeat.)

It is important to note that the directed graph of boss weaknesses looks like this:

[Source: Steam Guide]

The graph is connected; there are no cases where, say, Boss A is weak against Boss B’s power and Boss B is weak against Boss A’s power.

Best-Case Scenario

The probability of getting the right boss in the next level depends on how lucky you were previously. This is because of the fact that, if you manage to get the right boss for the power you have, that power is now ineffective against the remaining bosses, and now you need the right boss for the new power you acquired.

Let’s look at the best-case scenario. This is when you start somewhere on the graph above, and you manage to always battle the next boss in the graph. Let’s say you just defeated Boss 1. Since there are 3 bosses to choose from, the probability of finding the right Boss 2 is the probability that the first option is the right Boss 2 + the probability that the first option is not the right Boss 2 but the second option is the right Boss 2 + the probability that the first and second options are not the right Boss 2, but the third option is the right Boss 2. This leads to 1/7 + 6/7 * 1/6 + 6/7 * 5/6 * 1/5 = 3/7 (~43%).

Assuming you are on a lucky streak and you always manage to find the right boss before the current boss, the probabilities for the whole run will look like this:

Therefore, the probability of achieving a perfectly lucky run with all the right bosses is 3/7 * 1/2 * 3/5 * 3/4 = 27/280, which is ~9.64%. For comparison, these are much better odds than rolling 2 6’s in a row on a 6-sided die, the probability of which would be 1/6 * 1/6 = 1/36 (~2.78%).

Worst-Case Scenario

In the worst-case scenario, the first 4 bosses you battle will be something like this (the hidden bosses represent the ones you defeated):

You asked:

How many different bosses would I need to get through to be guaranteed that one of those three is weak to one of the powers I already have? My gut is saying I need to beat 5.

The answer to this depends on whether you will choose a boss who’s weak against one of your powers when you get the chance to do so.

In case you deliberately choose sensible* bosses who are not weak against your powers the answer is 4. This is represented by the graph I showed.

However, this is probably not the answer you were looking for. This is because I assumed that you are deliberately avoiding bosses who you have the right powers for until you can’t do so anymore in a sensible* manner. This is not a good strategy because it is unnecessary. (Btw, this is actually a good scenario if you are using the destiny skull, which removes the ability to choose the next boss.)

So, let’s now assume you will choose a boss who you have the right power for whenever you get the chance.

In that case, the scenario I showed is impossible. You will never end up with 4 bosses in the manner I showed. Here’s why:

Let’s say you started with the 3 bosses shown here. Then, you will never end up having to face the boss which none of your powers is strong against. This is because you will get 3 options, 2 out of which will be bosses you have strong powers against.

Similarly, even the scenario of starting with 3 “unlucky” bosses is impossible. Take a look at this:

There are only 2 bosses that you have no strong powers against. However, since you get 3 options, the third one will be a boss who you actually have a strong power against.

Therefore, the answer to your question, if we assume that you are not deliberately avoiding bosses that you have the right power for, is 2. If you don’t get to choose a boss you have a strong power against after defeating the first boss, you are guaranteed to be able to do so after defeating the second boss.

sensible*

In my answer, I used an asterisk with the word “sensible”. To clarify, I am assuming that the player is sensible enough to avoid choosing bosses which would give him/her powers which are useless against all future bosses.

It is actually possible to play the game such that only the eighth boss will be weak against a power that the player has. This is possible if the player chooses the bosses in this order:

Choosing a boss to the left of a boss you already defeated in the graph is the worst possible strategy, and there is no reason to do it. It is better to choose another boss, which would give you a power that will be useful against future bosses.

Tl;dr

The question asks for the number of bosses the player has to defeat in order to guarantee that he/she will have the option of choosing a boss who is weak against one of the powers he/she has. The answer depends on the strategy the player is following for choosing the next boss.

If the player is always avoiding bosses who are weak against one of his/her powers (this is not the best strategy), the answer is 4. After defeating 4 bosses who were not weak against any of his/her powers, he/she will then be forced to choose one who is.

If the player is choosing bosses who are weak against one of his/her powers, the answer is 2. After defeating 2 bosses who are not weak against any of his/her powers, the player will then definitely be able to pick a boss who is.