**An attempt to devise a transfinite version of the Cheryl birthday puzzle.**

I won't describe the original puzzle here -- just Google it if, by some miracle, you haven't seen it already. Let us define a logic puzzle of this sort to be of level N if it requires you to consider a chain of length N of the type "I know that you know that I know that you know ... etc." Then a level-omega puzzle would be one that requires you to consider chains of length N for arbitrarily large N. That's what I've tried to devise below. I do not guarantee that I have succeeded -- I may have made a silly mistake.

Cheryl presents Albert and Bernard with the following set of pairs of positive integers. For even n, let r=n^2, s=(n+1)^2 and let A(n) be the set that consists of the pairs (1,r), (r,r), (r,r+1), (r+1,r+1), (r+1,r+2), and so on up a staircase until you reach the point (s-1,s-1). For odd n, take instead the pairs (r,1), (r,r), (r+1,r), (r+1,r+1), (r+2,r+1), ... , (s-1,s-1). So, for example, A(1) consists of the points (1,1), (2,1), (2,2), (3,2), (3,3), while A(2) consists of the points (1,4), (4,4), (4,5), (5,5), ... , (8,8).

Cheryl then tells Albert the x-coordinate of a special point and tells Bernard the y-coordinate. Albert and Bernard then have the following conversation.

Albert: I don't know which point Cheryl has chosen.

Bernard: Even now you've told me that, I don't know which point she has chosen.

Albert: Even now

*you've*told me

*that*, I don't know which point she has chosen.

Bernard: Even now

*you've*told me

*that*, I don't know which point she has chosen.

and so on and so on. Eventually Cheryl gets bored and says, "Hey, can we talk about something else now? You're never going to work out the answer."

At that point Albert and Bernard both say, "Ah, now I know which point you've chosen." What was the point?

- Oh good! I was hoping someone would have a go at that.Apr 16, 2015
- I should remark that an omega+1 version would be one where after Cheryl's comment, it takes just one further comment by Albert or Bernard for the other to know the answer. I would guess that with a bit of effort, one could generalize the construction above to produce a version of complexity alpha for any given countable ordinal alpha. So for an omega^2 version, for example, Cheryl would have to keep on periodically saying, "Look, you're not going to find out the answer," and then at some point say, "Look, however many times I tell you you're not going to get the answer, it won't help you to get the answer," and then (and only then) will Albert and Bernard know the answer.Apr 16, 2015
- This is very nice! Here is my transfinite epistemic logic problem version: http://jdh.hamkins.org/now-i-know/, which can be made of level $\alpha$, for any ordinal $\alpha$.Apr 17, 2015
- And here is a further puzzle challenge http://jdh.hamkins.org/transfinite-epistemic-logic-puzzle-challenge/ in a similar spirit.Apr 18, 2015
- The point was (1, 1).

Apart from 1, the x and y coordinates in A(n) are all >=n^2 and <(n+1)^2

Suppose that the point isn't (1, 1). At least one of the two knows that they're in A(n) for a specific n.

Albert and Bernard know which column or row the point is in. Therefore, if the point Cheryl chose is ever the only possible point she could have chosen in a row or column, Albert or Bernard will know.

A(n) forms a staircase, and for most points, there are exactly 2 points in the row and column its part of, apart from (1, r) or (r, 1) where there are infinitely many in its row or column, and (s-1, s-1) where it's the only one in its row or column.

After Albert and Bernard say they don't know for the first time, we know the chosen point is not the only one in its row or column, so (s-1, s-1) is ruled out.

The point adjacent to (s-1, s-1) in the staircase is now the only one in its row or column, so after Albert and Bernard say they don't know again, we know it's not that one, and so on.

For all staircases other than A(1), this process eventually rules out every point in the staircase, but (1, 1) is left in A(1) since there are infinitely many points in both its row and column. As we know that every point other than (1, 1) is eventually ruled out, the point must be (1, 1)Apr 18, 2015 - I wonder if the problem could be generalized to N friends of Cheryl's, where she gives each of them an n-tuple?Apr 19, 2015
- The sum and product problem could be generalized to N people and N numbers using elementary symmetric polynomials. For N=3, one person would know the sum a+b+c, one would know the product a*b*c, and one would know a*b+a*c+b*c. Has anyone explored this variation?Apr 20, 2015
- "At that point Albert and Bernard both say, "Ah, now I know which point you've chosen." What was the point?"

The point was to show how deviously complicated a puzzle can be posed by a girl who does not care about the mental sanity of her two friends ;-)Apr 30, 2015

Add a comment...