Optimal Pulling Strategy in Love Live School Idol Festival

by greenturtle3141, Jun 23, 2022, 11:31 PM

Reading Difficulty: 2-3/5
Prerequisites: Know what an expected value is

The Premise

Love Live! School Idol Festival is a gacha rhythm game. You can spend a currency called Love Gems in the gacha system to obtain more powerful characters/cards that can help you earn higher scores.

There are multiple gacha systems in the game. The one we'll focus on in this post is Box Scouting.

Imagine a deck of 100 cards. Among them, there is exactly one card that we consider to have value, which we will call Hanayo. Hanayo's position in the deck is chosen uniformly at random. I can now pay love gems to take cards from the top of the deck until I get Hanayo. Specifically, I have two options. I can either:

Spend 5 love gems to take just the topmost card ("Single Pull"), or
Spend 50 love gems to take the top 11 cards ("11-Pull"), provided that there exist that many cards left.

You may assume that I have a large number of love gems - say, 500. To reiterate, my sole goal is to obtain Hanayo. I will stop pulling as soon as I get Hanayo.

QUESTION: What strategy should I follow for obtaining Hanayo so that the expected number of love gems spent is minimized?

To get our feet wet, let's start with a warm-up problem.

Problem 1: What is the expected number of love gems spent when doing only single pulls?

Of course, this is probably not the best strategy, but this is certainly a good starting point. How can we determine this?

We compute this using "casework":

The probability that Hanayo is the first card is $\frac1{100}$ , and in this case we'd spend only $5$ love gems.
The probability that Hanayo is the second card is $\frac1{100}$ , and in this case we'd spend $10$ love gems.
$\cdots$
The probability that Hanayo is the $n$ th card is $\frac1{100}$ , and in this case we'd spend $5n$ love gems.
$\cdots$
The probability that Hanayo is the $100$ th card is $\frac1{100}$ , and in this case we'd spend $500$ love gems.

Now we just use the formula for expected value by summing over these 100 "cases":
$\mathbb{E}[\text{Love Gems Spent}] = \sum_{n=1}^{100} \left(\frac{1}{100}\right)(5n) = \frac{1}{20}\sum_{n=1}^{100}n$ $= \frac{1}{20} \cdot \frac{100(101)}{2} = \boxed{252.5}$ That sounds about right! The maximum love gems we could possibly spent is $500$ , so by linearity we should really only expect to spend about half that much to get Hanayo.

Can we do better?

Surely this strategy can't be that good. 11-pulling is more efficient because you get to pull more cards per love gem ( $11/50 = 2.2$ cards per love gem, vs. $2$ cards per love gem for single-pulls). Shouldn't the following strategy be much better?

Keep doing 11-pulls.
If Hanayo is not obtained by the 9th such 11-pull, do a single pull to obtain the remaining card (which must be Hanayo).

Let's find out!

Problem 2: What is the expected number of love gems spent when following this mostly-11-pull strategy?

Computing the expectation is again a matter of "casework".

For each $n = 1,2,\cdots,9$ , the probability that Hanayo is in the $n$ th range of 11 cards (i.e. the cards in positions $11n-10$ , $11n-9$ , ..., $11n-1$ , and $11n$ ) is exactly $\frac{11}{100}$ , and in this case we'd spend $50n$ love gems.
The probability that Hanayo is the very last card is $\frac{1}{100}$ , and in this case we'd spend $50 \times 9 + 5 = 455$ love gems.

Altogether:
$\mathbb{E}[\text{Love Gems Spent}] = \left[\sum_{n=1}^9 \left(\frac{11}{100}\right)(50n)\right] + \left(\frac{1}{100}\right)(455) = \boxed{252.05}$ And indeed that is less than the expectation from the previous strategy, which was $252.5$ . Hooray, we've proven that this strategy is so much bett-

...hold on, that is a really NARROW margin! The 11-pulls strategy is better by less than half a love gem. How could this be?

Exercise 1: What exactly is the disadvantage of doing only 11-pulls?

Think about it before proceeding! This is a critical point.

Answer

This doesn't mean that 11-pulls are inferior! It just means that there are situations in which the 11-pull is better and situations in which the single pulls are better.

Exercise 2: Can you (roughly) figure out what those situations are?

The answer to this will lay the groundwork for the next section.

Answer

Can we do better?

With that discussion in tow, the next plausible strategy should be clear:

"Keep doing 11-pulls while the deck is still large. Then, at some point, switch to single pulls."

Specifically, here is our strategy: For some fixed integer $0 \leq k \leq 9$ , we do the following:

