Claire and David, CEOs of rival tech companies, must decide whether to Share (S) or Keep (K) their algorithms. Profit payoffs (in $B for $billions) depend on a tech boom (probability p) or slump (probability 1 – p):
- Both S: Boom: $6B each; Slump: $3B each.
- One K, one S: K gets $8b (boom) or $0B (slump); S gets $2B (boom) or $1B (slump).
- Both K: Boom: gets $4b each; Slump: loses $2b each.
What do you think Claire and David should do?
Refining unobtainium to boldly go…
Bob Conger submitted a very detailed solution for this puzzle that we will post online below.
He correctly noted that since there was no time limit to the main part of the puzzle, only one processing unit would be necessary, as the concentrate and tailings outputs could be re-input into the unit, according to various scheduled sequences, to produce the necessary purity of the final output. Of course, producing any meaningful quantity of sufficiently pure output would take an astronomically long time.
Conger estimated that he would need a little fewer than 3 trillion processing units given the constraints specified in the extra credit.
From Conger:
This puzzle gave me happy memories of one of the first Jon Evan puzzles for which I remember submitting an extensive solution. That puzzle also involved refining a radioactive element, but the solution required putting the tailings from one stage back into the input of an earlier stage. The constraints and dynamics are interestingly different in this puzzle.
UNOBTAINIUM PROBLEM
Question 1: Minimum number of separation units needed.
I estimate that the separation processing plant will require that the ore go through 51 Stages of concentration, with a range of 1 to 26 processing units (“PU”s) per Stage, and a plant-wide total of 676 different processing units each handling a different concentration of incoming material.
Some of the PUs will be significantly underutilized. For example, in Stage 3, PU(2,0) intakes material that is the concentrated output of both Stages 1 and 2; it will be handling 1/81 as much mass as PU(0,2), which intakes the material that is the tailing output of both Stages 1 and 2. PU(2,0) will be idle 99% of the time. However, this issue will be resolved as we scale up to produce a useful volume of product: for example, to double the output rate of Stage 3 of the processing plant we need to incorporate an additional PU(0,2) but no additional PU(2,0).
Note: The notation PU(c,t) designates the number of times, c and t, the incoming material to that PU has been the concentrated output versus tailing output of a prior processing Stage. So Stage 3, for example, has three different PUs: PU(2,0); PU(1,1); and PU(2,2). )
Conceptually, we also could resolve the underutilization issue in a small-scale processing plant by rotating the same piece of equipment to serve in multiple underutilized capacities, (e.g., serving sometimes as PU(2,0) and sometimes as PU(1,1)) and thus reduce the number of physical pieces of equipment that the plant requires. In the extreme, if we were not in any hurry for the output, we could reduce the number of pieces of equipment to merely 51, or 26, – or even just 1 — pieces of equipment and constantly move equipment between the various (c,t) roles, but I interpreted that solution not to be in the spirit of the puzzle.
Extra Credit question: Create 1 million metric tons of final product in 90 days. How many separation units needed?
- I need 26.94 x 10^12 separation units operating around the clock for 90 days, including a special “sprint” processing protocol beginning as the last batch of feedstock enters the front end of the processing plant.
SOLUTION
- Following “s” Stages of processing, the material has been sorted into s+1different buckets, ranging from a bucket that has been the concentrated output at every one of the s Stages, to a bucket that has been the tailing output at every one of the s Stages.
- The concentration of the material in a particular bucket depends on the number of times it has been concentrated versus tailing output, but not the order in which that has occurred. In other words, material that was the concentrated output of processing unit PU(0,0) in Stage 1, and then the tailing output of PU(1,0) in Stage 2 has the same concentration as the material that was the tailing output of PU(0,0) in Stage 1 and then the concentrated output of PU(0,1) in Stage 2.
- The concentration of material in Bucket(c,t) following Stage s can be calculated with a binomial expansion. Let U represent the mass of Unobtainium, X represent the mass of Non-Unobtainium, and Z the total mass of material in Bucket(c,t). After Stage s:
U(c,t) = U(0,0) x (0.5 ^ (c+t)) x Binomial coefficient
X(c,t) = X(0,0) x (0.1 ^ c) x (0.9 ^ t) x Binomial coefficient
Z(c,t) = U(c,t) + X(c,t) total mass of material
U concentration in Bucket(c,t) is U(c,t)/Z(c,t)
Where:
c can range from 0 to s
t = s minus c
c + t = s for all the buckets that result from Stage s
The probabilities 0.5, 0.1 and 0.9 are based on the statement of the problem.
The Binomial coefficients get very large, but are easily determined in Excel by creating Pascal’s triangle.
- Since U is split between concentrate and tailings in a 50-50 ratio, the buckets that contain half of the total U in the most concentrated form are Bucket(s,0) through Bucket(s/2,s/2) following an odd-numbered Stage s. Similarly, following an even-numbered stage, the buckets that contain half of the total U in the most concentrated form are Bucket(s,0) through Bucket(1 + (s-1)/2, (s-1)/2 ).
- For my estimate in Problem 1, I decided to look for the Stage s after which Bucket(s/2,s/2) or
Bucket(1 + (s-1)/2, (s-1)/2 ) met or exceeded the target 99.9999% U concentration. This will give an overestimate of the number of Stages of processing required, since the total finished product will include Bucket(s,0), Bucket (s-1,1) etc which will have a higher concentration of U.
Focusing on the ratio of N(c,t) to U(c,t), which I denote as N/U(c,t), our goal is
N/U(c,t) = 0.999999/0.000001,
given N(0,0) = 0.000001/.999999
Solve for even value of s:
N/U(s/2,s/2) >= N/U(0,0) x (0.1 ^ (s/2)) x (0.9 ^ (s/2)) / (0.5 ^ s )
Which can be rearranged to
s >= 2 x LN[ (0.000001/0.999999) / (0.999999/0.0000001)] / LN [.09/.25]
s >= 54.09
Solve for odd value of s:
s >= 1+ {2 x LN[ (0.000001/0.999999) / ((0.999999/0.0000001) x (.1/.5)) ] / LN [.09/.25]}
s >= 51.94
The better result for odd value of s is expected, since c>t (more concentrations than tailings) when s is an odd number.
I select s=51, expecting that 51.94 is an overestimate.
s = 51 turns out to be a good estimate.
- By accumulating Bucket(51,0) through Bucket(26,25) I find that I have a quantity of material that is 50.00002% the mass of the original feedstock, with a U concentration of 99.99996%.
- Trying smaller values of s, I do not find any successful results.
- The number of processing streams in Stage s is generally equal to s. However, once we are past Stage s=26, there is no value in conducting further processing of any Bucket(c>=26), since all descendants (whether concentrates or tailings) of these buckets would be included in Bucket(51,0) through Bucket(26,25). Thus, we simply include any Bucket(c>26) directly in the cumulative calculations of the final product. Similarly, there is no value in conducting further processing of buckets any Buckets(t>=26) as all descendants of these buckets will not contribute to the final usable product. Thus, Stage 27 requires only 25 processing streams, and the number of processing streams similarly is 52-s for each s>26. Thus, the total number of processing streams across the 51 Stages of the processing plant is 676.
- Scaling up to the extra credit problem, we start with 1.99999992 x 10^12 metric tons of feedstock. Given approximately 2145 hours (see below in my point #8) to enter all this material in Stage 1, we need to be processing 0.932 x 10^12 KG per hour through Stage 1, so we need 0.932 x 10^12 individual processing units in Stage 1. (One metric ton = 1000 KG.)
Similarly, in Stages 2 through 26, we process 100% of the material in each Stage, though divided into increasing numbers of different streams per Stage. The allocation of the .932 x 10^12 individual processing units per Stage is not even across the different streams, but rather is proportional to the mass of material to be processed in each stream within that Stage. For example, in Stage 3, processing units PU(0,2) will be 81 times as numerous as PU(2,0).
Beyond Stage 26, we no longer process 100% of the material, as described in point #6 above. I calculate the mass of material that will continue to be processed at each Stage by calculating the mass of material in Buckets (c<26 and t<26) at each Stage s>26. The proportion of material that needs to be processed drops quickly, for example
Stage 26 100%
Stage 27 94%
Stage 32 8%
Stage 42 0.2%
Stage 51 0.00001%
Adding up the individual processing units required in each Stage, we arrive at a grand total of 26.9 x 10^12 individual processing units across the 676 processing streams in the 51 Stages.
- In step 7, I referred to 2145 hours. 90 days is 2160 hours.
The processing unit counts derived in step 7 require 51 hours to process a particular batch of feedstock through the entire system. However, we can accelerate the processing of all the material that is in the processing stream at the time the last batch is entered, as follows:
- When the last batch completes its processing through Stage 1, we now reallocate the .932 x 10^12 processing units from Stage 1, proportionately to all the other 675 processing streams, in proportion to the number of units already allocated to each stream. This reallocation when Stage 1 becomes idle, amounts to approximately 3.5% more processing units in each stream in Stages 2 through 51, and thus accelerates all of the material in the system by 3.5% compared to its “usual” pace. Thus, it requires about 58 minutes rather than an hour for all of the material in each the Stages 2-51 to clear to the next processing Stage.
- Similarly, 58 minutes later later, we can reallocate all of the 1.035 x 932 x 10^9 processing units from Stage 2, spreading them proportionately across all the remaining 673 processing streams, resulting in a 56 minute completion time for all of the material in Stages 2-51 to clear to the next processing Stage
- By the time the final batch has reached Stage 27, the 90% of individual processing units that were deployed to Stages 1 through 26 have been reallocated to Stages 27 through 51, resulting in a 6 minute processing time for all the material in Stages 27-51 to clear to the next processing stage.
- And so on. By the time the last batch reaches Stage 51, about 10^5 KG of material will be processed by all of the approximately 10^12 processing units, requiring less than 1/1000 seconds for the final batch to complete Stage 51.
- In total, this last sprint consumes just 15 hours to clear all the processing units.
- Thus, we have 2160 – 15 = 2145 hours available to enter material into the front end of the processing plant.
- This final sprint, while entertaining to envision, only reduces by about 2% the number of individual processing units that the solution would require in the absence of reallocating processing units as the final batch of feedstock makes its way through the processing plant.
