41
$\begingroup$

I expect that nearly everyone here at stackexchange is by now familiar with Cheryl's birthday problem, which spawned many variant problems, including a transfinite version due to Timothy Gowers.

In response, I have made my own transfinite epistemic logic puzzle, Cheryl's rational gift, which appears below. Can you solve it?

Cheryl   Welcome, Albert and Bernard, to my birthday party, and I thank you for your gifts. To return the favor, as you entered my party, I privately made known to each of you a rational number of 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; please consider it my gift to each of you. Your numbers are different from each other, and you have received no other information about these numbers or anyone's knowledge about them beyond what I am now telling you. Let me ask, who of you has the larger number?

Albert    I don't know.

Bernard    Neither do I.

Albert    Indeed, I still do not know.

Bernard    And still neither do I.

Cheryl    Well, it is no use to continue that way! I can tell you that no matter how long you continue that back-and-forth, you shall not come to know who has the larger number.

Albert    What interesting new information! But alas, I still do not know whose number is larger.

Bernard    And still also I do not know.

Albert    I continue not to know.

Bernard    I regret that I also do not know.

Cheryl    Let me say once again that no matter how long you continue truthfully to tell each other in succession that you do not yet know, you will not know who has the larger number.

Albert    Well, thank you very much for saving us from that tiresome trouble! But unfortunately, I still do not know who has the larger number.

Bernard    And also I remain in ignorance. However shall we come to know?

Cheryl    Well, in fact, no matter how long we three continue from now in the pattern we have followed so far---namely, the pattern in which you two state back-and-forth that still you do not yet know whose number is larger and then I tell you yet again that no further amount of that back-and-forth will enable you to know---then still after as much repetition of that pattern as we can stand, you will not know whose number is larger! Furthermore, I could make that same statement a second time, even after now that I have said it to you once, and it would still be true. And a third and fourth as well! Indeed, I could make that same pronouncement a hundred times altogether in succession (counting my first time as amongst the one hundred), and it would be true every time. And furthermore, even after my having said it altogether one hundred times in succession, you would still not know who has the larger number!

Albert    Such powerful new information! But I am very sorry to say that still I do not know whose number is larger.

Bernard    And also I do not know.

Albert    But wait! It suddenly comes upon me after Bernard's last remark, that finally I know who has the larger number!

Bernard    Really? In that case, then I also know, and what is more, I know both of our numbers!

Albert    Well, now I also know them!

Question. What numbers did Cheryl give to Albert and Bernard?

There are many remarks and solution proposals posted already as comments on my blog, but the solutions proposed there do not all agree with one another.

I shall post a solution there in a few days time, but I thought people here at Math.SE might enjoy the puzzle. I apologize if some find this question to be an inappropriate use of this site.

You may also want to see my earlier transfinite epistemic logic puzzles, with solutions there.

$\endgroup$
8
  • $\begingroup$ I gather from the tag description that the (puzzle) tag is not used for questions like this? $\endgroup$
    – JDH
    Apr 19, 2015 at 1:29
  • $\begingroup$ So... What ordinal would you give to a problem like this? $\omega^2100$? And does the set of numbers of the form $n-\dfrac1{2^k}-\dfrac1{2^{k+r}}$ have order-type $\omega^3$? $\endgroup$
    – Akiva Weinberger
    Apr 19, 2015 at 14:01
  • $\begingroup$ @columbus8myhw Yes, Cheryl's set of numbers has order type $\omega^3$ altogether, since between each pair of natural numbers, there are $\omega$ many increasing $\omega$-sequences, and so we have $\omega$ many copies of $\omega^2$. $\endgroup$
    – JDH
    Apr 19, 2015 at 14:58
  • 1
    $\begingroup$ @JDH: Nice problem! $\endgroup$
    – Hanno
    Apr 19, 2015 at 15:15
  • $\begingroup$ In the last sentence: "And furthermore, even after my having said it altogether one hundred times in succession, you would still not know who has the larger number!", does she claim that they both don't know or that they don't both know? $\endgroup$
    – Florian F
    May 1, 2015 at 11:00

3 Answers 3

Reset to default
16
$\begingroup$

