## The wizard’s rational puzzle (mind your p’s and q’s!)

You have been abducted by a sadistic math wizard (don’t you hate it when that happens?). He ushers you into a plain but cozy-looking room, with a hardwood floor, a few exotic-looking rugs, and wood paneling on the walls.

He hands you a small polished metal cube. “Inside this cube”, he explains, “is a positive rational number. If you can correctly tell me its numerator and denominator in lowest terms, I will let you go free. If you guess wrong, though…” He pauses to indulge in an evil chuckle. “Let’s just say that my sharks are hoping you will fail.” He strides out and slams the door behind him. Of course you try to open the cube, but you can’t find any way to do it: you don’t see any hinges, or a lid, or even any kind of seam at all, just smooth metal. You try throwing it on the floor to see if it will shatter, but you only succeed in denting the floor. You next try the door, but of course it is locked, and seems extremely solid.

You sigh and start to look around the room. There are no windows, but you quickly notice that a few of the wooden panels have various holes, knobs, and inscriptions on them. You go to examine them more closely.

On the west wall is a panel labelled “RECIPROCATOR”. To one side there is a square hole labelled with the letter $x$; next to it is another hole labelled $1/x$. The holes look like they might be just about the same size as the metal cube, so you hold your cube up next to the hole labelled $x$ to compare their sizes. Suddenly, with a whirring sound, something starts to pull the cube out of your hand, into the hole; you desperately try to hang on, but the mechanism is too strong. You experience a brief moment of panic as the cube slips from your fingers, but instead of disappearing, it stops as soon as it is flush with the panel. There are more whirring sounds from inside the wall, and a few moments later, your cube slowly emerges from the hole again, along with new cube from the hole labelled $1/x$. They look identical; you are extremely glad at this moment of the decision you made, eleven years ago, to carry a permanent marker in your pocket at all times Just In Case. You carefully label the original cube and the new cube so you will not get them mixed up, since you are starting to get the feeling that you might end up with a lot of these.

On the north wall is a panel labelled “ARITHMETIZER”. There are three square holes: one labelled $x$, one labelled $y$, and one labelled $x + y$. However, you notice a little knob below the $+$ symbol; by turning it you are able to change the $+$ into $-$ or $\times$. You turn it back to $+$ and, sure enough, when you put your two cubes next to the holes labelled $x$ and $y$, they are sucked into the machine briefly, and after some whirring sounds they spit back out, along with a third cube (which you carefully label) ejected from the third hole.

The east wall has no panels, but it does have a window with a stunning view of the forest you were hiking in just a few hours ago. You realize, belatedly, that the stories that crazy old man at the lodge told about the “haunted math forest” may have had some truth to them after all.

On the south wall is a panel labelled “COMPARATOR”, with two holes labelled $x$ and $y$. To the right of those holes, under a blank space on the panel, is a label that reads $x < y$. You try putting in your original cube and the one that came out of the ARITHMETIZER. After the usual whirring, part of the panel over the label $x < y$ slides open for a few seconds, revealing a giant letter T. You swap the two cubes and put them back in, and sure enough, this time the panel slides open to reveal a giant letter F.

In the middle of the room is a small table with a chair and a lamp. On the desk, it looks like the wizard has thoughtfully provided you with a quill, a pot of ink, and a stack of blank paper. You have the first few ticklings of some ideas, so you sit down at the desk, look thoughtfully at the ceiling for a few seconds, then begin to write.

Can you escape? Or will you be feeding the sharks? What’s your best strategy?

Steel cube photograph by Zai Divecha Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in arithmetic, challenges, logic, programming, puzzles and tagged , , , , , . Bookmark the permalink.

### 15 Responses to The wizard’s rational puzzle (mind your p’s and q’s!)

1. Eric Burgess says:

I’ll get the ball rolling with a bad solution. I can create 1 as x(1/x), so I can create any positive integer by adding successive 1’s. Therefore I can create any positive rational using the division function. So I’ll just enumerate the positive rationals and start trying them…after some finite (but potentially very large) number of tries, I’ll find the right one, which I’ll recognize because I get the giant “F” from the comparator for both x<y and y<x.

