Thanks so much to everyone for trying out my transfinite epistemic logic puzzle, which I have given the name Cheryl’s Rational Gifts, on account of her gifts to Albert and Bernard. I hope that everyone enjoyed the puzzle. See the list of solvers and honorable mentions at the bottom of this post. Congratulations!
As I determine it, the solution is that
Albert has the number $100\frac38$, and
Bernard has the number $100\frac7{16}$.
Let me explain my reasoning and address a few issues that came up in the comments.
First, let’s understand the nature of the space of possible numbers that Cheryl describes, those of the form the form $$n-\frac{1}{2^k}-\frac{1}{2^{k+r}},$$ where $n$ and $k$ are positive integers and $r$ is a non-negative integer. Although this may seem complicated at first, in fact this set consists simply of a large number of increasing convergent sequences, one after the other. Specifically, the smallest of the numbers is $0=1-\frac12-\frac12$, and then $\frac14$, $\frac38$, $\frac7{16}$, and so on, converging to $\frac12$, which itself arises as $\frac12=1-\frac14-\frac14$. So the numbers begin with the increasing convergent sequence $$0 \quad\frac14\quad \frac38\quad \frac7{16}\quad\cdots\quad\to\quad \frac12.$$Immediately after this comes another sequence of points of the form $1-\frac14-\frac1{2^{2+r}}$, which converge to $\frac34$, which itself arises as $1-\frac18-\frac18$. So we have $$\frac12\quad \frac58\quad \frac{11}{16}\quad\frac{23}{32}\quad\cdots\quad\to\quad \frac34.$$Following upon this, there is a sequence converging to $\frac78$, and then another converging to $\frac{15}{16}$, and so on. Between $0$ and $1$, therefore, what we have altogether is an increasing sequence of increasing sequences of rational numbers, where the start of the next sequence is precisely the limit of the previous sequence.
The same pattern recurs between $1$ and $2$, between $2$ and $3$, and indeed between any positive integer $n$ and its successor $n+1$, for the numbers the occur between $n$ and $n+1$ are simply a translation of the numbers between $0$ and $1$. Thus, for every positive integer $k$ we have $n-\frac1{2^k}$ as the limit of the numbers $n-\frac{1}{2^k}-\frac{1}{2^{k+r}}$, as $r$ increases. Between any two non-negative integers, therefore, we have an increasing sequence of converging increasing sequences. Altogether, we have infinitely many copies of the picture between $0$ and $1$, which was infinitely many increasing convergent sequences, one after the other.
For those readers who are familiar with the ordinals, what this means is that the set of numbers forms a closed set of order type exactly $\omega^3$. We may associate the number $n-\frac{1}{2^k}-\frac{1}{2^{k+r}}$ with the ordinal number $\omega^2\cdot (n-1)+\omega\cdot (k-1)+r$, and observe that this correspondence is a (continuous) order-isomorphism of our numbers with the ordinals below $\omega^3$. In this way, we could replace all talk of the specific rational numbers in this puzzle with their corresponding ordinals below $\omega^3$ and imagine that Cheryl has actually given her friends ordinals rather than rationals. But to explain the solution, allow me to stick with the rational numbers.
The fact that Albert initially does not know who has the larger number implies that Albert does not have $0$, the smallest number overall, since if he were to have had $0$, then he would have known that Bernard’s must have been larger. Since then Bernard does not know, it follows that his number is neither $0$ nor $\frac14$, which is the next number, since otherwise he would have known that Albert’s number must have been larger. Since Albert continues not to know, we rule out the numbers up to $\frac38$ for him. And then similarly ruling out the numbers up to $\frac7{16}$ for Bernard. In this way, each step of the back-and-forth continuing denials of knowing eliminates the lowest remaining numbers from possibility.
Consequently, when Cheryl interrupts the first time, we learn that Albert and Bernard cannot have numbers on the first increasing sequence (below $\frac12$), since otherwise they would at some point come to know in that back-and-forth procedure who has the larger number, and so it wouldn’t be true that they wouldn’t know no matter how long they continued the back-and-forth, as Cheryl stated. Thus, after her remark, both Albert and Bernard know that both numbers are at least $\frac12$, which is the first limit point of the set of possible numbers.
Since at this point Albert states that he still doesn’t know who has the larger number, it cannot be that he has $\frac12$ himself, since otherwise he would have known that he had the smaller number. And then next since Bernard still doesn’t know, it follows that Bernard cannot have either $\frac12$ or $\frac58$, the next number. Thus, if they were to continue the iterative not-knowing-yet pronouncements, they would systematically eliminate the numbers on the second increasing sequence, which converges to $\frac34$. Because of Cheryl’s second interruption remark, therefore, it follows that their numbers do not appear on that second sequence, for otherwise they would have known by continuing that pattern long enough. Thus, after her remark, they both know that both numbers are at least $\frac34$.
And since Albert and Bernard in succession state that they still do not know, they have begun to eliminate numbers from the third sequence.
Consider now Cheryl’s contentful exasperated remark. What she says in the first part is that no matter how many times the three of them repeat that pattern, they will still not know. The content of this remark is precisely that neither of the two numbers can be on next sequence (the third), nor the fourth, nor the fifth and so on; they cannot be on any of the first $\omega$ many sequences (that is, below $1$), because if one of the numbers occurred on the $k^{th}$ sequence below $1$, as $1-\frac1{2^k}-\frac1{2^{k+r}}$, for example, then after $k-1$ repetitions of the three-way-pattern, it would no longer be true for Cheryl to say that no matter how long Albert and Bernard continued their back-and-forth they wouldn’t know, since they would indeed know after $r$ steps of that at that point. Thus, the first part of Cheryl’s remark implies that the numbers must both be at least $1$.
But Cheryl also says that the same statement would be true if she said it again. Thus, the numbers must not lie on any of the first $\omega$ many sequences above $1$. Those sequences converge to the limit points $1\frac12$, $1\frac34$, $1\frac78$ and so on. Consequently, after that second statement, everyone would know that the numbers must both be at least $2$. Similarly, after making the statement a third time, everyone knows the numbers must be at least $3$, and after the fourth time, everyone knows the numbers must be at least $4$.
Cheryl says that she could make the statement a hundred times altogether in succession (counting the time she has already said it as amongst the one hundred), and it would be true every time. Since each time she makes the statement, it eliminates precisely the possibility that one of the numbers is on any of the next $\omega$ many sequences, what everyone would know after the one hundredth pronouncement is precisely that both numbers are at least $100$. Even though she didn’t actually make the statement one hundred times, Albert and Bernard are entitled to know exactly that information even so, because she had said that the statement would be true every time, if she were to have said it one hundred times.
Note that it would be perfectly compatible with Cheryl making that statement one hundred times, if one of the numbers had been $100$, since each additional assertion simply eliminates the possibility that one of the numbers occurs on the sequences strictly before the next integer limit point, without eliminating the integer limit point itself.
Next Cheryl makes an additional statement, which it seems to me that some of the commentators did not give sufficient attention. Namely, she says, “And furthermore, even after my having said it altogether one hundred times in succession, you would still not know who has the larger number!” This statement gives additional epistemic information beyond the content of saying that the $100^{th}$ statement would be true. After the $100^{th}$ statement, according to what we have said, both Albert and Bernard would know precisely that both numbers are at least $100$. But Cheryl is telling them that they still would not know, even after the $100^{th}$ statement. Thus, it must be that neither Albert nor Bernard has $100$, since having that number is the only way they could know at that point who has the larger number. (Note also that Cheryl did not say that they would know that the other does not know, but only that they each would not know after the $100^{th}$ assertion, an issue that appeared to trip up some commentators. So she is making a common-knowledge assertion about what their individual epistemic states would be in that case.) The first few numbers after $100$ are: $$100\qquad 100\frac14\qquad 100\frac38\qquad 100\frac7{16}\qquad 100\frac{15}{32}\qquad\cdots\to\quad
100\frac12$$ So putting everything together, what everyone knows after Cheryl’s exasperated remark is that both numbers are at least $100\frac14$.
Since Albert still doesn’t know, it means his number is at least $100\frac 38$. Since Bernard doesn’t know after this, it means that Bernard cannot have either $100\frac14$ or $100\frac38$, since otherwise he would know that Albert’s is larger. So Bernard has at least $100\frac7{16}$.
But now suddenly, finally, Albert knows who has the larger number! How can this be? So far, all we knew is that Albert’s number was at least $100\frac 38$ and Bernard’s is at least $100\frac7{16}$. If Albert had $100\frac 38$, then indeed he would know that Bernard’s number is larger; but note also that if Albert had $100\frac7{16}$, then he would also know that Bernard must have the larger number (since he knows the numbers are different). But if Albert’s number were larger than $100\frac7{16}$, then he couldn’t know whether Bernard’s number was larger or not. So after Albert’s assertion, what we all know is precisely that Albert has either $100\frac38$ or $100\frac7{16}$.
But now, Bernard claims to know both numbers! How could he know which number Albert has? The only way that he can distinguish those two possibilities that we mentioned is if Bernard himself has $100\frac7{16}$, since this is the smallest possibility remaining for Bernard and if Bernard’s number were larger than that then Albert could have consistently had either $100\frac38$ or $100\frac7{16}$. Thus, because Bernard knows the numbers, it must be that Bernard has $100\frac7{16}$, which would eliminate this possibility for Albert.
So Albert has $100\frac38$ and Bernard has $100\frac7{16}$, and that is the solution of the puzzle.
A number of commentators solved the puzzle, coming to the same conclusion that I did, and so let me give some recognition here. Congratulations!
- Neel Nanda
- evanjhub
- Aris Katsaris
- Joe Dobrow and Kellen Kirchberg, also on math.SE
- MatNat2 Jonas
- Warwick Logic Reading Group
- Gavi Dov
- Paul Crowley (after fixing the fencepost)
Let me also give honorable mentions to the following people, who came very close.
I’m sorry, but those gifts are not rational at all. Nice bottle of wine, a tie, $5 gift card, cash… those are rational gifts! Playing cruel and transfinite games on your friends? That’s not very rational.
🙂
Isn’t the discovery the gift?
Thanks for that interesting puzzle!
I got caught by the “And furthermore, even after my having said it altogether one hundred times in succession, you would still not know who has the larger number!” and so was off by one number. I’d argue that that’s a bit ambiguous – “neither of you would know who has the larger number” would be clearer.
Cheers anyway!
I’m glad you enjoyed it. But what is the ambiguity? That is, what is the other reading that you are finding there? Your clarification seems to mean the same thing as what I intended. After she says is one hundred times, they will still not know. She isn’t saying that they will also know that the other doesn’t know.
Pingback: Cheryl’s Rational Gifts: transfinite epistemic logic puzzle challenge! | Joel David Hamkins