Ernie and the Disco Unicorn

Question

I was watching a bad movie on cable last week when my phone signaled a text from Ernie. The message read "Can you help me prepare my Disco ball for the Unicorn?". In some confusion I sent a "???" back but didn't get a reply, so I switched off the TV and jogged around to his place. As I approached I could see pulsing multi-coloured glow emanating from his living-room window, and I entered through the kitchen door to find Ernie hunched over a box of flashing lights, wearing a single white glove on his left hand. The box appeared to be constructed from a number of smaller cubes - some of these were flickering in bright colours, while others were variously transparent, mirrored, or opaque; a few seemed to be lit up with what looked like the ruby-coloured beams you see in laser pointers.

"I didn't think you were into the BeeGees...and aren't disco balls usually spherical?" I asked. Ernie carefully attached the cubelet he had been holding into his construction and turned to greet me. "Blame predictive texting", he growled, "I wrote DYSSQOBOL, not disco ball". He went on to explain. "DYSSQOBOL, stands for DYnamic menSuration of Space via a Quantum-Optical assemBlage of interferOmetric Lasers". Presumably I looked non-plussed so he explained in more detail. "Each of these...", he said holding up a small black cubelet with his white glove, "...is a programmable laser-interference device. The Skunk-works division of Acme Industries has lent me 125 of them for a month to see if I can demonstrate a practical application. They have adaptive-optical surface coatings so can switch instantaneously to any colour, reflectivity, and emissivity you desire, and each one has a tiny laser-interferometer at its centre that can be used to measure the distance to a neighboring cubelet accurate to better than a yocto-metre." I still looked confused, so he continued. "As you may know", (I didn't), "the General Theory of Relativity proves that time and space are warped by the presence of any mass - this assembly of cubelets should be accurate enough to detect spacial distortion resulting from the mass of a single mosquito flying past 100 metres away." "So it is an insect detector?" I ventured. "Of course not" Ernie replied scathingly. "According to my calculations it should enable me to measure the ripples in space resulting from the primordial Big Bang itself!".

"And the unicorn?", I ventured. "Uni-Con", he replied, enunciating very carefully, "predictive texting strikes again. The city is holding a Unicycle and Cognac festival in a couple of weeks, and that will be perfect for testing the equipment. The slightest vibration from traffic or even pedestrians walking the streets might be enough to drown out the subtle signals I am looking for. During the festival the streets will be closed to all vehicular traffic for the entire weekend, and if my calculations are correct, by Saturday morning the majority of the population will be lying motionless in bed - nursing a Cognac hangover or their bruises from misguided amateur unicycling attempts. So I should get 12 vibration-free hours for the experiment". I thought back to last year's ill-advised Festival of Tight-rope Walking and Whiskey Drinking and had to agree with Ernie's predictions.

"So what can I can do to help", I asked. "The problem is", he replied "I will need to concentrate on writing and debugging the control program. - so if you can rig up a suitable power supply for the experiment I will be greatly obliged". I asked for some more detailed instructions and, as he fitted the last of the cubes in place, he told me the following:

1) There are precisely 125 identical cubelets mounted into a perfect 5x5x5 cube.

2) In each measurement cycle, exactly four cubelets will be chosen randomly to operate in laser interometer mode - their centres will form the vertices of a (possibly irregular) tetrahedron.

3) Each of these four cubelets will send laser pulses from its exact centre to the exact centres of each of the three other laser cubelets, so together they can measure the exact lengths of all six edges of the tetrahedron.

4) Simultaneously, any cubelets lying directly in the path of any of the laser beams will turn transparent to allow the laser beams to pass through unobstructed, while any cubelets not in the path of a beam will remain opaque. Note that the edges and corners of all the cubelets have tiny chamfers, so cubelets for which the beam just glances along an edge or corner won't have to turn transparent.

5) After the measurements are recorded, all cubelets momentarily return to their default opaque mode, then steps 2-5 repeat throughout the 12 hours of experimentation.

6) A cubelet in laser interferometer mode requires precisely 1 kW to operate, a cubelet that is transparent requires precisely 100 W to operate, and an opaque cubelet requires precisely 10 W to operate (because its central processor is still operating of course). Note that the interferometer cubelets are automatically set to transparent mode, so don't need an extra 100 W in the case that they are in the path of a laser beam.

"So" I said, calculating out loud "we will need 4 kW for the interferometers and in the worst case scenario of all the other 121 cubelets all being transparent, a total of 16.1 kW should be sufficient - I could round that up to 17 kW just to be safe". "No!!!", Ernie protested, vehermently. "The cubelets are only prototypes - If you provide them with too much power they will overheat - I can't afford the risk of damaging them! The power supply should provide no more (or less) than the exact power requirement of the system when the four interferometer cubelets are in their least favourable (that is to say power-hungry) positions.". "But there must be thousands of combinations possible!" I protested. "Millions," Ernie replied, "so make sure you find the one with the most cubelets in the path of the lasers before you do your calculations". Then he turned to his lap-top and began programming.