If I'm interested in not dying of old age or going insane, I'll probably think about continued fractions instead.

• xander says:

I agree that your first solution is not a good one (there is no guarantee that the process would terminate). My second idea is similarly problematic: use bisection to hone in on $x$ (we can construct any dyadic rational, then compare away). Again, this won’t generally terminate.

On the other hand, my first thought was continued fractions (I went on to the second thought because I didn’t want to think about implementation, but it seem to be absolutely the right idea). This makes sense, as a number is rational if and only if it has a terminating continued fraction expansion, so we just have to work out what that expansion is.

Thinking in terms of subroutines required, we’ll need a way of getting integer and fractional parts—the rest is just(!) arithmetic. The integer part of a number $a$ can be found by comparing $a$ to the natural numbers (which can be constructed recursively as you describe, starting with 1—some kind of bisection argument will make things go faster), and the fractional part is just $a$ minus the integer part. Iterate the usual algorithm for finding a continued fraction expansion until the fractional part is zero, then work out the arithmetic to recover the original number.

• Eric Burgess says:

My bad method is guaranteed to terminate, unlike bisection. As soon as the target rational is chosen, and an enumeration of the rationals is fixed, we (the omniscient we) immediately know the target number’s position in the enumeration, and thus how many tries the prisoner will need to find it.

The downside is that it’s not guaranteed to terminate in any bounded time. (The prisoner knows N exists and is finite, but has no idea how big N may be.) However, my gut insists that’ll be a limitation of any method. I’m interested in hearing what we come up with for formally deciding that one method is better than another, and by how much. I suspect it’ll depend on how the wizard chooses the target rational, since there’s no uniform distribution.

• Brent says:

That works! Of course you’re right that it’s not the fastest.

2. John Doe says:

I’ll get the ball and propose two variants based on continued fractions, as I’d like to go out before the heat death of the universe.

As said previously, with x and 1/x, we can create 1, and from here every rational. I’m only interested by the integers.
Also, I can test equality between any x and y, as stated in the previous comment.
Last note: given x, either x = 1 (in that case I can test it, and exit the room), or one of x and 1/x is > 1, and *I know which one*.

Now we have x = p/q > 1.
The goal is to find the integer a > 1 such that a < x a. If so, we double a and try again. Eventually, we will find k such that 2^k < x <= 2^(k+1). If the equality holds, we are done, and we found x.
Otherwise, we then find by dichotomy of this interval the integer a such that a < x <= a+1 holds.

With both methods, we now have an integer a such that a < x 1, and we can start again recursively, until we find the exact rational value of x’, by recursion. Then we know the exact value of x = 1/x’ + a.

Now, for the analysis of the complexity.
With both variant proposed, the number of recursions steps needed is proportional to the “length” of the continued fraction expansion of x ; and the complexity of each individual step is the complexity of finding the good ‘a’ integer. This complexity depends only on the actual value of a itself, that is the value of the coefficient of the continued fraction expansion at this level.

Now, we know that, for a rational number, the “length” (or “depth”) of its CFE is always < log(q)/log(phi)+1 = O(log(q)), where phi is the golden ratio (cf. Wikipedia for example).
Now, for the complexity of the variants, where we are looking for the number a.
For the first variant, the analysis is simple: we need O(a) steps.
For the second variant, when we first widen the intervals, we do that O(log(a)) times, and after the dichotomy in an interval of length O(log(a)) costs O(log(log(a)). So the overal complexity is O(log(a)).
Now, we know that the value of a for each step is the coefficient in the CFE of a rational number, which is at any level is < q (expect maybe the very first one, which is < p).

All together, it means that the complexity of the first variant of the algorithm is O(q*log(q) + p).
And for the second variant O(log(q)^2 + log(p)).

I'm curious if that's the best we can do, though…. My guts tell me yes…

• Brent says:

Very nice! Although it looks like maybe some of your comment got omitted? I’m guessing probably due to less than and greater than signs being interpreted as HTML tags and stripped out. If you write &gt; in place of > and &lt; in place of < they will stick around.

• John Doe says:

Indeed, it looks like whole paragraphs have disappeared 😦 …..
For a math blog, maybe you’d want to disable HTML yeas, but be sure to enable the and = symbols. Which are quite common in math :-). I’m quite sure the culprit here is either Akismet, or the WordPress comment parameters themselves, configured to strip HTML, as opposed to authorize text-only comments.
Also, maybe you could enable LaTeX syntax in the comments 🙂 : $$\int_\mathbb{R} e^{-x^2} \mathrm{d}x = \sqrt{\pi}$$
My 2 cents :-).

