There is a card in Magic the Gathering called Lim-Dul's Vault. While it is slightly more complicated than presented, the question I would like to consider is this:
- Pay 1 life.
- Look at the top 5 cards of your deck. You may rearrange these cards in any order.
- You may repeat step 1. If you do, put the previous 5 cards on the bottom of your deck. If you don't, put the previous 5 cards on the top of your deck.
Given a deck of $n$ cards, how much life does it take to arrange all of the cards completely in the order you like?
Notes:
Clearly this can't be done if $n$ is a multiple of 5.
As an extension, for most decks, there are functionally identical cards (ie, the "four of spades" is the same as the "four of diamonds"). What is optimal in this case?
I have no idea what tags to put on this problem.
I cant give you a hard number, but can offer an $O(m)$ notation.
Since you have n cards and you can shuffle 5 cards under the deck each time.
You can change the place of a card by $n\%5$, but can also only affect $5-n\%5$, since those can be safely transfered.
If you want to transfer the bottom card to the top, you need to spent $\frac{n}{n\%5}$ Life for one step and $\frac{n}{n\%5}$ steps. Thus you'll need $\left(\frac{n}{n\%5}\right)^2$ Life per card. Thus you can safely assume you need $$O\left(n \times \left(\frac{n}{n\%5}\right)^2\right)$$ Life.
To precise it a bit more. Since we know we can affect $k = 5 - n\%5$ cards each time we can use $k$ instead of $n$. Allowing for $$O\left(\frac{n}{k} \times \left(\frac{n}{n\%5}\right)^2\right)$$ Or $$O\left(\frac{n^3}{k \times (n\%5)^2}\right)$$