Do exactly $k$ 11-pulls at the start.
Do $100-11k$ single pulls.

Problem 3: What is the expected number of love gems spent in this strategy, for each value of $k$ ? Moreover, which value of $k$ minimizes this expectation?

Observe that the case $k=0$ was our "stupid" only-single-pulls strategy, and the case $k=9$ is our not-as-stupid-11-pulls-strategy. This should let us verify whether or not we have a correct formula in the end.

Let's get into the casework!

For $n=1,2,\cdots,k$ , the probability that Hanayo is in the $n$ th range of 11 cards is $\frac{11}{100}$ , and in this case we spend $50n$ love gems.
For $n=1,2,\cdots,100-11k$ , the probability that Hanayo is the $(11k+n)th$ card is $\frac{1}{100}$ , and in this case we spend $50k + 5n$ love gems.

Bringing these cases together:
$\mathbb{E}[\text{Love Gems Spent}] = \left[\sum_{n=1}^k \left(\frac{11}{100}\right)(50n)\right] + \left[\sum_{n=1}^{100-11k} \left(\frac{1}{100}\right)\left(50k + 5n\right)\right]$ $= \frac{11 \cdot 50}{100} \cdot \frac{k(k+1)}{2} + \frac{(100-11k)(50k)}{100} + \frac{5}{100} \cdot \frac{(100-11k)(101-11k)}{2}$ After a lot of algebra (or Wolfram Alpha

) this comes out to:
$= \boxed{\frac{11 k^2 - 101 k + 10100}{40}}$ Plugging in $k=0$ and $k=9$ , this formula spits out $252.5$ and $252.05$ respectively. This is a good indicator that our formula is probably correct!

Now let's plot this formula in Desmos for a good view of what's going on:

Remarkable! The graph is a parabola, meaning that indeed, a strategy that goes "in between" the first two strategies we considered will actually be better! In particular our new strategy with $\boxed{k = 5}$ is best. That is, the best strategy as of now is to do the following:

Do exactly five 11-pulls.
If Hanayo is not obtained, do 45 single pulls until she is obtained.

This spends $\boxed{246.75}$ love gems in expectation, saving around 7 love gems over the previous two strategies. Yay!

Can we do better?

Er.

Probably not.

...

I mean, come on, our newest strategy seems so tight and optimized, there really is no way you could do better. Not by much, anyway.

...

And yet, as a math person, you'd get this horrible itch if you just leave the problem be now, because these intuitive feelings are not proof. How can we produce hard, irrefutable evidence that this third strategy is the absolute best, over ALL possible pulling strategies that could possibly exist?

Final problem: Prove that the " $k=5$ " pulling strategy is the best one.

Our angle of attack will be to prove this inductively. Let $f(n)$ be the expected number love gems spent to get Hanayo in a deck of $n$ cards, when following the best strategy. Can we get a recursive formula for $f(n)$ ?

Indeed, we can. Since we can either do a single pull or an 11-pull, we can essentially "check both options" and choose the better of the two. In math form:
$f(n) = \min\left(5 + \frac{n-1}{n}f(n-1), 50 + \frac{n-11}{n}f(n-11)\right) \qquad \forall n \geq 11$ In English: "If you do a single pull, you will spend 5 love gems. Then, either you got Hanayo or there is an $\frac{n-1}{n}$ chance that you now have a deck of $n-1$ cards, and now you follow the best strategy for this smaller deck. If you do a an 11-pull, you will spend 50 love gems. Then, either you got Hanayo or there is an $\frac{n-11}{n}$ chance that you now have a deck of $n-11$ cards, and now you follow the best strategy for this smaller deck. These are the two best possible outcomes, so choose the one that spends the least number of love gems in expectation."

But this only makes any sense whatsoever if there are at least 11 cards left. What about if $0 \leq n \leq 10$ ?

If you wear your thinking cap, get in your thinking chair, and then do the The Thinker pose, and muse philosophically, you can argue that $f(0) = 0$ . Technically it works out.
For $1 \leq n \leq 10$ , clearly the only strategy is to do single pulls, and this spends $\frac{5(n+1)}{2}$ love gems in expectation. So $f(n) = \frac{5(n+1)}{2}$ for all $1 \leq n \leq 10$ .

Now $f$ is fully defined, so now we just recursively find all values of $n$ up to infinity in order to prove our claim.

