-3
$\begingroup$

Here is a classic math olympiad problem (but this is NOT my question!): Each of the girls A and B tells the teacher a positive integer but neither of them knows the other's number. The teacher writes two distinct positive integers on the blackboard and announces that one of them is the sum of the numbers they told her. Then she asks A, “Do you know the sum of the two numbers?” If the answer is "no" then the teacher asks B the same question, and so on. Suppose the girls are truthful and intelligent. Prove that one of the answers will eventually be "yes".

(Source: "Mathematical Miniatures" by Svetoslav Savchev, Titu Andreescu, Mathematical Association of America, 2003).

(Solving this problem is not difficult, see e.g. the answers in https://math.stackexchange.com/questions/2819971/a-riddle-on-positive-integers)

Question: What is a good restatement of this problem in formal mathematical language? The informal statement of the problem above involves the concepts of knowledge and intelligence, which without careful formalization can lead to paradoxes (e.g. https://en.wikipedia.org/wiki/Unexpected_hanging_paradox). Clearly, one possible formalization is to define payoffs for the girls for answering the teachers question (e.g. payoff zero for answering "no", payoff minus infinity for answering "yes" and stating the wrong sum, payoff plus one for answering "yes" and stating the correct sum) and then setting this up as a two-player sequential game where the girls rationally maximize payoffs. I wonder whether there is a better formalization that stays closer to the informal statement above and avoids defining arbitrary payoffs?

(COMMENT: My original formulation of this question was not good, because it did not clarify right away that this "classic math olympiad problem" is not my question, and careful reading of the whole post was required to understand that. Therefore, within just a few hours of posting the question, it received 6 downvotes and only 1 upvote, and then was almost immediately closed. I strongly suspect that most of those 6 downvotes did only read the "classic math olympiad problem" and not my actual question. Within less than a day I then edited the question to avoid any misunderstanding for casual readers. Since that edit until now (within 30 days), this question has received 2 downvotes and 3 upvotes, but unfortunately has not been reopened, yet. Providing careful logical formalizations is clearly a question at the very heart of mathematics, e.g. the formalization in terms of rationally maximizing payoffs that I am alluding to above is simply a standard sequential game. So I am clearly asking a math question within the scope of this forum. I am obviously not interested in this little math olympiad problem itself -- that would not be research relevant -- but in the mathematical framework required for its formalization. For example, the Mathematics Magazine articles on "A Calculus for Know/Don't Know Problems" and "Goldbach, Lemoine, and a Know/Don't Know Problem" referenced by Gerald Edgar in his answer below are very relevant and interesting in that regard. By closing this question you have deprived other researchers from posting equally insightful answers, and you have deprived me of the benefit of those answers. I really hope you will reopen this question.)

$\endgroup$
7
  • 2
    $\begingroup$ plato.stanford.edu/entries/logic-epistemic/…. $\endgroup$
    – Dan Piponi
    Commented Mar 22, 2022 at 22:56
  • 1
    $\begingroup$ The intended meaning of ,"truthful and intelligent" is presumably that, if a girl has enough information to logically deduce the answer to the question she will answer it correctly and otherwise she'll say she doesn't know. I believe, however, that more than just "truthful & intelligent" is needed here. Each girl must know that the other is also truthful & intelligent and each must know that the other knows that she is truthful & intelligent, etc. A common term for such iterated "A knows that B knows that A knows..." is "common knowledge"; googling that term may help. $\endgroup$ Commented Mar 22, 2022 at 22:59
  • $\begingroup$ @AndreasBlass Is it like the common vs mutual thing terrytao talks about? terrytao.wordpress.com/2016/06/04/… $\endgroup$
    – BCLC
    Commented Mar 23, 2022 at 1:40
  • 1
    $\begingroup$ @BCLC Tao's description of common knowledge agrees with mine. $\endgroup$ Commented Mar 23, 2022 at 1:46
  • 1
    $\begingroup$ You have to be careful to avoid paradoxes such as en.wikipedia.org/wiki/Unexpected_hanging_paradox. $\endgroup$ Commented Mar 23, 2022 at 2:11

1 Answer 1

5
$\begingroup$

Q3. some literature for beginners

Austin, A. K., A calculus for know/don’t know problems, Math. Mag. 49, 12-14 (1976). ZBL0352.05001.

Kiltinen, John O.; Young, Peter B., Goldbach, Lemoine, and a know/don’t know problem, Math. Mag. 58, 195-203 (1985). ZBL0574.10001.

$\endgroup$
2
  • $\begingroup$ Is this answer copied from somewhere? I don't understand the "Q3" at the beginning, it looks as if it were taken from some FAQ. $\endgroup$
    – Alex M.
    Commented Mar 23, 2022 at 8:26
  • $\begingroup$ To Alex M.: I originally posted a longer version of the question that had three subquestions Q1, Q2, Q3, but the original question was closed because "This question does not appear to be about research level mathematics within the scope defined in the help center." I was given the option of editing the question and then I resubmitted a shorter edited version for review (but still the same question really). I hope they will open it again, because I think otherwise nobody can add further answers. Notice that I added a comment at the end the question acknowledging that it was edited. $\endgroup$ Commented Mar 23, 2022 at 9:59

Not the answer you're looking for? Browse other questions tagged .