Fastest way to get \$1 million of two different currencies in a video game

Question

This question actually relates to a video game, I came across the scenario and I realized I had no idea how to go about solving something like this or even what branch of mathematics it falls under.

Anyway, the simplified version is as follows:

There are two types of currencies, I will call them currency A and currency B.

You start out with an income of 512 of currency A per second and an income of 36 of currency B per second.

The goal is to get to 1 million or more of each type of currency at the same time as fast as possible.

Although, in order to speed up your progress you can invest in things that will give you more currency. The things you can invest in and their bonus income are as follows:

Format: Option name, cost, bonus income

• A1, 33 B, +1 A/s (s is seconds)
• A2, 257 B, +8 A/s
• A3, 1025 B, +32 A/s
• A4, 4097 B, +128 A/s
• A5, 16385 B, +512 A/s
• A6, 65537 B, +2048 A/s
• A7, 262145 B, +8192 A/s
• A8, 1000001 B, +32768 A/s
• B1, 4096 A, +1 B/s
• B2, 20480 A, +6 B/s
• B3, 81920 A, +36 B/s
• B4, 262144 A, +216 B/s
• B5, 1000000 A, +1296 B/s

Using these investment options, what is the fastest way to obtain 1 million or more of both currency A and currency B at the same time?

I am most concerned with what TYPE of question this is and HOW to solve it rather than the actual answer. Any help on this would be appreciated.

---

Note: Since I am not sure what branch of mathematics this is I put optimization down as the tag, if this tag is incorrect I would appreciate it if someone could add the correct tag.

Answer 1

One possible approach is as follows. Write a computer program which evaluates all the possible strategies on the first turn (buy nothing, buy A1, buy A2, etc.). Order the strategies according to the following relation: say $S_1 \leq S_2$ if the amount of $A$ you have after $S_1$ is no more than the amount of $A$ you have after $S_2$; and the amount of $B$ you have after $S_1$ is no more than the amount you have after $S_2$; and your income of $A$ after $S_1$ is no more than your income of $B$ after $S_2$; and your income of $B$ after $S_1$ is no more than your income of $B$ after $S_2$. Intuitively, if $S_1 \leq S_2$, then $S_1$ can't possibly be a better strategy than $S_2$.

Now you have a preordered set of strategies. Essentially you want to take all of the "maximal elements" of this set. Actually the issue is subtler, because you can have a set of strategies which are all just as good each other in every dimension; if you regard "being just as good as each other in every dimension" as an equivalence relation on strategies, then the set of equivalence classes has a naturally induced partial order. Take one representative from each equivalence class which is maximal in this order; these are your "maximal elements."

Those maximal elements are the strategies which move on to the next round. In the next round, evaluate all of the possible ways of making the second move from the given strategies. Order these two-turn strategies as before, and again take a set of "maximal elements" of the resulting set. Move on to the third turn with those strategies. Continue like this. When you first find a strategy which reaches the goal, you have your answer.

My hope is that this process takes a reasonable amount of computation time, because taking only the best strategies from each round keeps the search space from blowing up exponentially. That is, my hope is that the set of maximal elements is always reasonably small, and in particular doesn't increase exponentially in size. However, I am not certain this would happen. Does anybody have any idea?

Answer 2

Let $S$ be your salary, $C$ be the cost of making investments, $R$ be the return, $V(t)$ be your cash (a 1x2 matrix), $P(t)$ be your portfolio (an 8x2 matrix) and $I(t)$ your investment strategy (an 8x2 matrix) all at time $t$. Then

$$S=\begin{bmatrix} 512&36\\ \end{bmatrix}$$

$$C=\begin{bmatrix} 4096&20480&81920&262144&10000000&0&0&0\\ 33&257&1025&4097&16385&65537&262145&1000001\\ \end{bmatrix}$$

$$R=\begin{bmatrix} 1&8&32&128&512&2048&8192&32768\\ 1&6&36&216&1296&0&0&0\\ \end{bmatrix}$$

$$V(0)=0_{1,2}$$

$$P(0)=0_{8,2}$$

And

$$P(t+1)=P(t)+I(t)$$

$$V(t+1)=V(t)+S-CI(t)+R(P(t)+I(t))$$

subject to the proviso that all elements of $V(t)\ge CI(t)$.

Now all you have to do is solve this partial differential equation and fine the minimum $T$ such that all the elements of $V(T)\ge1,000,000$ while at least one of the elements of $V(T-1)\lt 1,000,000$.