5 ms·

Did I miss it, or does the article not actually explain why we know that at least one pair can be eliminated every round? It seems plausible that the process co

• otras 4y ago
  You’re totally right: there’s no guarantee that the candidate list continues to shrink, and there’s no guarantee that it won’t get stuck. For this problem, we are able to leverage the fact that it ends after 15 rounds, so the problem is less “run it until it finds a solution” and more “find the solution after exactly 15 rounds”. In fact, if you let it run past 15 rounds (for N=100, at least), and check the number of disqualified candidates between rounds, you’ll find that it does get stuck in after 15 rounds as the candidate list doesn’t change. The flip side of this is that there are also solutions before 15 rounds, too, but with the problem’s original statement, we’re looking at exactly 15.
• refurb 4y ago
  Yup, without a critical assumption - each "I don't know eliminates a potential solution" - it's not solvable because there is no new information when someone says "I don't know the answer"
  • rcxdude 4y ago
    The only critical assumptions are that they are aware of the details of what both of them have been given and that if they could have known the answer they would say so (i.e. that they are being perfectly logical and not making a mistake). The fact that this eliminates potential solutions is a consequence of that and the problem as set out. The whole puzzle hinges the fact that one person not knowing the answer from the part they are given (and the knowledge that the other person does not know after each step) constrains (i.e. gives information on) the answer. (but it is correct that as stated you could not derive all pairs of numbers this way: the puzzle gives you a sequence for which the pair is knowable)
  • vintermann 4y ago
    For N=100, though, they could know beforehand that potential solutions are eliminated at least the first 15 times someone says "I don't know". For any N, it should be possible to work out the longest such a game could go on (until one of them says, "I don't know, and I don't know any more from your last statement").
    • refurb 4y ago
      I would assume it hinges on the fact that when one party says "I don't know the answer" then they are eliminating a possibility (which isn't intuitive at all with that answer).
      • vintermann 4y ago
        I believe (I could be wrong here, I haven't rigorously checked this) that when the numbers are less than 100 and both parties know this, there will always be a possibility eliminated by a "I don't know" statement.
        • caf 4y ago
          After the round in the posed problem, it reaches a stalemate. If Peter had said "I don't know the numbers" at the end there, Sandy can exclude the possibility that the numbers were 77 and 84. However, at this point Peter already knows that Sandy still doesn't know the numbers: Even if the sum Sandy was told was 161, there are still five remaining live possibilities for that sum (62 + 99, 65 + 96, 70 + 91, 76 + 85 and 80 + 81), so Peter gains no new information from Sandy's next statement that Sandy does not know the numbers.
• vintermann 4y ago
  They did mention that you get stuck on certain N. That sounds like nice material for an OEIS sequence.