This week's Riddler is a race into space:
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. There are only three in the world and the Russians want $400 million for each of them. Buying one will reduce the trip time by 200 days. Buying two will allow you to split your payload and will save another 100 days.
- NASA ion engines. There are only eight of these $140 million large-scale engines in the world. Each will consume 5,000 kilograms of xenon during the trip. There are 30,000 kg of xenon available worldwide at a price of $2,000/kg, so 5,000 kg costs $10 million. Bottom line: For each $150 million fully fueled xenon engine you buy, you can take 50 days off of the trip.
- Light payloads. For $50 million each, you can send one of four return flight fuel tanks out ahead of the mission, using existing technology. Each time you do this, you lighten the main mission and reduce the arrival time by 25 days.
What’s your best strategy to get there first?
If we want to get there first, it seems like we should try to get there as fast as possible, so as a first pass let's see if we can optimize for the number of days saved. One way to attempt this is to view the items in terms of their days saved per dollar. For example, a single Russian engine costs $400M and will save 200 days, so that's 0.5 days per dollar (D/$). However, the second Russian engine would only save us another 100 days, for a value of 0.25 D/$. Each NASA ion engine paired with the necessary amount of xenon will cost $150M to save 50 days, for a value of 0.333 D/$. And the light payloads, at 25 days saved for $50M, provide a value of 0.5 D/$.
So for the best value, we might want to buy one Russian engine and all four light payloads. This will cost us $600M and save us 300 days. For another $300M, we could buy two ion/xenon combos to save another 100 days, so in total we can save 400 days by spending $900M. That's pretty good, but we still have $100M left over and nothing to spend it on, which seems suboptimal. We can actually do a little bit better - if we buy just 3 light payloads, that will free up an additional $50M with which we can add another ion/xenon combo. Now we've spent all $1B at our disposal, and will save a total of 425 days on the trip.
That's the fastest we can get to our destination, but it's actually not the solution to the puzzle. We're not just racing against the clock, we're racing against other people. Specifically, let's assume that we have a single rival with an unlimited budget. Whatever resources we don't buy, he will purchase and use to try to beat us. In our 425 day solution above, we left 2 Russian Engines, 3 ion/xenon combos, and a light payload on the table for our rival to use. He can buy them all and they'll save him 300 + 150 + 25 = 475 days! So by optimizing for speed, we actually lose the race. We need to rethink our approach.
The key to solving this is taking advantage of the fact that the worldwide resources are limited. The puzzle doesn't require us to get to our destination as fast as possible, it just asks us to get there before anyone else. There are arguably a few ways to interpret our specific challenge, but either way it turns out that there are a number of ways to solve it.
One way to interpret the puzzle is to win the race to our destination for the least amount of money possible. This is probably how we'd approach the problem in the real world, right? Up to this point, I've been combining the NASA ion engines with their required xenon fuel as a single purchase, but we should now consider them separately. If our goal is not only to get to the alien artifact quickly but also to prevent our rival from getting there quickly, the cheapest way to slow him down is by buying up the world's supply of xenon - it's inexpensive, and without it the NASA ion engines are useless.
For just $60M we can buy all the xenon, meaning the ion engines are now worthless to our rival. For another $200M we can buy all four light payloads. This doesn't leave us enough money to buy two Russian engines, but that's ok. We can buy one for $400M, and also buy a single ion engine for $140M. Thus we've spent a total of $60M + $200M + $400M + $140M = $800M, and the number of days we save is 200 (from the Russian engine) + 50 (from the ion engine) + 100 (from the light payloads) = 350 days. More importantly, this leaves just two Russian engines for our rival, meaning he'll only save 300 days. So we'll win the race with $200M left to spare! (Technically our opponent could also buy 7 NASA ion engines, but without any xenon they won't do him any good.)
What if, instead of optimizing for cost, our goal is to beat our rival by the largest margin? We might want to give ourselves the largest lead time possible to study the artifact by ourselves. Our approach above has us winning the race by 50 days, but we can do better. The simplest and cheapest way is to take our solution above and buy one more NASA ion engine. This will save us an additional 50 days (bringing our total to 400 days saved for $940M spent) and our rival can still only save 300 days, meaning we'll have the artifact all to ourselves for 100 days.
There are actually two other solutions that allow us to win by a 100 day margin, and in fact there are a total of 12 unique solutions that allow us to win the race by buying various quantities of the available resources. I described two of them above, and I'll leave the rest of them for the reader to find.
EDIT: It occurred to me after writing this that I may have been misinterpreting the last part of the puzzle, and it turns out I was:
@luckypri_me nope. anyone can lighten their payload if they choose (and pay).
— Oliver Roeder (@ollie) April 18, 2016
There still doesn't appear to be a single unique solution to the puzzle (which is mildly disappointing), but the correct solutions we do get are slightly different than the ones I arrived at previously. In particular, the $800M solution I described no longer works, since it relied on the idea that if we sent out 4 light payloads, our rival couldn't send any.
Now I know that our opponent will always send four light payloads (since I've assumed he has an unlimited budget), and he'll also always buy at least one Russian engine since we can't buy all three of them. So at best (or worst, depending on your perspective) he will always save 300 days on his trip time. If we let him buy a second Russian engine, that increases to 400 days, and that's a total we can't beat.
So we need to buy two Russian engines, not only to speed up our own trip but to ensure that our rival doesn't get a second one. That leaves just $200M to spend to ensure our victory, which we can still do by simply buying up all the world's supply of xenon for $60M. We then have $140M left to either (a) buy a NASA ion engine or (b) send out one or more light payloads. The latter is sufficient for the two cases we tried to optimize for above:
- If we want to save money, we send a single light payload. This saves us a total of 325 days for $910M spent.
- If we want a larger margin of victory, we send two light payloads. This saves us a total of 350 days for $960M spent, so we beat our rival by 50 days as opposed to 25.
- If we're willing to sacrifice both of those in the interests of getting there as quickly as possible, we could sacrifice 5,000 kg of xenon to send out a third light payload. This saves us 375 days for a total of $1B. However, our rival will buy the xenon we left, which allows him to save 350 days. We still win, but for more money than the first option, and by not as many days as the second option.