beavers Who are Busy

This post is something of a fun introduction to the kind of stuff I want to do for this blog. Here I’ll show a puzzle, and if you want to, you can pause after reading it to try and solve it for yourself before reading on. If you feel like having a hint, or if you’re just here for the show, that’s fine too (of course it is, what can I do to control you anyway?).

The Puzzle:

Two Genies Play a Game (He said it!). The genies are named Djimmi and John. The game goes like this: Each turn, Djimmi chooses any finite string of digits, and sticks it on the end of the running string of digits (like concatenation), and John chooses one digit and puts it at the end of what Djimmi just chose. The running string starts out as just a “0.” (read as “zero-point”, it’s not a letter!). If, after an infinite number of turns, the number the two genies make ends up being rational, then Djimmi wins, if its irrational, John wins (though I’m not sure either of them can really be called winners playing this dull game for infinity).

For example, Djimmi could choose to first place down “1224”, making 0.1224, then John might place down a “1”, making 0.12241, if Djimmi placed down “1224” again, and John placed down “1” again, and so on and so forth, they would make the decimal number 0.(12241) repeating. This is exactly equal to 12241/99999, so Djimmi would win here.

The question is: If both the genies play perfectly, who will win? Can you prove your answer is correct?

Hint Incoming!

There exist things called “Pairing Functions”, which map pairs of positive integers to individual positive integers (look it up!)

Solution:

To prove that either of the genies will win, it’ll be enough to just find a strategy that guarantees their victory. Since every single rational number has a periodic decimal form (it has a finite nonrepeating part followed by an infinite repeating part), it seems as if, in order for Djimmi to win, John will have to play along with his choices for infinity, so it makes sense to start looking for a strategy that’ll guarantee John’s win.

Looking for a bit will yeild the following optimal strategy:

Using any pairing function (If you don’t know what I’m talking about, look back at the hint!) we can assign a rational number to a positive integer. For example, we might do this by taking the numerator and denominator as an ordered pair, and mapping the ordered pair to a natural number. after doing this, we can implement this gameplan:

1. On the nth turn where we are choosing the mth digit of the running string, find the rational number that corresponds to n under our pairing function
2. Choose any digit which is different from the mth digit of the rational number attached to n

This will guarantee that, at infinity, the number will not be a rational number, since it will be different from every single rational number in at least one digits place.

This solution is actually pretty cool, since looking at the problem straight away might make you think that you’ll have to try to find some kind of algorithm that “thinks” by taking in the string of digits that has already been placed down as an input, but in solving the problem, we realize that it is possible to make an algorithm that doesn’t think at all and yet still works.

This ends up being really representative of a bigger trend in puzzlesolving and algorithmic design as a whole: When it’s too hard to make a smart algorithm, it might just be better to make a simple one.