Thorsten Seelend wrote:
> I'd like to get advices how to solve a specific programming task in
> procedural languages like Java, Pascal/Modula and C/C++.
> ...
> Mister X thinks about two integers between 1 and 100 excluding. He
> tells Susan the SUM of them and Peter their PRODUCT. The task for
> both is to get the two original values without telling each other
> the numbers, that Mister X told them.
> After some time Peter says: "I can't say definitively which are
> the original numbers." (It means there is more than one
> solution.) Then Susan responds: "I can't neither. But I knew
> that you couldn't know it." Peter: "Really? So now I know the
> original numbers". And finally Susan: "Now I know them too".
> Question: What are the two numbers, Mister X thought of.
> ...
Here's an attempt to explain why the (one and only) solution (4, 13)
fullfills the given facts.
Susan knows 17 = 4 + 13
Peter knows 52 = 4 * 13
Peter(1) : "I don't know the numbers"
From his view there are two possibilities:
52 = 4*13 and
52 = 2*26
Susan(1) : "I don't know either, but I knew that you couldn't know"
First part:
There are 7 possibilities to get a sum of 17, so Susan can't
know.
Second part:
For all these possibilities Peter(1) is true, i.e. there
exists no solution so that Peter could exactly factorize his
product.
x y product possible factorizations
======================================================
2 15 30 (2,15), (3,10), ...
3 14 42 (2,21), (3,14), ...
4 13 52 (2,26), (4,13), ...
5 12 60 (2,30), (3,20), ...
6 11 66 (2,33), (3,22), ...
7 10 70 (2,35), (5,14), ...
8 9 72 (2,36), (3,24), ...
Peter(2) : "So now I know the numbers"
Checking both possibilities -- (4,13) and (2,26) -- and do
thinking the way Susan did, he realizes that only the pair (4,13)
lets Susan knew that he can't know it. Assuming the pair (2,26)
and creating the according table like for (4,13) above, this table
starts with
x y product possible factorizations
======================================================
2 26 52 (2,26), (4,13), ...
3 25 75 (3,25), (5,15), ...
4 24 96 (2,48), (3,32), ...
5 23 115 (5,23). !!!!!!!
...
As you can see, if (2,26) would have been the solution, then from
the view of Susan there would have been at least one way to split
the sum 28 (=2+26, what Susan would have been told by Mister X) --
the pair(5,23) -- for those product -- 115 -- there exist only one
factorization (5 and 23 are prime). Hence Susan than couldn't have
knew that Peter too couldn't knew the original pair (a bit
difficult to write it down in english). So therefore Peter "now"
knows that (4,13) has to be the solution.
Susan(2) : "Now I know them too"
I better don't try to explain this ;-)
The problem is that neither the sum nor the product are told to
us. So, really all given facts are necessary (especially Susan(2)) to
compute the solution, i.e. find the one and only solution.
Thorsten Seelend
