Can you solve my challenge puzzle?
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?
If you can determine the answer, make comments below or post a link to your solution. I have posted my own solution on another post.
See my earlier transfinite epistemic logic puzzles, with solutions. These were inspired by Timothy Gowers’s example.
I have edited the dialogue slightly from first posting.
I further sharpened some of the dialogue in response to some remarks of Andrej Bauer and to a request of Huy Nguyen concerning Cheryl’s critical final clue. These changes did not change my intended meaning. But just in case there might be disagreement, let us use the dialogue as it appears currently.
I have also placed the puzzle on math.stackexchange at http://math.stackexchange.com/q/1241197/413.
I’m not sure where to post my solution because there is no reply box at the bottom of this page, so I’m just replying to this post.
My answer is slightly different from some others below. 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
Yes.
I have a doubt here, reminiscent of the Surprise Test paradox. I’d appreciate it if somebody could clear the doubt.
“even after my having said it altogether one hundred times in succession, you would still not know who has the larger number”
When Cheryl states the above, it is instantly clear to Albert and Bernard that nobody has a 100 (since then that person would know). Now say Albert (or Bernard) had 100 + 1/4, he would know for sure that the other person has the larger number, so it’s not possible that anyone has 100 + 1/4.
I do not see how this elimination of 100 + 1/4 could be wrong except that it must be wrong (or Cheryl’s statement must be paradoxical) because of what it entails:
If we can eliminate 100 + 1/4, this can be extended to 100 + 3/8 etc arbitrarily close to 100 + 1/2. (maybe more, I have not formally tried)
However, if their numbers were 100 + 3/8 and 100 + 7/16, it is clear that neither Albert nor Bernard would know whose number is larger.
In conclusion: “Aaaaaaaargh, help!”
Although she is making that statement with the status of common knowledge, the knowledge statement that she asserts is not about common knowledge. That is, she says only that after saying that statement, they will not know, not that they will know that they both do not know. I think this is a very subtle point, and I’m glad that you mentioned it.
This is an astute comment.
How about: “…even after my having said it altogether one hundred times in succession, still neither of you would know who has the larger number (although I do not guarantee that either need know of the other’s ignorance).”
A wonderful puzzle!
What if they agreed on some encoding of the tripples?
Won’t give a good ordering though… 🙂
First we must show the relative importance of the different integers n, k, and r. We can show mathematically that one party having a greater n value will render their overall rational number (let’s call them A and B) larger regardless of k and r and likewise for k being more important than r. Here is a proof for that fact:
First note that A increases consistently with an increase in any of the three integers. We can also note that no number A can be generated by more than one distinct triple (which will be more evident after the rest of this segment of the proof). If Albert’s number A has an n-value of (let’s call then nA, nB, kA, kB, rA, rB,) nA=2 and Bernard has nB=1, then Albert must have the larger number. Why? The maximum Albert can lose from the remaining two terms is attained when kA=1 and rA=0 giving Albert a value of A=1. That is the lowest value Albert can achieve when nA=1. If we minimize the amount Bernard loses from the next two terms, we set both kB and rB to approach infinity and Bernard will have a value of B that approaches 1 but never reaches it. So B=.99999… but not 1. In mathematical terms we call 1 an “upper bound” for the value of B (when nB=1) but 1 is NOT a maximum. Thus for any two consecutive (and even more obviously for non consecutive values of nB and nA) the greater value for n will always yield a greater overall number A or B. Thus to rank the two values A, and B, we need only look past their n values if they are the same.
We will now prove the same argument for k (operating under the assumption that nA=nB). Consider them having consecutive numbers for k (again, if they differ by more, the claim will only be stronger). Let those numbers be kA= q and kB = q-1 (for any q greater than 1).
Then A = n-1/(2^q)- 1/(2^(q+r)) and B = n-1/(2^q+1)- 1/(2^(q+r+1)).
The smallest we can make A is when rA=0 and A = n-2/(2^q) = n-1/(2^(q-1))
The largest B is when rB approaches infinity and B approaches n-1/(2^(q-1)) but never reaches it. So similarly, we need only look at rA and rB if nA=nB and kA=kB.
Thus we can rank their numbers in terms of three coordinates (n,k,r) where A(nA,kA,rA) is greater than B(nB,kB,rB) if and only if nA>nB OR (nA=nB AND kA>kB) OR (nA=nB AND kA=kB AND rA>rB).
The smallest triple is (1,1,0) yielding 0. Next is (1,1,1) yielding ¼. They increase with increasing r and approach (1,1,infinity) which yields a number that approaches ½.
The next triple is (1,2,0) which ACTUALLY yields ½. Etc. Then we increase k until we reach (1,inifinty,r) which approaches 1 followed by (2,1,0) which ACTUALLY yields 1.
We will now go through the statements having the above axiom and determine who has what numbers.
Albert’s first statement “I don’t know” means he does not have (1,1,0) because having (1,1,0) is the only way for him to know who has the larger number without any more information. The only way for him to know who has the larger is if he has the absolute smallest number possible (and he would have it uniquely).
Bernard’s statement “Neither do I” means he does not have (1,1,0) or else he would know Albert had a larger number. It also means that he does not have (1,1,1) either since, knowing that Albert does not have (1,1,0), he would have known that Albert’s number was larger if he has (1,1,1).
Then Albert tells us he doesn’t have (1,1,1) or (1,1,2).
ETC.
Cheryl then chimes in and tell them that this pattern will not help them solve the puzzle. This tells us something very important. This tells us that neither have numbers of the form: (1,1,r). If they did, this back and forth would eventually lead one of them to realize he has the smaller number.
Albert’s next IDK tell us that he does not have (1,2,0).
Bernard’s tell us that he doesn’t either, and additionally, he doesn’t have (1,2,1) since, knowing that Albert doesn’t have (1,2,0), having (1,2,1) would make his number the smallest.
Albert’s next comment tells us that he doesn’t have (1,2,1) or (1,2,2) either.
ETC.
Cheryl then chimes in again and like before, tells them that this pattern will not yield a solution. Therefore, neither can have anything of the form (1,2,r).
Cheryl then offers even more advice. She says that above pattern will not yield a solution. This means that they cannot both have numbers of the form (1,k,r). Because if they had, the above pattern (which, if you include Cheryl’s own comment is essentially two nested loops) would ultimately tell one of them that he has the smaller number. NOTE: it is essential that the “above pattern” include Cheryl’s remarks as well, because those remarks give lots of information.
Then Cheryl claims that the above statement could be made 100 times and they would still not get it! Each time she makes the claim, she is precluding an entire double loop of possibilities. The first time she made the comment, she eliminated the possibility of either of them having (1,k,r). The second time would eliminate either of them having (2,k,r).
After saying it 100 times, she eliminates either of them having (100,k,r). By saying “Furthermore, you would not know…” she gives away that neither of them has (100,1,0) because if either did, they would know.
Albert’s next IDK tells us that he does not have (100,1,1).
Bernard’s next tells us that he also does not have (100,1,1) and he doesn’t have (101, 1,2) either.
The fact that Albert now knows tells us that either he has (101,1,2) or he has (101,1,3) – either way he knows his is the smallest.
Bernard knowing both the numbers tells us that he must have (101,1,3): he knows Albert must have either (101,1,2) or (101,1,3), and his own is obviously larger. The only way to know which of the two Albert has is by having (101,1,3) himself.
Therefore A=A(101,1,2)=100+3/8
And B=B(101,1,3)=100+7/16
This is a very surreal birthday party. So I’m going to say $\omega_1+2$, or if Cheryl is a constructivist, $\omega_1^{CK}+2$. 🙂
Asaf, I find your answer to be in the right spirit, but the numbers are supposed be rational, of the special form that Cheryl had described!
Cheryl says “if I did X a hundred times, then you would know Y” but she did not in fact do X a hundred times. Therefore, Albert and Bernard cannot continue reasoning as if X happened a 100 times. How can this be fixed so that no doubt is left in the formulation of the puzzle?
P.S. I cannot log into the commenting system with Wordress or Google+.
Could you clarify the objection? For a truthful person to say X, or to say “If I were to say X, it would be true” seem to have the same epistemic content for this purpose. Why can’t they reason as if she actually had said that one hundred time in succession? That was certainly my intention; if you have a suggestion for clarifying the dialogue, please let me know.
(And sorry about logging in–I don’t know how to enable that, but I’ll look into it. I had to approve your first comment.)
Mmm, I’d bet the numbers are:
smaller: 2 – 1/2 – 1/8
larger: 2-1/2 – 1/16
Perhaps some knowledgeable person, for whom it is easy, can help me to make an attractive picture showing the numbers that Cheryl had mentioned? I imagine them drawn on a number line, with some of them labeled and with some gradations of color or size, so as to suggest the general pattern. What is the best way to do that? I think I could learn how to do for-loops in tikz and draw it that way using tex. Any suggestions?
Andrej Bauer has kindly produced some images, which now appear in the post.
Intriguing. I understand that Albert has got the smaller of the two numbers (obtained with n = 101, k = 1, and r = 3, or something like that).
Then, Bernard, who already knows his own number, can deduce Albert’s by following the same reasoning as me. However, I don’t know how Albert (or we) can use this information (his own number, the fact that Bernard’s number is greater than his, and the fact that finally Bernard knows both numbers) to obtain Bernard’s number.
Since I can’t solve the whole puzzle, chances are that I made a mistake in the first half of the puzzle as well 😛
[Little Spoilers] You are an inch from the answer, think more!
So close! You got n & k correct, but let me walk you through the last bit. I’ll start from after Cheryl goes through the “100” bit, knowing that n > 100.
At this point, the exchange goes as follows:
Albert: Dunno
Bernard: Dunno
Albert: I know who’s is bigger
Bernard: I know the values
Albert: Me too
From Albert’s dunno, we rule out A = f(101,1,0).
From Bernard’s dunno, we rule out B = f(101,1,0) and B = f(101,1,1).
Then Albert knows that A must be smaller than B, meaning that either A = f(101,1,1). or A = f(101,1,2).
This is where the magic comes in. If A = f(101,1,2), then B would be at least f(101,1,3). This would preclude Bernard from determining whether A was f(101,1,1) or f(101,1,2).
Because Bernard DOES figure out A, we know B = f(101,1,2), forcing A to be f(101,1,1).
Therefore Albert has 100 1/4 and Bernard has 100 3/8.
Almost. But Cheryl 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 rules out either having f(101,1,0), since if one had it, he would know. So we start the next round at f(101,1,1):
From Albert’s dunno, we rule out A = f(101,1,1).
From Bernard’s dunno, we rule out B = f(101,1,1) and B = f(101,1,2).
Then Albert knows that A is smaller than B, so that A = f(101,1,2) or A = f(101,1,3).
The only way Bernard knows which is if B = f(101, 1, 3) and A = f(101, 1, 2).
Ah, for wilmer’s answer I deduce that the number 100 might actually be significant, while at a first reading I assumed it was standing, colloquially, for an arbitrary large numer.
Oh, I believe that Cheryl had meant exactly one hundred when she said that.
It seems the first ‘run’ of “I don’t know’s”, together with Cheryl’s announcement, rules out all numbers in the range
[ 1 – 2 * 1/2, 1 – 1/2 )
(the candidates in this interval are 0, 1/4, 3/8, 7/16, etc..)
and similarly, the nth run rules out the range
[ 1 – 2 * 1/(2^n), 1 – 1/(2^n) )
(candidates: 1/2, 5/8, 11/16, 23/32, etc…)
From the structure of the set of candidates you can easily see that it is a well-ordered set. After 100 runs and 2 steps into the 101st run, Albert knows the answer after Bernhard says he doesn’t know.
This would seem to imply that Albert has the number
1 – 1/(2^102) – 1/(2^103)
(that is, the second smallest number in the 101st run, which starts with 1 – 2 * 1/(2^102) )
but I am still clueless about Bernhard’s number. (I don’t really see how Bernhard’s statement “Really? In that case, then I also know, and what is more, I know both of our numbers!” adds any new information for Albert, or for me or anyone doing the puzzle.) Beyond the fact that it must be some larger number than Albert’s, that is…
Addendum: with his last
“Bernard And also I do not know.”
Bernard betrays that he does not have 1-1/(2^102)-1/(2^103) or anything smaller. So in fact, when Albert replies
“Albert But wait! It suddenly comes upon me after Bernard’s last remark, that finally I know who has the larger number!”
this means he either has 1-1/(2^102)-1/(2^103) or 1-1/(2^102)-1/(2^104).
Because Bernard now knows Albert’s number, this must mean he has 1-1/(2^102)-1/(2^104), and thus Albert has 1-1/(2^102)-1/(2^103).
After the latest reformulation of the problem, let’s see if my guess has to be formulated (I think I made some sloppy mistakes with some of the details):
– The 1st completed run (including Cheryl’s statement “you will not know how matter how long you continue) rules out all numbers strictly below
1 – 1/2
and similarly, the nth completed run rules out all numbers strictly below
1 – 1/2^n
– Nobody knows within the first 100 runs. This means the smallest candidates now left are
(
1 – 1/(2^101) – 1/(2^101) (= 1 – 1/(2^100)),
1 – 1/(2^101) – 1/(2^102)
1 – 1/(2^101) – 1/(2^103)
1 – 1/(2^101) – 1/(2^104)
)
Then Albert says he doesn’t know one more time, which means his number is larger than:
1 – 1/(2^101) – 1/(2^101)
Then Bernard says he doesn’t know one more time, which means his number is larger than:
1 – 1/(2^101) – 1/(2^102)
Then Albert says he now knows. This means his number is either
1 – 1/(2^101) – 1/(2^102) or 1 – 1/(2^101) – 1/(2^103)
Bernard now says he also knows, and he knows Albert’s number. This is only possible if B’s number is one of A’s two candidates. It thus must be the case that
B has 1 – 1/(2^101) – 1/(2^103)
A has 1 – 1/(2^101) – 1/(2^102)
This is my final guess. (And it’s one step away from my previous guess.)
Ah, just saw I misread Cheryl’s last statement, which does not rule out just the first 100 runs, but rather the first omega * 100 runs. (which rule out all numbers below 100)
Now we get, using the same logic
B has 101 – 1/2 – 1/8
A has 101 – 1/2 – 1/4
as I think some others already concluded…
Albert’s number: 101 – 1/2 – 1/4
Bernard’s number: 101 – 1/2 – 1/8
Here’s my attempt in ordinary language.
Let’s call Albert’s number a, and Bernard’s number b, and let them be given by n_a, k_a, r_a and n_b, k_b, r_a in the obvious way. We can see that if n_a > n_b, this guarantees that a > b, while if n_a = n_b and k_a > k_b, we must have that a > b, regardless of the values of r_a and r_b. Then we see that the answer can only come to be known through the initial back and forth if n_a, n_b, k_a and k_b are all at their minimum values. That the back and forth can go on forever means that k_a and k_b must be at least one step greater. Each time the meta back-and-forth can go on, the matter is not decidable by changing the value of k. Thus, n_a and n_b must be at least one step greater for each meta back-and-forth.
Cheryl states that the meta back and forth can occur 100 times altogether. The fact that the matter concludes a finite number of steps after this means that k_a, k_b must be 1 while n_a, n_b are 101, as otherwise the back and forth could go on again. Now Albert still does not know at this point, so r_a >= 1 and furthermore Bernard knows this. But after this Bernard still doesn’t know, so r_b >= 2, as each possibility r_b = 0, r_b = 1 would leave him in no doubt he had the lesser number. At this point, Albert finally knows, hence r_a = 1 or r_a = 2. But Bernard also can work out Albert’s number from this, so Bernard must have had one of those numbers. But we know already that Bernard can’t have had r_b = 1, so it must be that r_b = 2. It follows from this that r_a = 1. Albert follows this reasoning, and thereby works out Bernard’s number.
So unless I’ve made a mistake, we have n_a = n_b = 101, k_a = k_b = 1, while r_a = 1, r_b = 2. That is, a = 100.25, while b = 100.375
Albert = 2 – 1/2 – 1/4
Bernard = 2 – 1/2 – 1/8
Cheryl’s first comment rules out n=1, k=1. Her second comment rules out n=1, k=2. Her third comment rules out n=1, period. After that, we are up to n=2, and the remainder follows by Singaporean logic.
Spoiler: solution below:
Alfred has the smaller number with n=101 k=1 r=1
And bertnard has the larger possible number n=101 k=1 r=2
Outline of solution.
Every step of initial back and forth excludes low numbers of k. The meta back and forth excludes low numbers of n. 100 times means n is 101. After that the final exchange we know alf is either r=1 or r=2 but Bert knows that only if he is r=2
My solution is that Albert has n=101, k=1, r=2, and Bernard has the same but r=3.
Let f(n, k, r)=n-2^-k-2^(-k-r)
1>=1/2^k+1/2^(k+r)>0, so n-1<=f(n, k, r)n’, f(n, k, r)>f(n’, k’, r’) for any values k, r, k’, r’
1/2^(k-1)>=1/2^k+1/2^(k+r)>1/2^k, so if k>k’, f(n, k, r)>f(n, k’, r’) for any r, r’
-1/2^(k+r) is increasing in r, so if r>r’, f(n, k, r)>f(n, k, r’)
So, given any distinct (n, k, r) and (n’, k’, r’), to find which gives a larger number, find the larger n. If they’re equal, find the larger k, and if those are also equal then find the larger r
There is no upper bound to f, so during the questioning, A and B can only know who has the largest number if their number is less than or equal to the minimum possible number the other can have.
At the beginning, the minimum possible is f(1, 1, 0). A not knowing means they don’t have f(1, 1, 0), so B not knowing means they don’t have f(1, 1, 1) or f(1, 1, 0) and so on. If either has f(1, 1, anything), then this means they’ll eventually find out, so Cheryl’s intercession means the minimum either can have is f(1, 2, 0). The next intercession increases the minimum value of the second number by 1 again, and so on.
Therefore, if n is 1 for either, once Cheryl intercedes enough times, they’ll know who has the larger number. Cheryl says this doesn’t happen, so the min value of n increases by 1 to 2.
This happens every time Cheryl says it doesn’t matter how many times she intercedes. I’m unsure exactly how to parse the paragraph where she says it lots of times, whether it means she says it doesn’t matter how many times she intercedes twice and then another hundred times, or just a hundred in total. Assuming the latter, the minimum value of n is 101.
This means the minimum is now f(101, 1, 0). If either has this, they’d know that the other is larger, so as Cheryl says neither knows, they can’t have it, and the minimum is f(101, 1, 1).
If A had f(101, 1, 1), he’d know that B is larger, and A doesn’t, so A’s minimum is f(101, 1, 2).
If B had f(101, 1, 1) or f(101, 1, 2), they’d know A is larger, so B’s minimum is now f(101, 1, 3).
A now knows, so A has f(101, 1, 2) or f(101, 1, 3).
B then says that they know A’s number. The only way B can distinguish between f(101, 1, 2) and f(101, 1, 3) is if B has f(101, 1, 3) as their numbers are different, so this must be the solution, and A has f(101, 1, 2).
PART I
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−1/2^k−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.
A would know if he had the smallest #, q = f(n, k, r) = f(1, 1, 0) = 0, since B’s # must be different. –> A does not have 0. Further, note that since 1/2^(k+r) < 1/2^k ∞ and they will never get to the k column. –> The bigger # is not decided by the r column, and players now contend over k.
Albert What interesting new information! But alas, I still do not know whose number is larger.
The new information is that players are not tied on (n, k) = (1, 1). A does not have (1, 1, r).
Bernard And still also I do not know.
B does not have (1, 2, r).
Albert I continue not to know.
A does not have (1, 3, r).
Bernard I regret that I also do not know.
B does not have (1, 4, r).
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.
Same logic as before, neither k nor r will decide the winner. N is where it really matters, and they are not tied at n = 1.
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.
A does not have (1, k, r).
Bernard And also I remain in ignorance. However shall we come to know?
B does not have (2, k, r).
…
(PART II pending) Can you please phrase Cheryl’s last clue more clearly (mathematically precise)? Thanks!
First commentary should say, “Further, note that since 1/2^(k+r) < 1/2^k < n." Some formatting was lost pasting.
Cheryl Well, in fact, no matter how long we three continue from now in the pattern of you two going back-and-forth stating that still you do not yet know whose number is larger and me telling you yet again that no further amount of that back-and-forth will enable you to know, then still after as much of that as we can stand, you will not know whose number is larger! Furthermore, I could make that same statement again, even after now that I have said it to you once, and it would still be true. Indeed, I could make that same pronouncement a hundred times in succession, 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!
This phrasing was difficult to interpret, but I understand it to mean that we fast forward to:
B does not have (100, k, r).
Albert Such powerful new information! But I am very sorry to say that still I do not know whose number is larger.
The new information is that players must have at least (101, 1, 1). Since A still doesn’t know, he doesn’t have this new minimum.
Bernard And also I do not know.
B does not have (101, 1, 2).
Albert But wait! It suddenly comes upon me after Bernard’s last remark, that finally I know who has the larger number!
There are two possibilities here. A could have (101, 1, 2) or (101, 1, 3), either of which would guarantee his # to be smaller.
Bernard Really? In that case, then I also know, and what is more, I know both of our numbers!
How can B know which of the two A has? If only B has one of those #s himself! Since B does not have (101, 1, 2), he must have (101, 1, 3)! This is the only (unique) way B could know A’s #!
Albert Well, now I also know them!
q_A = f(101, 1, 2) = 101 – 1/2 – 1/4 = 100.25
q_B = f(101, 1, 3) = 101 – 1/2 – 1/8 = 100.375
Correction: “The new information is that players must have at least (101, 1, 0).” I remembered n, k are positive, but r is non-negative (starts at 0).
This updates to:
q_A = f(101, 1, 1) = 101 – 1/2 – 1/2 = 100
q_B = f(101, 1, 2) = 101 – 1/2 – 1/4 = 100.25
Nope. When the regression with n=100 ended, it ended with the number approaching 100, as k and r go to infinity. So, the number 100 was already out of the picture. Hence, we need to start with n=101, k=1, and r=1.
Right, with OP’s recent clarification, I understand:
“And furthermore, even after my having said it altogether one hundred times in succession, you would still not know who has the larger number!”
to mean the new minimum must be (101, 1, 0), but neither would know because neither have this #. So…
A: I don’t know. –> A does not have (101, 1, 1).
This issue was present in the original wording as well, since Cheryl had said something like: I could say that same statement truly one hundred times altogether, and still you would not know. This implied that they still would not know even after her having said it. But the current wording makes this a little more clear, I think.
“The new information is that players must have at least (101, 1, 1). Since A still doesn’t know, he doesn’t have this new minimum.
Bernard And also I do not know.
B does not have (101, 1, 2).”
I don’t get it. A doesn’t have (101,1,1). When B says he does not know, he too is saying that he does not have (101,1,1). How can just A’s statement prove that B does not have the minimum? When A hints that he does not have (101,1,1), if B had (101,1,1), B would say “Now I know whose number is larger”. He also has to provide a negative hint if he does not have (101,1,1) to move on to the next minimum.
In that case,
when A suddenly says that he knows, A has the minimum of (101,1,2). He cannot say the same if he had (101,1,3). When B comments that he knows both the numbers, that is true. He knows A has (101,1,2), and his number.
Now the problem is, how does A know what B’s number is? It could be anything greater than (101,1,2).. I am stuck there.
Good point. Hmm…
Oh! If A does not have (101, 1, 1) and B says “I don’t know,” this means B does not have (101, 1, 1) OR (101, 1, 2)!
If B had (101, 1, 2), he would’ve known as well! This solves the rest of it, I think!
But B says he does not know. Therefore, B does not have both (101,1,1) and (101,1,2). Then A says he knows => A has (101,1,2). Then B knows that A has (101,1,2), and also B knows his own number, so he says he knows both. But how does A figure out B’s number?
I think Aris Katsaris got it right 🙂
Yeah, that was a good explanation at the end. Repeating the same logic, A could have (101, 1, 2) OR (101, 1, 3) when he figures his is smaller.
I think we’re all good now! Cool puzzle–thanks for sharing, OP!
Here are some pictures: http://andrej.com/tmp/joel/
Fantastic! Thanks very much. I’ll put this into the post later this evening.
Of course I missed the whole 100 business since I read the puzzle while trying to convince my daughter to go to sleep. Yes, n=101, I think. Although the wording is confusing, even to a native speaker. It still is not clear to me (a native speaker) whether “even after my having said it altogether one hundred times in succession” includes the first pronouncement or not (i.e. whether the first pronouncement counts as accumulated knowledge or only a hypothetical possibility).
By saying “altogether” I had meant that the first time would be included in the one hundred. I think I’ll clarify that wording.
By my math:
Albert = 101 – 1/2 – 1/8
Bernard = 101 – 1/2 – 1/16
“By saying ‘altogether’ I had meant that the first time would be included in the one hundred. I think I’ll clarify that wording.”
Ah. In that case, it should be:
Albert = 100 – 1/2 – 1/8
Bernard = 100 – 1/2 – 1/16
Ah, no wait, n starts at 1, thus it should still be 101. My original answer was correct.
I’m not sure if anyone else volunteered yet but if not, I’d be more than happy to provide an illustration of the solution. I think I can handle it with something ranging from PowerPoint to Processing.
It is very kind of you to offer. If your comment was in reply to my request above for an image illustrating the collection of Cheryl’s numbers, though, then I’ve now already got some images from Andrej Bauer, which I shall upload soon.
But if you meant that you would write up a careful account of your solution of the puzzle, then please go ahead! You can provide a link to it here.
Meanwhile, I have my own solution prepared, which I intend to post in a few days time. I would note that not everyone currently agrees on the answer.
I meant an illustration and I missed Andrej comment – I’ll try to be faster next time! 🙂
Lovely, lovely puzzle. With sufficiently more parameters it can be adapted to any countable ordinal, but to go beyond that Cheryl would need to assume that her guests are actually familiar with ordinal numbers and not merely rational ones, right?
Well, every countable ordinal embeds into the rational numbers, and so that may not be an obstacle. But what I do find to be an obstacle is the artifice of Cheryl carrying Albert and Bernard through the limits by means of those kind of remarks. For sufficiently large ordinals, I would find this to be difficult to do unambiguously. I had earlier replied to Miha saying that in the case of larger ordinals, I would find it natural simply for Albert and Bernard to undertake an actually infinite conversation, without need for Cheryl to interrupt at all.
Yes of course, this makes sense.
As a side note (I hope it’s ok), I’m wondering if you’re familiar with the simple construction of a set of rational (dyadic) numbers of order type at least epsilon_0, explained here (warning: some claims are wrong):
http://www.mathpuzzle.com/fusible.pdf
and expanded upon more carefully here:
http://arxiv.org/pdf/1202.5614v1.pdf
Alon, your links on fusible numbers are great!
The numbers are:
A = 101 + 1/4
B = 101 + 3/8
Or, in the form given in your scenario:
Albert’s number is 102 – 1/2 – 1/4.
Bernard’s number is 102 – 1/2 – 1/8.
I have given a natural language explanation for my solution. Upon further investigation, there appears to be some ambiguity in Cheryl’s very last sentence, so I have provided possible solutions to each meaning that I could ascribe to it.
https://drive.google.com/file/d/0B1LG4ZMS2RsKcnBrRF9wVmVmdUU/view?usp=sharing
When A suddenly says that he knows, A has the minimum of (101,1,2). He cannot say the same if he had (101,1,3). When B comments that he knows both the numbers, that is true. He knows A has (101,1,2), and he knows his number.
Now the problem is, how does A know what B’s number is? It could be anything greater than (101,1,2).. I am stuck there.
Not reading any of the comments before I give my own response: Let’s name x=n – 1/2^k -1/2^(k+r)
The nature of the solution space is such that for any n1 > n2, it will be x1 > x2. And similarly when n1=n2, for any k1>k2 it will be x1 > x2, and when it’s n1=n2 and k1=k2 and
So the smallest possible number x (0) is when n = 1, k = 1, r = 0
and the immediately smallest is n=1, k=1, r=1 and the next is n=1, k=1, r=2
Let’s identify it just like this: (1, 1, 0), (1, 1, 1), (1, 1, 2) and so forth from now on.
Since the numbers given to Albert and Bernard are different, if one of them had this number, they would know whose was the largest one.
For the first exchange “Albert I don’t know.”
communicates to Bernard that Albert doesn’t have (1, 1, 0).
“Bernard Neither do I.”
communicates to Albert than Bernard doesn’t have (1, 1, 0) or (1, 1, 1)
“Albert Indeed, I still do not know.”
in turn communicates to Bernard that Albert doesn’t have (1, 1, 1) or (1, 1, 2)
“Bernard And still neither do I.”
again communicates to Albert that Bernard doesn’ t have (1, 1, 2) or (1, 1, 3)
“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.”
At this Cheryl communicates to Albert and Bernard that none of their number is of the form (1, 1, ?)
“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.”
Now Albert and Bernard moved to do the same thing with numbers of the form (1, 2, ?) and Cheryl again communicates that neither of them has a number of such form
“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!”
Now Cheryl communicates that actually neither of them has a number of the form (1, ?, ?) — incrementing the last two digits isn’t enough. Having this information Albert and Bernard would finally begin with values of the form (2, ?, ?), but Cheryl provides more information by saying:
“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!”
After having said the same statement a hundred times, Albert would be ready to begin again, starting with number of the form (101, 1, ?). But since they still don’t know who has the largest number, (101, 1, 0) is excluded as a possibility,
“Albert Such powerful new information! But I am very sorry to say that still I do not know whose number is larger.”
Albert communicates to Bernard that his number isn’t (101, 1, 1)
“Bernard And also I do not know.”
Bernard communicates to Albert that his number isn’t (101, 1, 1) or (101, 1, 2)
“Albert But wait! It suddenly comes upon me after Bernard’s last remark, that finally I know who has the larger number!”
Since as far as we know Bernard could have any number from (101, 1, 3) and up, if Albert knows who has the larger number, then Albert’s own number is either (101, 1, 2) or (101, 1, 3). Albert knows which, but we don’t yet.
“Bernard Really? In that case, then I also know, and what is more, I know both of our numbers!”
Since Bernard knows both the numbers, then he must have been able to exclude one of the two possibilities. So Bernard’s number is (101, 1, 3)=101 – 1/2^1 – 1/2^4=101 – 1/2 – 1/16 = 100 7/16 , and Albert’s number is (101, 1, 2) = 101 – 1/ 2^1 – 1/2^3 = 101 – 1/2 – 1 / 8 = 100 6/16
Albert Well, now I also know them!
Would i be right in saying that at n=101, one of the numbers is 0, so the person with 0 would know that the other person has the larger number. And is there a reason why you specify n and k as positive integers and that r is a ‘non-negative integer’ (does that mean the r may be 0). I can do more math if I’m on the right track.
Yes, $n$ and $k$ should be positive integers, so amongst $1,2,3,\ldots$, whilst $r$ is a non-negative integer, so amongst $0,1,2,3,\ldots$. Various configurations of these numbers produce the rational numbers shown in the illustration diagram.
My solution is on Facebook (for example, my wall at https://www.facebook.com/howard.a.landman, currently at the top). I get that Albert has 100 3/8 (n=101,k=1,r=2) but I think it’s impossible to know Bernard’s number except that it’s larger.
Thanks for your answer, but unfortunately, since I’m not on Facebook, I don’t see anything at your link.
Did some latex for easy readablity:
https://www.overleaf.com/read/zqmshfxccxwg
After having spent a day thinking about this rather than work, we have come up with the answer:
Albert: 100 3/8
Bernard: 100 7/16
Pingback: #thatlogicproblem round-up | The Aperiodical
I’m sorry, but I don’t think we can infer Bernard’s number from the above. Albert’s is fine – his is 100 and 3/8, but as far as I’m concerned, Bernard could have any number larger than that (in the appropriate form of course), and would still know both numbers as soon as Albert announced that he now knew who had the smallest number.
Consider for example, if Bernard had 100 and 15/32. Cheryl makes her final announcement which gets them to 100 as the minimum value which one of them can have. Albert says he still doesn’t know, thus indicating to Bernard that he doesn’t have 100, then Bernard says he still doesn’t know, meaning that he doesn’t have 100 and 1/4. Albert then says he knows who’s got the smallest number, which can only be true if he has 100 and 3/8. And thus Bernard, who in this hypothetical scenario has 100 and 15/32, knows both numbers – he’s been told his own at the beginning (which really makes his statement that he now knows both rather redundant), and he’s just worked out Albert’s number from Albert blurting out that he knows who’s got the smallest. But this scenario holds whether Bernard has 100 and 7/16, 100 and 15/32, 100 and 31/64… or indeed any number of the appropriate format as long as it’s larger than Albert’s. Thus Albert cannot know Bernard’s number from these final sentences.
At the point where Albert anounced he knows who (must be him) has the smallest number he could have 100 and 1/4 as well. As it is only known that Bernard doesnt have it at this point.
Also you missed the part where Cheryl sayd “and you would still not know” and therefore are one step short.
Seems like Suhail Sherif has a valid point. I would like to know what answers others have to it? It can be reformulated as follows: after the Cheryls remark about 100 iterations, the first Albert’s reply doesn’t bring any new information on the table, because she just predicted that he wouldn’t know and that is precisely what he says: “I don’t know”. Since this was no new information, also the following Bertnard’s comment cannot be new information, and so the next remark of Albert cannot be justified.
This is probably not intended by Joel. Instead of her last remark Cheryl should say something like “after 99 times of saying that, no matter how many (finitely many) more cycles like this we go, you will still not know whose number is bigger.”
It seems to me that when he says he doesn’t know at that point, it does add new information—he still doesn’t know, even after she has said that. This is more than him not knowing just after her having said the 100th statement.
But doesnt that imply that credibility of Cheryl is questionable?
I don’t see how it would. She is only saying that after saying that statement 100 times, they (individually) won’t know something. She didn’t say that they would also know that the other person doesn’t know it.
If they both hear her and know that the other hears her as well, then if she says “neither of you will know”, then it includes the information that the other knows that you don’t know etc ad infinitum. But you might still be right, because she doesn’t say “after I say this, you will not know”, rather she says “you wouldn’t know even if I said this and that.” It’s subtle as you said and still a little bit unclear to me.
I don’t think it is unclear. If I say, “I know that you don’t know”, it isn’t ordinarily taken to mean that I know that you still don’t know even after I say that, which is essentially how you are trying to reason.
Cheryl predicted they would know when their epistemic state had included Cheryl’s 100th statement of that sort.
Albert’s “I don’t know” after that is his epistemic state after *both* the 100th statement, *and* Cheryl’s prediction, so it’s indeed new information.
(for some reason I can’t reply in the thread that I started, so – just happy you’ve found fusible numbers interesting, and I can’t wait to see your published proof that their order type is indeed epsilon_0 🙂 )
Up to index shifting mistakes, it should be 100+7/16 for Albert and 100+15/32 for Bernard.
Reasoning sketch:
The smallest number of this form is 1-1/2-1/2=0. But if A had that number, he knew that it was smaller, so his IDK means he doesn’t have 0.
If B had 0 or 1-1/2-1/4, the second smallest number, he knew now that his number was smaller. As he doesn’t, his number is neither 0 nor 1-1/2-1/4.
If this can go on forever, it means that k cannot be 1 while n is 1.
After each repition of this pattern, another value for k is excluded. So k can’t be 2,3,4,… while n is 1 either. This means that n cannot be 1 for any of their numbers.
If this can be done for a 100 times, it means that for neither of the numbers is n equal to 1,2,…,100. If after that they still don’t know, none of their numbers can be the smallest number with n=101, i.e. 100. This information is still part of the 100th repition. But according to C, they still don’t know after that was said – so their numbers can also both not be 101-1/2-1/4. With this, the final part of the dialogue starts:
A doesn’t know, so his number is not 101-1/2-1/8.
B still doesnt’ know, so his number is neither 101-1/2-1/8 nor 101-1/2-1/16.
But now A knows. So his number must be either 101-1/2-1/16 or 101-1/2-1/32. Also, A must have the smaller number.
Now B knows A’s number. If B had some number bigger than 101-1/2-1/32, he couldn’t know which of the numbers 101-1/2-1/16 or 101-1/2-1/32 A had. So his number is 101-1/2-1/16 or 101-1/2-1/32 as well. As he has the bigger number, he has
101-1/2-1/32 and A has 101-1/2-1/16.
Pingback: Solution to Cheryl’s Rational Gifts, my transfinite epistemic logic puzzle | Joel David Hamkins
Pingback: 趣题:无限多层嵌套的逻辑推理 | Matrix67: The Aha Moments
Pingback: 趣题:无限多层嵌套的逻辑推理 | 洋芋博客
Pingback: Still don’t know, an epistemic logic puzzle | Joel David Hamkins