• Brent says:

I’m not sure how much control I have over the HTML escaping in comments, since the blog is hosted on wordpress.com. But LaTeX syntax already is enabled in the comments! You just have to enclose things in $latex ...$, but without the space in between the dollar sign and the l. Like this: $\sqrt{\pi^2/8}$

3. Kaligule says:

Let $x$ be the searched number.

– If we want, we can make infinite copies of every number that we already have.

– We can test for equality (by comparing $a$ with $b$ and $b$ with $a$)

– We can construct $0$ and $1$ (and also all the integers and rational numbers if we need to).

– We can negate a number and test if it is negative or positive. So the sadistic math wizard made it a bit easier then necessary for us by stating that the searched number is positive. That wouldn’t have been necessary.

– If we know a number to be an integer we can find it relatively fast by comparing it to $1$, $2$, $4$, $8$ and so on and then doing a binary search.

– We have all the operations needed for an Euclidean algorithm (note that we don’t need a modulo operation for it, we can just continue to subtract the smaller number from the bigger one until they switch places). We can even do the extended version if we keep track of how often we had to subtract.

– By doing the extended Euclidean algorithm on $x$ and $\frac{1}{x}$ we can find two integers $n$ and $m$ so that $x \cdot n + \frac{1}{x} \cdot m = 0$. (The extended Euclidian algorithm does work on rational numbers.)

– Since we know that $n$ and $m$ are integers, we can find them relatively fast by comparing them to $1$, $2$, $4$, $8$ and so on and then doing a binary search (of course, check the signum first).

– The equation $x \cdot n + \frac{1}{x} \cdot m = 0$ is equivalent to $x^2 = - \frac{m}{n}$. So all we have to do now is to calculate two integer square roots, which we can do with our marker on the floor, without using the cubes.

(We should probably make sure that $x$ is completly reduced at that point, though I am pretty sure it isn’t necessary since the extended Euclidean algorithm should give us coprime $n$ and $m$. But I wouldn’t risk it while facing the sharks.)

This was great fun. The best thing is that we didn’t have to write $x$ as a fraction, so we don’t have to mind any p’s or q’s.

It would be nice to have a heatmap of all possible positive fractions which shows how many steps we needed.

4. Kushal Chauhan says:

We can do it using the good old binary search:
1. First, get 0 using $x - x$.
2. Get 1 using $x(1/x)$.
3. Get 0.5 using $1/(1+1)$.
4. Compare x with 1:
3.1 IF x 1: x’ = 1/x
(So that x’ lies between 0 and 1)
3.3 ELSE return p=1, q=1
5. Set high = 1 and low = 0
6. Set mid = $0.5*(high+low)$
7. Compare mid and x:
7.1 IF x mid; low = mid, GOTO 6
7.3 ELSE return p = numerator of mid, q = denominator of mid (or vice versa if x’ = 1/x in STEP 4)

• Brent says:

Binary search is a nice idea, and it would work great if we were searching for an *integer*, but I don’t think it will work here. For example, what if the number was 1/3 ? Do you see why this won’t work?

• Kushal Chauhan says:

Oh yeah! In the case of 1/3, or for any other fraction where the denominator is not a power of two, the algorithm will not terminate. Great catch! Love your blog!

• Brent says:

Right! And thanks!