Counting your way out of hell

Tom Waits as your tormenting Devil

Today I have some riddles and games for you. The game is called counting your way out of hell and involves a simple a little story. You have died and been banished to hell for the many transgressions you have committed during your life (such as this or this). In any case Satan (played by Tom Waits) offers you a way out. He proposes a challenge (said in a classic Waitsian drawl):

I'm gonna think of a number, it's gonna be positive whole number like 1,2,3 or 57823. It can be as big as I want. Now you have to guess what it is, but you have as many guesses as you want.

So you think to yourself, this is a pretty sweet deal. Since you have been damned for all eternity you have time for quite a few guesses. So how do you do it?

So this is an easy one. I'm sure you've figured it out. So you start at 1, and the 2, 3, 4 and so on. And you know that eventually you are gonna get there. It may take a long time but eventually you'll get there, and you do. The Devil is marginally impressed and stroking his pointy beard proposes a slightly more difficult challenge:

So now I'm gonna think of another number, this time it can be positive or negative. Same rules, you get as many guess as you want.

This one's a bit more difficult. If you try your original strategy and Old Nick guesses a negative number you are never gonna get there. But with just a simple modification you figure it out. If you follow every positive guess with a negative one then you get there, something like 1,-1,2,-2,3,-3 and so on. Once again whatever the number is you are guaranteed to eventually guess it.

Satan grins, knowing that he has just been warming you up. He gives his final challenge:

This time I'm going to think of a fraction. It can be any positive fraction, proper or improper (i.e. ¹⁄₄ or ⁷⁄₃). You get as many guesses as you want. If you guess the right number then you get go to back to your life.

Now this one is tricky, and it takes a bit of thought. Think about it for a few minutes.

There are a couple of (wrong) ways you could try this. You could try every simple fraction with a numerator of 1, something like ¹⁄₁, ¹⁄₂, ¹⁄₃, ¹⁄₄ and so on. But then if the Devil guesses ²⁄₃ you are never gonna guess it and you'll be spending all of eternity in the fiery abyss. Similarly if you pick any other single Numerator (the top number in a fraction) or Denominator (the bottom number in a fraction) and try all of possibilities. However, there is a way.

Imagine the fractions on a grid, with the one axis being all the denominators and the other being all the numerators, such as the one shown below. Then all you have to do is count them off on each diagonal starting at the top left corner. Below is a little animation of this system for numerators and denominators between 1 and 9. Click the "Go!" Button to start it.

	Denominators
N u m e r a t o r s

It should be clear that if you continued this pattern for long enough you would eventually reach any fraction. Realising this you eventually guess the correct fraction (and really no matter how long it takes you it's a lot shorter than eternity). Reluctantly the Devil has to let you go, strangely the Devil seems bound by verbal contracts just like everyone else. And that's how you count your way out of hell.

Mathematically this is all possible because Natural Numbers, Integers and Rational Numbers(Fractions) are all Countable. What this essentially means is that you can create a system (a bijection technically) that can assign a Natural Number (1,2,3,etc.) to each and every Integer and Rational Number. With Integers it was pretty obvious how to do it but with the Rational Numbers the system explained above is called a Cantor Pairing, after the Mathematician Georg Cantor.

Countability is an important concept when we want to talk about the size of infinitely large sets. There are an infinite amount of Natural Numbers and Real Numbers, but in some sense we feel that there should be "more" Real Numbers than Natural Numbers. To define this idea we use the idea of countability. In some sense we say that the infinite amount of Natural Numbers is the same as the infinite amount of Integers and is also the same as the infinite amount of Rational Numbers - they are all countable. However, we can prove that the Real Numbers are not countable (which I will not show here, but has a simple elegant proof you can look up here), they are uncountable and strictly larger than than a countable set. The fact that Rational Numbers are countable is surprising since in between 0 and 1 there are infinitely many Rational Numbers, yet despite that we consider the set of all Natural Numbers and the set of all Rational Numbers to be the same size.

Cantor's pairing function can be seen as a way of encoding two numbers into one number, which you can see if you consider a fraction ^a⁄_b to just be a pair of numbers (a,b). The function can easily be extended to encode any amount of numbers, for example (a,b,c). It can even be used to encode tuples where you don't know the length by first encoding the length of the tuple and then encoding the the tuple in a single number and then taking the cantor pairing of those. The consequence of this is that a surprisingly large amount of sets turn out to be countable. For example:

• Rational Numbers
• Polynomials
• Algebraic numbers
• All polygons with integers length sides (I'm guessing on this but it seems obvious)
• All Computer programs

Because we can number all these things we can use them much more easily in proofs, and we sometimes make very surprising relations between one and the other.