Mr.S and Mr. P puzzle — "Formalization of two Puzzles Involving Knowledge", McCarthy, John (1987)
We pick two numbers $a$ and $b$, such that $a\geq b$ and both numbers are within the range $(2,99)$. We give Mr.P the product $a b$ and give Mr.S the sum $a+b$. Then following dialog takes place:
Mr.P: I don't know the numbers
Mr.S: I knew you didn't know. I don'tknow either.
Mr.P: Now I know the numbers
Mr.S: Now I know them tooCan we find the numbers $a$ and $b$?
I tried to do this, but it is very slow. I am sure there must be a simpler way.
Clear[pool, f1, f2, f3];
pool = Join @@ Table[{i, j}, {i, 2, 99}, {j, 2, i}];
f1[x_] := Length@Select[pool, Times @@ # == x &] != 1
f2[x_] := Length@Select[pool, Plus @@ # == x &] != 1
f3[x_] := And @@ (f1 /@ (Times @@@ Select[pool, Plus @@ # == x &]))
f4[x_] := Length@Select[Select[pool, Times @@ # == x &], f3[#[[1]] + #[[2]]] &] == 1
f5[x_] := Length@Select[Select[pool, Plus @@ # == x &], f4[#[[1]]*#[[2]]] &] == 1
Select[pool,
f1[#[[1]]*#[[2]]] && f2[#[[1]] + #[[2]]] && f3[#[[1]] + #[[2]]] &&
f4[#[[1]]*#[[2]]] && f5[#[[1]] + #[[2]]] &] // Timing