The wizard’s rational puzzle (solutions, part 1)

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 $x$ is $x$ again—that is, $1/(1/x) = x$ —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 $x$ by its reciprocal to create $x \cdot 1/x = 1$ , that is, we can make a cube which we know contains the number $1$ . We can also make a cube containing $0$ by making a copy of any number $x$ and then subtracting it from itself.
We can also use the reciprocator machine, in conjunction with multiplication, to implement division: to compute $x/y$ we reciprocate $y$ and then multiply the result by $x$ , since $x/y = x \cdot 1/y$ .
We can use copies of the number $1$ , 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 $x < y$ and $y < x$ are false.¹

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 $1$ ) 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 $1, 1/2, 2, 1/3, 3/2, 2/3, 3, 1/4, 4/3$ , …)

However, this could of course take a long time. For example, suppose the wizard has chosen $1397/5331$ . 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 $160$ 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.↩

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

3 Responses to The wizard’s rational puzzle (solutions, part 1)

William Tanksley says:

October 24, 2018 at 12:04 pm

Stern-Brocot is the most efficient answer — but not the sequence, the tree.

We will consider 4 boxes with initial values given below to be a single matrix, accessed as (m1, m2, m3, m4), where [m1 m3] and [m2 m4] are the two row vectors of the matrix. m1/m3 will be the left limit of the current search, and m2/m4 will be the right limit of the current search. We will speak of “replacing the right limit with the mediant” and “replacing the left limit with the mediant”, which is performed by replacing the respective row vector with the two elements of the mediant in the same order as the mediant.

Recall how to test for equality, and define an operation called “mediant” (q.v.), which takes 4 boxes representing a 2×2 matrix, and returns 2 boxes representing a fraction (numerator and denominator): n/d = (m1+m2)/(m3+m4).

First, construct zero and test for negative or nonnegative (using the less-than operator). If nonnegative, test the unknown for zero (and report success if it works).

Next, begin the loop: construct 4 boxes forming either the identity matrix or the negative of it (depending on whether the unknown is positive or negative, respectively). You’ll need to keep track of the unknown and 4 boxes. To conduct each loop step, form the mediant for the current matrix and test for equality (report success if it works). Otherwise if the mediant is less than the unknown, replace the left limit with the mediant; otherwise replace the right element with the mediant. Continue the loop.
- Pavel says:
  
  October 27, 2018 at 4:19 pm
  
  I also used Stern-Brocot tree, but in a more straightforward way. The rational being searched for is (p, q).
  1. Set lower bound = (0, 1), upper bound = (1, 0) (that’s a “pseudo-rational”), steps = 0
  2. Iterate:
  2.1. Create the mediant from the lower and upper bounds: (a, b) “+” (c, d) => (a + c, b + d)
  2.2 Compare (p, q) with the mediant:
  2.2a. If equal, then we found (p, q) in the tree. Report the number of steps.
  2.2b. If greater, set the mediant as the new lower bound. Increment the number of steps.
  2.2c. If less, set the mediant as the new upper bound. Increment the number of steps.
  
  The rational 1397/5331 can be found in 22 steps.
Pingback: The wizard’s rational puzzle (solutions, part 2) | The Math Less Traveled

Comments are closed.