Optimal collecting strategy I've faced this problem in one online game and have some struggles to solve it by myself so sharing it with you.
Let's say we aim to collect items from N collections with K items in each. We go to the vendor who offers us one absolutely random item for the price P1 or item from any specific collection for P2 (where P1 < P2, obviously). What is the optimal collection strategy to fill all collections?
Intuitively, we should be buying items for P1 till we finish our collection to some particular percent and then we'll target missing collectibles paying P2.
In my particular case, we have 6 collections with 6 items in each and P1=1 and P2=5.
Cheers!
 A: I see no particular reason to expect that there is a nice and simple description of the optimal strategy. It shouldn't be too difficult to though to write a program that does all the relevant calculations. In the following, I'll describe how to approach this.
For any given state of our collection, we want to compute the expected cost of completing it when buying either specific or generic cards. We start at the very end, when we are only missing a single card. The expected number of buys necessary to obtain the desired card is just the inverse of the success probability, so if we buy specific cards we expect to pay $P_2K$, if we buy generic cards we expect to pay $KN$. Whichever number is smaller is the expected cost (and this tells us what we should do).
If we have two missing cards from the same collection, we expect to pay $\frac{P_2K}{2}$ for getting one of the two missing for specific cards, and $\frac{KN}{2}$ for generic ones. Same comparison as above. If the two missing cards are from different collections though, the numbers to compare are $P_2K$ and $\frac{KN}{2}$ instead. By summing up the costs here with those from the preceding paragraph, we get the expected cost to pay if two cards in the same/different collections remain.
If we have three cards missing, with 2 in the same and 1 in different collections, the calculation gets more difficult. The reason is that "progress" isn't the only thing that matters, but we need to also include the difference in expected future costs whether we end up with missing 2 from the same collection or two from different ones. By buying specifically from the larger missing one, we get expected cost $\frac{P_2K}{2}$ to proceed to two different missing cards. Buying from the smaller one gets us expected cost $P_2K$ to proceed to to two missing cards from the same collection. Buying from the generic pack gets us expected costs of $\frac{KN}{3}$ to get a $\frac{1}{3}$-chance of the two-of-same-collection subsequent state, and a $\frac{2}{3}$-chance of the two-of-different-collection subsequent state.
The last paragraph is, conceptually, as complicated as it gets here. If you $K = N = 6$, the total number of states to consider should be feasible for a brute force computation.
