You Have $1 Billion To Win A Space Race. Go.

You are the CEO of a space transport company in the year 2080, and your chief scientist comes in to tell you that one of your space probes has detected an alien artifact at the Jupiter Solar Lagrangian (L2) point.

You want to be the first to get to it! But you know that the story will leak soon and you only have a short time to make critical decisions. With standard technology available to anyone with a few billion dollars, a manned rocket can be quickly assembled and arrive at the artifact in 1,600 days. But with some nonstandard items you can reduce that time and beat the competition. Your accountants tell you that they can get you an immediate line of credit of $1 billion.

You can buy:

• Big Russian engines. Up to three, at $400 million each. Buying one reduces the trip by 200 days; buying two lets you split the payload and saves another 100 days (300 days in all).

• NASA ion engines. Up to eight $140 million engines, each needing 5,000 kg of xenon. Only 30,000 kg of xenon exists worldwide at $2,000/kg, so fuel for one engine costs $10 million. Each fully fuelled $150 million engine takes 50 days off the trip.

• Light payloads. Up to four return-fuel tanks at $50 million each, sent ahead. Each lightens the mission and saves 25 days.

What’s your best strategy to get there first?

The Riddler, FiveThirtyEight(original post)

Solution

This is a budgeted knapsack: maximise the days shaved off the trip without spending more than $1,000 million. Rank the options by days saved per million dollars. A fuel tank gives $25/50 = 0.50$, the first Russian engine $200/400 = 0.50$, a fuelled ion engine $50/150 \approx 0.33$, and the second Russian engine only $100/400 = 0.25$ (a third is both undefined and unaffordable, since three would cost $1,200 million).

Greedily taking the two most efficient buys, one Russian engine and four fuel tanks, costs $600 million for 300 days and leaves $400 million, enough for two fuelled ion engines: $900 million for 400 days, with $100 million stranded. But the lumpiness of the prices rewards a swap. Drop one fuel tank (giving back $50 million and 25 days) and the freed cash plus the stranded $100 million buys a third ion engine ($150 million, 50 days), a net gain of 25 days that spends the budget to the last dollar. An exhaustive search confirms this is the unique best plan: $$\boxed{\text{1 Russian engine}, \ 3 \text{ fuelled ion engines}, \ 3 \text{ light payloads}.}$$ It costs exactly $1,000 million and saves $200 + 3(50) + 3(25) = 425$ days, bringing the arrival forward from day 1,600 to day 1,175.

The computation

Enumerate every affordable combination of Russian engines, fuelled ion engines and fuel tanks (an ion engine saves nothing unless its xenon is bought too, and only six engines’ worth of xenon exists), and keep the one that saves the most days.

from itertools import product
re_save = {0: 0, 1: 200, 2: 300}        # Russian engines (a 3rd is unaffordable)
best = None
for r, i, f, x in product(range(3), range(9), range(5), range(7)):
    fuelled = min(i, x)                 # ion engines save only when fuelled
    days = re_save[r] + 50 * fuelled + 25 * f
    cost = 400 * r + 140 * i + 10 * x + 50 * f
    if cost <= 1000 and (best is None or (days, -cost) > best[0]):
        best = ((days, -cost), r, fuelled, f, x, cost)
(d, _), r, fuelled, f, x, cost = best
print(r, fuelled, f, "cost", cost, "days", d, "arrive", 1600 - d)