lii. Sum and Product Puzzle and Cheryl's Birthday

Problem (Freudenthal, 1969). Two integers $2\le x<y$ with $x+y\le 100$. S knows the sum, P knows the product. P: “I don’t know the numbers.” S: “I knew you didn’t.” P: “Now I know them.” S: “Now I know too.” Find them. Answer: 4 and 13. (Cheryl’s birthday is the same kind of puzzle.)

Method: keep the set of candidate pairs and filter it once per statement; each statement is a condition on how many candidates share the speaker’s value.

vector<pair<int, int>> sumAndProduct(int maxSum) {   // 2 <= x < y, x + y <= maxSum (Freudenthal)
    vector<pair<int, int>> all;
    for (int x = 2; x < maxSum; x++) for (int y = x + 1; x + y <= maxSum; y++) all.push_back({x, y});
    map<int, int> byP; for (auto [x, y] : all) byP[x * y]++;
    map<int, bool> sumOk;                            // S: "I knew P could not know": every split of the sum has an ambiguous product
    for (auto [x, y] : all) sumOk[x + y] = true;
    for (auto [x, y] : all) if (byP[x * y] == 1) sumOk[x + y] = false;
    map<int, int> byP2; for (auto [x, y] : all) if (sumOk[x + y]) byP2[x * y]++;          // P: "now I know"
    map<int, int> byS3; for (auto [x, y] : all) if (sumOk[x + y] && byP2[x * y] == 1) byS3[x + y]++;   // S: "now I know too"
    vector<pair<int, int>> res;
    for (auto [x, y] : all) if (sumOk[x + y] && byP2[x * y] == 1 && byS3[x + y] == 1) res.push_back({x, y});
    return res;
}

Proof: each filter encodes one statement

“P doesn’t know” means the product is shared by at least two candidates. “S knew that” means every pair with that sum has a non-unique product, which defines the set of good sums. “P now knows” means, among pairs with a good sum, the product is unique. “S now knows” means, among those survivors, the sum is unique. Applying the four filters in order to all pairs with $x+y\le 100$ leaves exactly $(4,13)$, which the code computes.