Can You Fend Off The Alien Armada?
Logic, Calculus; Difficulty: Easy
Can You Fend Off The Alien Armada?
The first Riddler of 2023 is a straightforward but interesting resource optimization logic Q. The Classic reproduced:
The astronomers of Planet Xiddler are back in action! Unfortunately, this time they have used their telescopes to spot an armada of hostile alien warships on a direct course for Xiddler. The armada will be arriving in exactly 100 days. (Recall that, like Earth, there are 24 hours in a Xiddler day.)
Fortunately, Xiddler’s engineers have just completed construction of the planet’s first assembler, which is capable of producing any object. An assembler can be used to build a space fighter to defend the planet, which takes one hour to produce. An assembler can also be used to build another assembler (which, in turn, can build other space fighters or assemblers). However, building an assembler is more time-consuming, requiring six whole days. Also, you cannot use multiple assemblers to build one space fighter or assembler in a shorter period of time.
What is the greatest number of space fighters the Xiddlerian fleet can have when the alien armada arrives?
*spoiler alert* solution and answer follow below
Solution :
From among the many numerous possibilities/combinations of assembler action at every time period, the solution follows from recognizing two fairly obvious points about any optimal manufacturing strategy:
- If any assembler is going to make more assemblers, then it has to be before commencing manufacturing of fighters.
- One cannot end up with a better solution (larger number of fighters) if one or more assemblers are making assemblers while other assemblers are making fighters. i.e. at any time, all assemblers are making assemblers or making fighters in an optimum solution
1 follows simply from the fact that if we make fighters from assemblers that later switch to making assemblers, we could immediately have increased fighter output by making the assemblers first!
2 has to be true because the output of any single assembler in time is independent/decoupled from the output of the others. So if at some point in the 100 days, we had one assembler making assemblers and another making fighters and one of them had greater final fighter output, we would obviously switch all assemblers to the plan that yielded more.
This implies that any optimum plan involves manufacturing assemblers up to a point in time and then switching all the assemblers to make fighters.
Let’s say the switch point is after \(n\) cycles. Each cycle lasts \(24 \ X \ 6 \ = \ 144 \) hrs, at the end of which the number of assemblers is doubled. So after \(n\) cycles, we have \(2^n\) assemblers. The time remaining is \(2400 \ – \ 144n \)hrs.
The number of fighters \(F\) that be produced with the \(2^n\) assemblers in the time remaining is:
\begin{align*}
F = 2^n(2400 – 144n)
\end{align*}
Now \(n\), the number of 6 day cycles we use to make assemblers can only take on integer values between 0 (when we don’t make any new assemblers) 16 (when we make assemblers for the first 96 days!).
All we need is to determine which of these 17 values of \(n\) maximizes \(F\)
A simple plot (shown below) reveals the maximum to be at n = 15 to give us a maximum of 7,864,320 fighters. That’s a formidable defense!
If you prefer to derive the maximum analytically, then treating n as continuous (vs. integer) and differentiating F gives:
\begin{align*}
F’ = 2^n \ (2400\cdot ln2 \ – \ 144 \ – \ 144n\cdot ln2)
\end{align*}
Setting this to 0 gives us \(n \approx 15.224 \) (straightforward to check that \(F”\) is negative at this value). Since \(n\) has to be whole, we only have to try \( n = 15 \) or \(n = 16\) to arrive at the same answer as above.
2 thoughts on “Can You Fend Off The Alien Armada?”
Actually this puzzle can be solved in your head with a simple reasoning.
An assembler will build another assembler if the additional assembler has enough time to build at least the amount of fighters missed during its construction – in other words, if the additional assembler can operate for at least another six days. (Exactly six days would be the point of break even where it doesn’t matter if you build another assembler or start building fighters.)
So the general rule would be: If there are 12 days or more remaining, build an assembler. If there are less than 12 days remaining, start building fighters.
By checking out multiples of 6 smaller than 100, you can easily find that the latter will happen after 90 days (= 15 cycles of 6 days), with 10 days remaining.
After that, 2^15 = 32 768 assemblers will build 10 ⋅ 24 = 240 fighters each, making up for a grand total of 7,864,320 fighters.
Excellent!