About two and a half months ago I posted a challenge involving a sadistic math wizard, metal cubes containing rational numbers, and a room full of strange machines. I’ve been remiss in following up with some solutions. (Go read the first post and think about it before reading on if you haven’t already!)
I had fun creating an elaborate setup to frame the puzzle, but as you probably figured out, really the puzzle comes down to this: is it possible to figure out the numerator and denominator of an unknown positive rational number, if you are only allowed to take reciprocals, add, subtract, multiply, and test whether one number is less than another?
There are many ways to solve this. First, a few preliminary ideas which many commenters picked up on:
- The reciprocal of the reciprocal of is again—that is, —so we can use the reciprocator machine as a copying machine, in order to create multiple cubes with the same value.
- We can also multiply any by its reciprocal to create , that is, we can make a cube which we know contains the number . We can also make a cube containing by making a copy of any number and then subtracting it from itself.
- We can also use the reciprocator machine, in conjunction with multiplication, to implement division: to compute we reciprocate and then multiply the result by , since .
- We can use copies of the number , along with operations like addition and multiplication, to create a cube containing any positive integer we want. (We can also use subtraction to create any negative integer.) We can then divide such integers to create any rational number we want.
- We can test whether any two cubes contain equal numbers by putting them into the less-than comparator twice, once in each order. If the machine says “true” one way and “false” the other way, then one number is really less than the other. If it says “false” both ways, then the numbers must be equal, since this is the only situation in which both and are false.1
Given these preliminaries, the simplest method, put forth originally by Eric Burgess, is to methodically list all the positive rational numbers (creating each one by building up its numerator and denominator out of copies of the number ) and test each one to see whether it is equal to the wizard’s number. Since the rational numbers are countable, we can list them in such a way that every rational number appears at a finite position. This means that no matter what the wizard’s number is, after some finite amount of time we will encounter it in our list. (One very nice such list we might consider is the Calkin-Wilf order , …)
However, this could of course take a long time. For example, suppose the wizard has chosen . It turns out that this is the 4,285,192nd rational in the Calkin-Wilf order. Even if we can construct and test one rational number every 20 minutes (which actually seems overly optimistic, more on this later), it would still take us over years (with no breaks for sleeping or eating, and did you notice the wizard didn’t seem to provide a bathroom for us to use?). So we have to ask: is there a faster way?
If the machine says “true” both ways, then you should probably start thinking about deconstructing the machines and using the parts to build some kind of weapon or clever escape device.↩