...nah, we're smarter than that. Observe first that
$f(11) = \min\left(\frac{5(12)}{2},50 + 0\right) = 30$ because $30 < 50$ . So for a deck of 11 cards, we choose to do a single pull. In fact, we'd be doing all single pulls, since that's our strategy for all single pulls. As long as the best thing to do for a deck of $m=1,2,\cdots,n$ cards is a single pull, we have that the best strategy for $n$ is ONLY single pulls, and moreover we would have the formula $f(n) = \frac{5(n+1)}{2}$ .

Therefore, we have that:
$f(n) = \min\left(5 + \frac{n-1}{n}f(n-1), 50 + \frac{n-11}{n}f(n-11)\right) = \min\left(5 + \frac{n-1}{n} \cdot \frac{5n}{2}, 50 + \frac{n-11}{n} \cdot \frac{5(n-10)}{2}\right)$ as long as the best thing to do for decks of sizes up to $n-1$ cards was to do a single pull, because again, for all such deck sizes we can use the $f(n) = \frac{5(n+1)}{2}$ formula.

This formula will break as SOON as this minimum does NOT choose the left side. Therefore, the smallest value of $n$ in which
$50 + \frac{n-11}{n} \cdot \frac{5(n-10)}{2} < 5 + \frac{n-1}{n} \cdot \frac{5n}{2}$ will be the FIRST value of $n$ in which the best thing to do is an 11-pull.

If you do the algebra and/or graph both sides, we'll see that this value of $n$ is $\boxed{n = 56}$ . (Funnily enough, both sides are equal for $n=55$ , meaning that you could do whatever you want. Perhaps you could argue that in this case you should do an 11-pull to save time since it doesn't matter.)

Our summary of findings up to now:

For decks of sizes $1,2,\cdots,55$ , the best strategy is to do single pulls.
For a deck of size $56$ , you first do an 11-pull.

So far, this is consistent with the hypothesis that our latest strategy is the best one! This is because after four 11-pulls, the deck size ends up being $100 - 44 = 56$ , and then the above findings say that indeed, you now must do an 11-pull.

Now we need to extrapolate our findings to show that for all deck sizes of at least $56$ , the best strategy is an 11-pull.

First, we prove this inductively for $n = 57,58,\ldots,66$ . If for such an $n$ , we have that the best strategy for $n-1$ is to first do an 11-pull and then do single pulls, then:
$f(n) = \min\left(5 + \frac{n-1}{n}f(n-1), 50 + \frac{n-11}{n}f(n-11)\right)$ $\min\left(5 + \frac{n-1}{n}\left[50 + \frac{n-12}{n-1}f(n-12)\right], 50 + \frac{n-11}{n} \cdot \frac{5(n-10)}{2}\right)$ $\min\left(5 + \frac{n-1}{n}\left[50 + \frac{n-12}{n-1} \cdot \frac{5(n-11)}{2}\right], 50 + \frac{n-11}{n} \cdot \frac{5(n-10)}{2}\right)$ Some algebra and/or Desmos will show that the left side is always strictly larger than the right side. This implies by induction that the best strategy is to do an 11-pull and then always single pulls for $n = 57,58,\ldots,66$ , and moreover the formula for the expectation is $f(n) = 50 + \frac{n-11}{n} \cdot \frac{5(n-10)}{2}$ .

To finish, we need to prove the following claim: For every $k \in \mathbb{N}$ , the formula for the expectation for $f(n)$ where $45+11k \leq n \leq 55+11k$ is given by $f(n) = \sum_{l=1}^k \frac{11}{n}(50l) + \sum_{l=1}^{n-11k} \frac{1}{n}\left(50k + 5l\right)$ . We prove this inductively! In the previous paragraph, we showed the base case $k=1$ . Now assume that the claim holds for some $k$ . We now just need to prove the claimed formula for all $45 + 11(k+1) \leq n \leq 55 + 11(k+1)$ by... using induction. Yeah, an induction inside an induction. The base case would be $n = 45 + 11(k+1)$ , and then you finish the proof for all $n$ in this interval. I think it would not be worth your time to write it out, but what's important is that the optimal strategy can indeed be proven!

Can we do better?

We can try and shorten this proof by proving the following claim:

CLAIM: If for a deck of $n$ cards, the best strategy is to do an 11-pull, then the same is true for a deck of $(n+1)$ cards.

The following argument comes from "tanoshii".

LEMMA: Let $n \geq 11$ . If it is known that Hanayo is at the bottom of the deck, then it is optimal to do an 11-pull.

Proof.

Because of the efficiency argument, minimizing the number of love gems spent is now clearly a matter of how many 11-pulls you can squeeze in. Snice $n \geq 11$ , we can do an 11-pull, thus doing an 11-pull is an optimal strategy. $\square$

