I'll start with the simplest version of the riddle: There is a frog standing on the beginning of the natural number line (at 0). In the beginning of the game the frog chooses a number $k\in \mathbb{N}$, which is unknown to you. Once the game starts, at every round the frog jumps $k$ steps to the right, and then you need to make a guess as to what number it ended on, if you succeed, you have caught the frog and won. Your task is to find an algorithm that will ensure that you can catch the frog in a finite number of steps. One possible solution is to
At each round $n$ consider $k=n$, and therefore guess the frog is on $n^2$. You are guaranteed to win in exactly $k$ steps.
Once you realize the solution, it is pretty straight forward to generalize the riddle. For instance, we can specify that the initial position is not at 0, but at some unknown $r \in \mathbb{N}$. Then the solution is to
Well-order $\mathbb{N}^2$ and traverse this order, at each pair $(r, k)$ arrived to at turn $t$, guess $r + kt$
This works with any sort of generalization to a countable set, such as $\mathbb{Q}$, $\mathbb{Z}^n$ etc.
My question:
Can we generalize this riddle to $\mathbb{R}$? Specifically, assuming the axiom of choice which entails the existence of a well ordering of $\mathbb{R}$, can this be used for a similar solution to the ones shown? I realize the problem would probably be with the words "construct", and "algorithm", but is there maybe a way to edit the formulation of the riddle so that this won't be a problem?
There is no algorithm to solve this in finitely many steps. In other words, this has no generalization to all real numbers. This solution uses countably and uncountably infinite sets.
We know the set $\mathbb R$ is infinite. Let us show it is uncountable. In other words, let us show that we can never draw a 1-1 correspondence between the items in $\mathbb Z^+$ and $\mathbb R$. This is done through Cantor's diagonalization argument.
Suppose we have such a 1-1 correspondence, $f: \mathbb Z^+\rightarrow\mathbb R$. Let us visualize this correspondence:
(I have simply chosen some random real numbers to show the mapping). Let us show that, by any such mapping, we have left at least 1 real number unpaired.
Real numbers can have any digit in any decimal place. Construct a real number such that the $k^\text{th}$ digit after the decimal place is not equal to the $k^\text{th}$ digit of $f(k)$ for every positive integer $k$. Now, for every positive integer (as $k$ ranges over all positive integers), our newly constructed real number is not equal to any of the mapped real numbers (as it differs by at least one digit). Therefore, this newly constructed real number is left unpaired, and the bijection cannot exist.
In order to meet your requirements, one must create an algorithm that, in finitely many steps, considers every real number. At that step, it would guess the predicted location of the frog based on that guess.
By definition, there is a bijection between the set of positive integers and the real numbers guessed by such an algorithm. Each positive integer $k$ maps to the real number guessed on the $k^\text{th}$ guess. However, there is no bijection between the set of positive integers and the set of all real numbers, as the set of real numbers is larger. Therefore, one cannot construct an algorithm that can guarantee guessing the position of the frog in finitely many steps.