A brief take on a famous logic puzzle in terms of Epistemic Logic
by N. Nikolopoulos & N. Paslis
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 chosenx, 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:The objective is to determine
- P: I don’t know the numbers
- S: I knew that
- P: Now I know the numbers
- S: Now I know them too
x, y
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 :
x=4
and y=13
(x, y)
as nodes in an undirected graph. The graph has two types of edges :
(x_{1}, y_{1})↔_{p}(x_{2}, y_{2})
⇔ x_{1}y_{1} = x_{2}y_{2}
(x_{1}, y_{1})↔_{s}(x_{2}, y_{2})
⇔ x_{1}+y_{1} = x_{2}+y_{2}
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 :
u ∈ V
u→_{s}v ⇒ ∃ w≠v: v→_{p}w
(u→_{p}v ∧ u≠v) ⇒ ∃ w≠v: (v→_{s}w
∄ z: (z≠w ∧ w→_{p}z))
(u→_{s}v ∧ u≠v)⇒ (2) doesn't hold for v
v, w, z ∈ V
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
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.