Puzzle!
You invite two perfect logicians, Alf and Bertie, to play a game. Each of them is given a positive integer (i.e., one of 1, 2, 3, etc.) They’re also told that the other one’s number differs by exactly one from his; that is, if Alf has 3, he knows that Bertie has 2 or 4. They’re then asked alternately if they know what the other one’s number is:
Alf: No
Bertie: No
Alf: No
Bertie: Yes
A few questions for you:
1. What is Alf’s number?
2. What is Bertie’s number?
3. In general, if the Nth answer is the first “Yes”, what are Alf and Bertie’s numbers respectively?
rot13 any answers, so people can keep playing. (This means that you should spell out any numbers, since the rot13 of “42” is “42”.)
Obgu crbcyr jbhyq ernyvmr gung gur bayl Lrf pbaqvgvba jbhyq or orgjrra mreb naq nabgure ahzore. Vs Nys’f ahzore jnf bar, ur jbhyq xabj vzzrqvngryl gung Oregvr unq gjb. Fb obgu unir gb jbex qbjajneq sebz gurve erfcrpgvir ahzoref… fbzrubj?
Orlbaq gung, V’z ng n ybff.Report
Nys unf svir naq Oregvr unf sbhe. Va trareny, gur gjb ahzoref jvyy or A naq A cyhf bar naq Nys nyjnlf unf na bqq ahzore naq Oregvr na rira ahzore.Report
V qba’g guvax vg unf n havdhr fbyhgvba. Ohg V zvtug or jebat!
Gur svefg ab gryyf hf Nys vfa’g bar, nf vs ur jnf bar ur jbhyq xabj gung Oregvr jnf gjb.
Gur frpbaq ab gryyf hf Oregvr vfa’g bar be gjb, nf vs Oregvr jnf bar ur jbhyq xabj Nys jnf gjb, naq vs Oregvr jnf gjb ur jbhyq xabj Nys jnf guerr. (Vs Oregvr vf guerr ur qbrfa’g xabj vs Nys vf gjb be sbhe.)
Gur guveq ab gryyf hf gung Nys vfa’g gjb be guerr, orpnhfr vs Nys jnf gjb Oregvr jbhyq arrq gb or guerr, naq vs Nys jnf guerr Oregvr jbhyq arrq gb or sbhe. (Vs Nys vf sbhe ur qbrfa’g xabj vs Oregvr vf guerr be svir.)
Gur lrf gura gryyf hf gung Oregvr pna or guerr be sbhe naq Nys pna or sbhe be svir erfcrpgviryl, nf Oregvr xabjf uvf ahzore naq juvpu vf gur pbeerpg cnve, ohg jr qba’g.
Vf pnyphyngvat A qrcraqrag ba n havdhr fbyhgvba? Gur sbezhynf V’z pbzvat hc jvgu onfrq ba gung ner dhvgr uvqrbhfyl pbzcyrk. Sha gubhtu!Report
Oregvr’f ahzore vf sbhe. Nys’f ahzore vf svir. Trarenyvmvat gb a vf pbzcyvpngrq, frr arkg cnentencu.
Gur svefg ab nafjre vaqvpngrf “Zl ahzore vf terngre guna 1.” Ol vaqhpgvba, gur x-gu ab nafjre vaqvpngrf “Zl ahzore vf terngre guna x.” Yrg a or gur fznyyre bs gur gjb ahzoref. Cynl cebprrqf hagvy gur cynlre jvgu gur ynetre ahzore naabhaprf, “Zl ahzore vf terngre guna a-zvahf-bar” be “Zl ahzore vf terngre guna a.” Juvpu pnfr bpphef qrcraqf ba n pbhcyr bs guvatf (vf gur fznyyre ahzore rira be bqq, qvq gur cynlre jvgu gur fznyyre ahzore tb svefg be frpbaq). Vs gur bgure cynlre’f naabhaprzrag vf “Zl ahzore vf terngre guna a-zvahf-bar”, gura gur lrf nafjre jvyy or gur a-gu nafjre birenyy. Vs “Zl ahzore vf terngre guna a,” gura gur lrf nafjre jvyy or gur a-cyhf-svefg nafjre birenyy.Report
Bbcf. Oregvr’f ahzore pbhyq nyfb or guerr naq Nys’f sbhe. Oregvr xabjf jung Nys’f ahzore vf. Na bhgfvqr bofreire gung qbrfa’g xabj Oregvr’f ahzore bayl xabjf gung vg’f guerr be sbhe.Report
Evtug, gur nafjref nera’g havdhr, ohg gurl’er abg unez gb fhzznevmr. Pner gb tvir vg n gel?Report
Yrg a or gur fznyyre ahzore. Gura lrf vf gur a-gu nafjre vs a vf bqq naq gur cynlre jvgu gur fznyyre ahzore tbrf svefg, be vs a vf rira naq gur cynlre jvgu gur ynetre ahzore tbrf svefg. Gubfr ner gur pbaqvgvbaf haqre juvpu gur cynlre jvgu gur ynetre ahzore unf gb fvtany “Zl ahzore vf terngre guna a-zvahf-bar.”Report
Be whfg, lrf vf gur a-gu nafjre vs gur cynlre jvgu gur bqq ahzore tbrf svefg.Report
V qba’g guvax gung’f dhvgr evtug. V’yy tvir gur nafjre, naq lbh pna gryy zr vs jr’er fnlvat gur fnzr guvat.Report
Answer:
The only way one player can know the other’s number is if all the numbers lower than his have been eliminated; then the other player’s number must be higher than his. That is, it’s always the player with the lower number who will say “yes” first.
The only way Alf can know this on his first turn is if he has 1; then Bertie must have 2. Otherwise (that is, if Alf has anything other than 1), he must say “no”.
Likewise, on Bertie’s first turn, if he has a 1, Alf must have a 2. Further, since Alf has said “no”, he can’t have 1. Thus if Bertie has 2, he says “yes” because he knows that Alf must have 3.
On Alf’s second turn, he knows Bertie doesn’t have 1 or 2. So if Alf has 2, Bertie must have 3, and if Alf has 3, Bertie must have 4. If Alf says “no”, he doesn;t have 2 or 3.
On Bertie’s second turn, he knows Alf has at least 4, so a Bertie 3 means an Alf 4 and a Bertie 4 means an Alf 5. If Bertie says “no”, he doesn’t have 3 or 4.
And so on, with each “no” eliminating another two possibilities.
Putting this into a table:
etc.
In other words:
The player with the lower number will always be the one to say “yes”.
If it’s Alf, he will say yes on turn N if his number is 2N-1 or 2N-2.
If it’s Bertie, he will say yes on turn N if his number is 2N or 2N-1.Report
Mr. Schilling, up in the rot13 discussion, in response to my answer(s): “I don’t think that’s quite right. I’ll give the answer, and you can tell me if we’re saying the same thing.”
I worked in terms of individual answers. By induction, the k-th no answer is a signal that says “My number is greater than k,” no matter which player says it. If n is the smaller of the two numbers, the player with that number knows the answer when the other player’s no announces either, “My number is greater than n-1,” or “My number is greater than n.” Which announcement occurs depends on who goes first and whether n is odd or even. My answer on when the yes occurs in the sequence is that it will be the n-th answer if the player with the odd number goes first, and the (n+1)-st answer if the player with the even number goes first. Mr. Schilling’s answer works in terms of rounds, and answers the question, “In which round will the player with smaller number answer yes.
The two answers are equivalent (or at least, I’ll show that Mr. Schilling’s result can be derived from mine). Mr. Schilling’s answer assumes that Alf always goes first. As a result, the “My number is greater than k” information for a no answer will always have k being odd for Alf and even for Bertie. In round M, Alf’s k is 2M-1 and Bertie’s k is 2M. If Alf answers yes in round N, Bertie’s critical answer will be given in round N-1. Now we’ll just enumerate the possibilities. If Alf has the smaller number n and it is even, Bertie’s critical answer has the form “My number is greater than n”, so the number is 2(N-1)=2N-2. If Alf has the smaller number n and it is odd, Bertie’s critical answer has the form “My number is greater than n-1”, so the number is 2(N-1)+1=2N-1. If Bertie answers yes in round N, Alf’s critical answer is also given in round N. If Bertie has the smaller number and it is odd, Alf’s critical answer has the form “My number is greater than n” so the number is 2N-1. If Bertie has the smaller number and it is even, Alf’s signal has the form “My number is greater than n-1” so the number is (2N-1)+1=2N.Report
Got it. Mr Cain is entirely correct.Report
Hey mike pretty sure your completeness post is incorrect. You try to prove that S doesn’t have a least upper bound by showing you can always find a smaller least upper bound. That doesn’t make sense. What you work actually does is show there is no greatest lower bound (let’s call it L) for a set S defined like this. S is the set of all rationals who’s square root is greater than two. Then your work is correct it shows you can always find a number smaller than any supposed L. And therefore this set has no greatest lower bound. This can then be used to show your original set has no least upper bound. I am sorry for posting this here, that post was closed. That post still helped me a lot. If I am wrong could you email me.
-BrendanReport
You’re talking abut this post. It discusses the set S of positive rationals whose square is less than 2, saying, that
A. S is bounded above by 2, but
B. For any upper bound for S, it’s possible to find a smaller upper bound.
Thus it has no least upper bound, showing that Q (the field of rationals) is incomplete. What you suggest (showing that ~S has no greatest lower bound) can be done by exactly the same argument.Report
Okay I see now how your developing this argument. But you must show that there is no upper bound with the following property.
U^2<2. That is that an upper bound lies in S itself.
You make this assumption. But I'm not sure it is easy to prove.
Also in my post "square root" should be replaced by "square"Report
There’s a proof of that that I think goes back to Euclid. (It assumes unique prime factorization.)
Assume there is a rational square root of 2. It can be put in lowest terms as p/q. p*p/q*q = 2, or p*p = 2*q*q. Thus p is even, and equals 2*k for some k, so 2*q*q = (2*k) * (2*k) = 4*k*k. Dividing by 2, q*q = 2*k*k, so q must be even as well. But this contradicts our assumption that p/q was in lowest terms. Thus there is no rational square root of 2.
This argument can be generalized to prove that the only integers with rational square roots are the perfect squares (0, 1, 4, 9, etc.)Report
Well, I guess actually it is easy enough to show that there is no upper bound in S.
Just show that we can always find a larger member s’ in S, regardless of the choice of some s in S.
finding x in the rationals such that (s+x)^2 and then letting s’=s+x will suffice.
set s^2 +2sx+x^2 < 2.
and from here it easy, but doing it explicitly in terms of rational numbers would take some lines.Report
Yes we know there is no square root of two(that was known by the Pythagoreans blew up their whole world based on rational numbers thing). But the problem with your argument is not that. It is that you assume that there is no greatest s in S. But I just showed how to plug this whole.Report