# Solution to a scarce resources assignment game

I would like to tell you about this game, which can looks like very simple but there's a constraint which complicates it and prevents me from finding an analytical solution.

Rules of the game:

• there are two types of points, called "Points A" (or shortly $A$) and "Points B" (or shortly $B$);
• the player must use these points to buy $n$ items, each one of them costs $700$ units of $A$ or $90$ units of $B$. In fact, the player cannot mix up $A$ and $B$, e.g. spending $350$ of $A$ and $45$ of $B$: he must choose if he wants to spend just $A$ or just $B$ for each item bought;
• each week the player can earn $286$ units of $A$ and $14$ units of $B$;
• to win, the player must buy all the $n$ items in the shortest time possible, that is, he has to find the optimal spending scheme according to the constraints.

Anyone can show me how to solve this game and/or to set the optimisation problem (if needed)?

-

you spend 700 units of A when you have more than 700, and 90 units of b when you have more than 90. so, for example, if you wanted 2 items, it'll take you 5 weeks because 5 times 286A is 1430A and 5 times 14B is 70B. (You can buy 2 items with 1430A)

Real answer: Supposing that i is 1 item, and w is 1 week:

Do A(i)=(700/286)w=(350/143)w and round that up to 3w. And for A(2i) it will be 2(350/143)w=(700/143)w then rounded up to 5w, and so on...

For B(i) it will be (90/14)w=(45/7)w and you round it up to 7w. And for B(2i) it will be 2(45/7)w=(90/7)w rounded up to 13w, and so on...

The formula for A is i=(350/143)w, and formula for B is i=(45/7)w.

Then you find a common multiple, which is the 2 multiplied together, and find how many i is in that. So, in (350/143)(45/7)w=(2250/143)w, you can buy ((350/143)+(45/7))i=(8885/1001)i.

So, the formula is (8885/1001)i=(2250/143)w. This can be simplified to i=((2250/143)/(8885/1001))w=(2250/143)(1001/8885)w

But, you need to add 1 as it initial starting amount of weeks. You can get 1 item in (2250/143)(1001/8885) weeks, And just to make life easier, (2250/143)(1001/8885) is approx 1.7726504

Remember, you can't get a week in a fraction, so you have to round it up every answer.

Proof:

To get 100 items, you will need 179 weeks ((1.7726504 x 100 rounded up)+1). In 179 weeks, you will get: (286x179)A=51194A to buy (51194/700)= rounded down to 73 items. You will also get (14x179)B=2506B to buy (2506/90)= rounded down to 27 items. 27 items plus 73 items is 100 items.

To get 270 items, you will need 480 weeks ((1.7726504 x 270 rounded up)+1). In 480 weeks, you will get: (286x480)A=137280A to buy (137280/700)= rounded down to 196 items. You will also get (14x480)B=6720B to buy (6720/90)= rounded down to 74 items. 74 items plus 196 items is 270 items.

Final formula: (punch it into your calculator and it'll work)

n=((2250/143)(1001/8885)n[rounded up]+1)w

-
Thank you all, guys. I voted Anonymous's answer because he was the first one to answer, albeit I really appreciated Lybra's asnwer :) – Lisa Ann Aug 14 '13 at 11:09
@Anonymous: please, notice that, according to Lisa Ann's first post, the cost of the item is 90 units of B, not 80 as it seems you assumed calculating $t_B(1)$. – Libra Aug 14 '13 at 12:02
oh... you saw nothing... – EpicGuy Aug 19 '13 at 8:49
Btw I changed my name to EpicGuy – EpicGuy Sep 13 '13 at 8:20

Agree with Anonymous, greedily buying items when you save enough money is optimal. That is, buy as soon as you have enough A, and buy as soon as you have enough B.

Assume, at last, you would buy $a$ items with A and $b$ items with B, all at the moment you earn enough points. Delaying purchase (but still using the same kind of points) of an item would not improve the time, as item prices are fixed, there is no interest, and there is no way to exchange points.

Assume, buying 1 item fewer with A and 1 item more with B would give shorter time. That means there were at least 700 A remaining using our method. Either you just earned enough A and enough B in the same week (which would not improve your time), or you have over 700 A in your pocket already last week, which contradicts our buying scheme. Therefore, switching from using B to using A would not improve the time.

Similarly, switching from using A to using B for an item would not improve the time either. Therefore, this heuristic is actually optimal.

-

The first heuristics than comes to my mind is to buy the items as soon as you get enough points $A$ or $B$.

For example, let's start at time $t = 1$, and assume that you get the points at the beginning of each day. Using points $A$, you can buy the first item at time $t_A(1)= \lceil700/286\rceil=3$, that is at the beginning of the third day (just after having received the points), when you have $286 \cdot 3=858$ points $A$. Using points $B$, instead, you can make your first purchase at time $t_B(1)= \lceil 80/14\rceil=7$ when you have $14 \cdot 7=98$ points $B$. Therefore, you first buy using $A$.

After this first purchase, you still have $858 - 700 = 158$ points $A$ and $42$ points $B$ (that is, $14 \cdot 3$). Therefore, for the next purchase your need either $700 - 158= 542$ points $A$ or $90-42 = 48$ points $B$. The next purchase can be at time $t_A(2) = t_{last\;purchase} + \lceil 542/286\rceil = 3 + 2 = 5$ or at time $t_B(2) = t_{last\;purchase} + \lceil 48/14\rceil = 3 + 4 = 7$. The term $t_{last\;purchase}$ for item $n$ is equal to $\min(t_A(n-1), t_B(n-1))$, and 0 for $n = 1$.

You can then repeat the process for the other items to buy, to find the "spending scheme".

-