Description

There exist many variations of the puzzle but the most common is the following :

There are three agents: A, P, S (as in Announcer, Product, Sum)
A says to P and S : ”I have chosen x, y ∈ ℕ: (1 < x < y) ∧ (x + y < 100)”
Then P gives (privately) their sum to S and their product to P.
The following conversation between S and P then takes place:

• P: I don’t know the numbers
• S: I knew that
• P: Now I know the numbers
• S: Now I know them too

The objective is to determine x, y

About

The Sum and Product puzzle is a logic puzzle first published in 1969 by Hans Freudenthal and the number of solutions depends on the bounds set for x and y.The puzzle can be solved via an arithmetic approach based on the arithmetical implications induced on the sum and product by the statements of S and P.
In sort, the translation of the statements in an arithmetical setting are the following :

1. p is not uniquely expressible as a product of x and y with the aforementioned properties.
2. s cannot be expressed as a sum of x and y for which their product is uniquely expressible.
3. ∃! representation of p such that for the consequent sum s (2) holds.
4. ∃! representation of s such that for the consequent product p (3) holds.

It is provable the only such numbers for s and p for the given bounds are 17 and 52 respectively and so x=4 and y=13

Using Dynamic Epistemic Logic

We can imagine all (x, y) as nodes in an undirected graph. The graph has two types of edges :

• p-edges where (x1, y1)↔p(x2, y2) ⇔ x1y1 = x2y2
• s-edges where (x1, y1)↔s(x2, y2) ⇔ x1+y1 = x2+y2

That is the translation to a possible world semantics setting.
The conversation of P and S could be perceived as a sequence of truthful public announcements between the agents. Each of these announcements affect agents' knowledge, since they restrict the epistemic states each agent considers possible. Consequently, graph theoretic conditions on the node are imposed representing the actual world. The idea is that by searching for the nodes satisfying these connection properties, we are able to find all the possible pairs representing a solution to the problem.

After graph's construction G(V,E) we are searching for nodes satisfying the following conditions :

For u ∈ V
1. u→sv ⇒ ∃ w≠v: v→pw
2. (u→pv ∧ u≠v) ⇒ ∃ w≠v: (v→sw ∄ z: (z≠w ∧ w→pz))
3. (u→sv ∧ u≠v)⇒ (2) doesn't hold for v
Obviously v, w, z ∈ V

It is provable that in the given bounds the only node that satisfies conditions 1,2,3 is node (4,13)

Implementation

Main class file

Using Python 3.8 we implemented the above graph approach to the Sum & Product puzzle in this file. The whole puzzle is represented by class SumProductPuzzle where one can optionally change problem's bounds. The graph construction is pretty straightforward, we are using dictionaries as adjacency lists for the two edge types adjListP, adjListS. The above three necessary conditions are implemented as class methods condX. Finally the class method getSolution scans all graph nodes for nodes satisfying all three conditions.
You can run the program by typing in your terminal python sum_product.py

Unit testing

To test the program's validity we have developed a testing program that enables us to sanity check the methods' correctness. You can find that program here and test your own understanding on the puzzle by considering why each node passes (or not) the corresponding condition.

Finally, if the program takes too long to construct the puzzle's graph, you can download a binary file containing the puzzle data here. Both of these programs are designed to automatically look for that file and load the class; if the file is not found, it is being created locally.