We can map $n - 2^{-k} - 2^{-(k+r)}$ onto the ordinal $\omega^2(n-1) + \omega(k-1) + r$; this preserves order. So Cheryl effectively says "I have given you both distinct ordinals $a$ and $b$, both less than $\omega^3$. Which is bigger?"

Albert says "$a \geq 1$", Bernard says "$b \geq 2$", Albert says "$a \geq 3$", Bernard says "$b \geq 4$".

Cheryl says "Actually $a$ and $b$ are both $\geq \omega$".

Albert says "$a \geq \omega + 1$", Bernard says "$b \geq \omega + 2$", Albert says "$a \geq \omega + 3$", Bernard says "$b \geq \omega + 4$".

Eventually Cheryl says "Actually both are $\geq \omega^2 100 + 1$".

Albert says "$a \geq \omega^2 100 + 2$".

Bernard says "$b \geq \omega^2 100 + 3$".

Albert says "Aha! In that case I know the answer, which tells you that $a < \omega^2 100 + 4$".

From that, Bernard can work out Albert's number. How does he know whether Albert's number is $\omega^2 100 + 2$ or $\omega^2 100 + 3$? It can only be that $\omega^2 100 + 3$ is Bernards's number, so he knows Albert's must be $\omega^2 100 + 2$.

Translating back in to the language of the original question, this means that Albert's number is $101 - 2^{-1}- 2^{-3} = 100.375$ and Bernard's is $101 - 2^{-1}- 2^{-4} = 100.4375$.

$\endgroup$
4
  • 3
    $\begingroup$ Nitpick: According to ordinal multiplication, $100\omega^2$ is not the same as $\omega^2100$. $100\omega^2=\omega^2$, while $\omega^2100>\omega^2$. (Because $100\omega^2=100+100+\dotsb+100+100+\dotsb+100+100+\dotsb+\dotsb$, with $100$ written $\omega^2$ times. This is equal to $\omega+\omega+\omega+\dotsb=\omega^2$. On the other hand, $\omega^2100=\omega^2+\omega^2+\dotsb+\omega^2$, which is what you probably meant.) $\endgroup$
    – Akiva Weinberger
    Apr 19, 2015 at 15:21
  • $\begingroup$ Oops, thank you, fixed! I think Gödel, Escher, Bach gets this wrong, which is where I originally learned about ordinals from. $\endgroup$
    – Paul Crowley
    Apr 19, 2015 at 15:28
  • 3
    $\begingroup$ Almost. You need to take into account Cheryl's very last sentence ("And furthermore, even after having said it 100 times… you still would not know!"), which translates to "Actually $a$, $b\ge\omega^2\cdot100 + 1$". So $a = \omega^2\cdot100+2 \mapsto 100.375$ and $b = \omega^2\cdot100 + 3 \mapsto 100.4375$. $\endgroup$
    – Chad Groft
    Apr 19, 2015 at 16:12
  • $\begingroup$ Argh, I knew I'd make a fencepost error! Thanks, fixed! $\endgroup$
    – Paul Crowley
    Apr 19, 2015 at 16:19
11
$\begingroup$

Every time Albert and Bernard go back and forth they are eliminating a new ‘r’ , and every time she tells them that no matter how many times they go back and forth they won’t get it, they are eliminating a new ‘k.’

When Cheryl makes her big rant, she if effectively telling them that for all r and k when n = 1, they won’t find it, and furthermore that the first 100 times she makes that statement they won’t find it.

She also says that after saying it 100 times, neither will know which number is larger. This means that neither Albert nor Bernard has the number 100. (something a couple other solutions missed I think.) Albert says he does not know, ruling out him having 100 + 1/4, and then Bernard says he still does not know, ruling out Bernard having 100 + 3/8 and 100 + 1/4.

When Albert says that he suddenly knows, he can either have 100 + 3/8 or 100 + 7/16. The only way for Bernard to know both of their numbers is if he has 100 + 7/16, which gives us the answer:

Albert: 100 + 3/8 Bernard: 100 + 7/16

$\endgroup$
2
$\begingroup$

I have posted an extended solution on my blog:

Solution to my transfinite epistemic logic puzzle.

My answer agrees with that of Joe and Kellen and Paul on the other answers here, namely, that Albert has $100\frac38$ and Bernard has $100\frac7{16}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .