Puzzle!

Mike Schilling

Mike has been a software engineer far longer than he would like to admit. He has strong opinions on baseball, software, science fiction, comedy, contract bridge, and European history, any of which he's willing to share with almost no prompting whatsoever.

Related Post Roulette

18 Responses

  1. Jason Tank says:

    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

  2. Rod says:

    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

  3. Niall says:

    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

  4. Michael Cain says:

    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

  5. Mike Schilling says:

    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:

    Turn # “Yes”-er Possibilities
    1 Alf 1
    1 Bertie 1,2
    2 Alf 2,3
    2 Bertie 3,4
    3 Alf 4,5
    3 Bertie 5,6

    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

  6. Brendan says:

    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

    • Mike Schilling in reply to Brendan says:

      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

      • Brendan in reply to Mike Schilling says:

        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

      • Mike Schilling in reply to Mike Schilling says:

        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

  7. Brendan says:

    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

  8. Brendan says:

    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