To finish the proof of the claim, take a deck of $n+1$ cards, and note that either Hanayo is at the bottom of the deck or she is not. If she is, then an 11-pull is optimal by the lemma. If not, then the bottom card is not Hanayo, and we can view the problem as just a deck of $n$ cards, in which the best thing to do is an 11-pull by the inductive hypothesis.

...and, voila?

It's certainly a very beautiful argument, and one of my curiosities left over is figuring out how one would formalize it.

Anyways, isn't it simply remarkable how much math came out of a dumb gacha game? Look carefully and you truly can find math anywhere.

tl;dr

Do exactly five 11-pulls, then keep doing single pulls. This is the best possible strategy and it spends $246.75$ love gems on average.

This post has been edited 4 times. Last edited by greenturtle3141, Jun 23, 2022, 11:36 PM

probability

practical math

Comment

2 Comments

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

interesting

by Taco12, Jul 25, 2022, 8:17 PM

Report

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

when a random terrence tao decides to play video games once:

by akliu, Sep 11, 2022, 3:50 PM

Report

Submit

Can you give some thought to dropping a guide to STS? Just like how you presented your research (in your paper), what your essays were about, etc. Also cool blog!
by Shreyasharma, Mar 13, 2025, 7:03 PM
this is so good
by purpledonutdragon, Mar 4, 2025, 2:05 PM
orz usamts grader
by Lhaj3, Jan 23, 2025, 7:43 PM
Entertaining blog
by eduD_looC, Dec 31, 2024, 8:57 PM
wow really cool stuff
by kingu, Dec 4, 2024, 1:02 AM
Although I had a decent college essay, this isn't really my specialty so I don't really have anything useful to say that isn't already available online.
by greenturtle3141, Nov 3, 2024, 7:25 PM
Could you also make a blog post about college essay writing :skull:
by Shreyasharma, Nov 2, 2024, 9:04 PM
what gold
by peace09, Oct 15, 2024, 3:39 PM
oh lmao, i was confused because of the title initially. thanks! great read
by OlympusHero, Jul 20, 2024, 5:00 AM
It should be under August 2023
by greenturtle3141, Jul 11, 2024, 11:44 PM
does this blog still have the post about your math journey? for some reason i can't find it
by OlympusHero, Jul 10, 2024, 5:41 PM
imagine not tortoise math

no but seriously really interesting blog
by fruitmonster97, Apr 2, 2024, 12:39 AM
W blog man
by s12d34, Jan 24, 2024, 11:37 PM
very nice blog greenturtle it is very descriptive and fascinating to pay attention to
by StarLex1, Jan 3, 2024, 3:12 PM
orz blog
by ryanbear, Dec 6, 2023, 9:23 PM
Hi! Cool blog!
by mahaler, Nov 14, 2021, 3:08 PM
fascinating...
by pi271828, Nov 14, 2021, 12:00 AM
I believe that indeed, turtles come in all sorts of different colors. Even real ones! Some googling shows that indeed, red turtles seem to exist, though they're not that red.
by greenturtle3141, Nov 13, 2021, 9:21 PM
hello

since you have turtle knowledge, does your species of green turtles have a brethren that possess a color of red? what about blue? what about tawny mauve?
by pi271828, Nov 13, 2021, 9:18 PM
Nice Blog!
by Jwenslawski, Nov 13, 2021, 6:22 PM
Looking especially forward to how you improved on your AMC/AIME/USAMO so quickly
by StopSine, Nov 11, 2021, 2:01 AM
thanks the_turtle
by pog, Nov 10, 2021, 1:09 PM
another turtle blog?
by The_Turtle, Nov 9, 2021, 2:23 AM
Looking forward to future posts!
by Arr0w, Nov 2, 2021, 6:15 PM
just copy and paste every single one of your msm posts and thisll become the best blog ever hahahaha
by peace09, Nov 1, 2021, 9:33 PM
hello!
by tigerzhang, Nov 1, 2021, 9:09 PM
3rd shout! Yay greenturtle blog!
by violin21, Oct 25, 2021, 1:04 AM
hello $\text{[math]}$ $\text{[math]}$
by v4913, Oct 24, 2021, 5:33 PM
first shout
by mathlearner2357, Oct 24, 2021, 5:12 AM

67 shouts

Turtle Math

Optimal Pulling Strategy in Love Live School Idol Festival

by greenturtle3141, Jun 23, 2022, 11:31 PM

2 Comments