So here is my problem. I have covered dozens of pages with scribbling and even built scale models, but just can't get to grips with exactly how many transparent cubelets there will be in the worst case scenario. And if I can't solve the problem soon Ernie will miss his window for the quiet 12 hours needed for his experiment (on the weekend following the Uni-Con the city will be holding a Death Metal Festival, and the Cannon Barrage Reenactment Society will be running the weekend after that - by which time Ernie will have to return the equipment to Acme Industries). Can anyone help me calculate the exact maximum power required for the power supply?

Answer 1

By exhaustively enumerating the $\binom{5^3}{4}=9\,691\,375$ possible choices of cubelets, I have discovered that the maximum number of edge-containing cublets is:

$38$

Corresponding to the configuration below:

This means that the maximum power requirement is:

$4\times 1~\text{kW} + (38 - 4)\times 100~\text{W} + (125-38)\times 10~\text{W}=8.270~\text{kW}$

I did this by first precomputing a lookup table of the cubes along each of the $\binom{5^3}{2}=7\,750$ possible edges. (Since there are only $5^3=125$ cubes I could store the edges as bits in a uint128_t, making the table "only" around 242 kB.)

Then, for each of the 9.7M choices of four cublets I took the union (bitwise OR) of the six edge sets from the lookup table and took the size (popcount) of the resulting set.

Here is the complete tally of my results (counting reflections and rotations separately)

 cublets  # of configurations
 ----------------------------
      4    8,094
      5   21,852
      6   66,696
      7  115,980
      8  230,664
      9  277,485
     10  423,336
     11  523,356
     12  628,952
     13  677,393
     14  730,068
     15  752,100
     16  767,916
     17  718,626
     18  654,444
     19  608,596
     20  537,016
     21  452,229
     22  376,700
     23  304,116
     24  238,560
     25  179,884
     26  130,842
     27   94,800
     28   67,500
     29   46,336
     30   27,846
     31   14,396
     32    8,040
     33    4,632
     34    1,680
     35      912
     36      264
     37       16
     38       48
 

Answer 2

So the question is really to

count the maximal number of cubelets in transparent mode.
If there are $n$ of them, then the power needed is $4\times1000+n\times100+(121-n)\times10=5210+90\times n$ Watts.

A lower and upper bound for

this maximal number is 18 and 66 respectively.

The lower bound comes from an actual setup where the interferometer cubes are in 4 corners of the large cube, so they are pairwise in opposite corners of a side of the cube. (See the blue cubelets on the picture in the next paragraph.) Any two of these have 3 cubelets between them, different pair of interferometer cubes on different sides of the cube, so those between them are all distinct cubelets, that's $6\times3=18$ in total.

However, this case is special because of the laserlight passing through the edges of the cubelets.
In a more usual case a laserlight which goes through two cubelets which only share an edge between them, it is done through one of their common neighbours. Two cubelets in opposite corners of the cube can be reached through 11 other cubelets with a path in which consecutive cubelets share sides. Four cubelets make 6 different pairs, hence $6\times11$ is a very rough upper bound - actually the 4 cubelets can not all be in opposing corners to each other, and the sets of cubelets between those pairs probably have some common elements, which should not be counted twice.

There are some parts of the question for which I have a generic method.

How many cubelets need to be transparent between two interferometer cubelets, whose coordinates are $[x_1,y_1,z_1]$ and $[x_2,y_2,z_2]$?
Noting the absolute distances for each coordinate with $[d_x,d_y,d_z]=[|x_1-x_2|,|y_1-y_2|,|z_1-z_2|]$ the answer for this is something like $d_x+d_y+d_z-\gcd(d_x+1,d_y+1)-\gcd(d_x+1,d_z+1)-\gcd(d_y+1,d_z+1)+2\gcd(d_x+1,d_y+1,d_z+1)$, where $\gcd(\cdot)$ notes the greatest common divisor.
This expression relies on the fact that among the transparent cubelets there have to be one for each of the $x$ coordinate range between $x_1$ and $x_2$ ($d_x-1$), and also for the other two coordinates. (analogous expression with $d_y$ and $d_z$ instead of $d_x$) For each coordinate-pair, we have to subtract the amount of edge-crossings ($\gcd(d_x+1,d_y+1)-1$ and analogous expressions), but then we have counted corner-crossings ($\gcd(d_x+1,d_y+1,d_z+1)-1$) three times, so we have to add the double of that amount back. But I'm not sure in this last term, and the expression seems to have some error in some cases.
Ok, I have to think this through. Although this expression works well for estimation, it is far from being correct. I'm working on cleaning it.

My guess is that the solution

for $n$ is exactly in the middle of these bounds: 42. That would have a power need of 8990W, that is approximately 9kW.
I think a setup which needs 42 transparent cubelets can easily be shown: just put a slight rotation on the maximal tetrahedron fitting in the cube, so its corners are neighbouring the corners of the cube. Here it is on a picture to help understanding:
(Blue cubelets are interferometers for the $n=18$ case. Brownish ones - and the fourth blue corner - produce 33, if my method above for counting is correct. That one immediately gives a new lower bound, and I think it's not that far from the optimal value.)


But I might be totally wrong. It's just my mathematical intuition speaking.