Riddlers (09/18)
Centrifuges and Word Games
This week’s Riddler puzzles could both be solved analytically! I was really excited that I didn’t have to rely on an absurd number of Python simulations to check the solutions. I also discovered a deeper connection to number theory in a general form for one of the problems that I’m pretty excited about.
Riddler Express: Centrifuge Problem
You have to place 7 tubes in a 12-slot centrifuge such that the centrifuge is balanced (i.e., the center of mass is at its the center of the circle). You can assume the tubes all have the same dynamics.
At first, this problem seems impossible. After all, there is some notion of symmetry here, and 7 just doesn’t feel like a number amenable to any kind of symmetry. However, the key is to recognize that the superposition of balanced sets is also a balanced set.
In other words, if you need to place 4 tubes in the centrifuge, you can immediately see that placing them all 3 spots apart will result in a balanced configuration. But if you don’t see it immediately, you can also see that if you can place 2 tubes in a balanced configuration (by choosing diametrically opposing slots), then you can just repeat that process and you’ve put 4 tubes in a balanced configuration! The one caveat, of course, is that when you combine placements like this, you have to be sure that none of the slots are used twice (i.e., across two different placements).
Now, we can decompose 7 tubes like this and solve the problem! If we use 7 = 3 + 2 + 2, it’s pretty easy to see how we can superimpose these 3 balanced configurations to create one balanced configuration over the 12 slots.
Extra Credit
OK, of course I did the extra credit (nerd alert!). If we want to see how many configurations there are to put these 7 tubes in, we can just look at it as a combinatorial problem. We first assume some rotational symmetry (i.e., putting two tubes in slots 12 and 6 is the same as putting them in 1 and 7 and so on) so that we’re actually looking at the unique number of configurations.
Now, let’s place the 3 tubes (spaced 4 slots apart) however we want. There’s really only 1 choice to place the 3 tubes in a balanced configuration (can’t be decomposed into 2 + 1, since we can’t place 1 in a balanced configuration). So, all we’re choosing is where to put the two 2-tube arrangements.
Remember the one constraint we have in this decomposition view is that we can’t have two decomposed configurations using the same slot. The 3 tube configuration actually rules out 6 slots for us to put tubes in, since the 2-tube requires the tubes to be diametrically opposed. So there’s 6 remaining slots.
Choosing where to put 1 of the 2 tubes automatically determines where the other one will go (there is only one balanced configuration for 2 tubes). So, we have $\binom 32$ choices for how to arrange the 7 tubes.
Extra Extra Credit
The more interesting question is: for what values of $n$ and $k$ can we actually place $k$ balanced tubes in an $n$-slot centrifuge? We had this natural instinct about $k=7$ and $n=12$ that ended up being wrong. It turns out that you can think about this problem in the complex plane. Any time I see evenly spaced points around a circle, my instinct is to think about the roots of unity on the unit circle. These form evenly spaced points along the circumference, each of which maps to a slot on the centrifuge.
It turns out there’s a conjecture in number theory as follows: If $n\geq 2$ and $k\in [1,n]$, then you can find $k$ distinct $n$th roots of unity that sum to 0 if and only if $k$ and $n-k$ are nonnegative linear combinations (i.e., all coefficients are nonnegative) of prime factors of $n$.
The distinct caveat is important here. Basically, we need to make sure we don’t try to put more than one test tube into a slot. It turns out this conjectore was proved. Oddly enough, it was proved in the setting of this centrifuge problem!
If you don’t want to think of the roots of unity, then you can also equivalently express this condition as $k$ and $n-k$ must be expressed as a sum of prime divisors of $n$.
Riddler Classic: Word Games
So this problem actually took less time than the express did (probably because of my own tortuous extension of that problem). We have some $n$ words in a vocabulary, and we’re playing a game where try to guess what word was used this round. Every time we guess, the person tells us if the true word is alphabetically before or after our guess (or, if our guess is right).
If you’ve studied computer science algorithms, this is a very familiar form. We’re traversing a binary tree with $n$ nodes, and each time we get feedback on our guess, we choose which child of the current node to explore. If you’re familiar with this structure, then you’re probably inclined to shout out $\log n$ search time, just like I did! But this is actually wrong.
It takes $\log n$ time to traverse a binary search tree when you don’t know if your query is in the tree. In this problem, we actually know that the word the game gave us is in the tree. Conditioning on this success can give us a slightly better answer. It’s better when you look at it asymptotically, but I guess for the $n$ given in the problem, it’s a pretty incremental improvement.
Given that we know a path exists from the root to the node containing the correct word, we actually only care about what the path length is (i.e., how many queries we need to make). We can compute the expectation of the path length. The main assumption made here is that the game has a uniform distribution over all possible words in the vocabulary.
There is only one path from the root to any single node in the tree, a property of the construction of a binary search tree. Let $T(n)$ be the expected number of queries needed to find the correct word. Then,
The 1 here accounts for the initial iteration. I’m not going to compute this out for a general $n$, since it’s not necessary for the problem. But you can do it if you split the cases into whether or not the correct node is in the middle of the tree or is a leaf node.