Don't read this (unless you are a masochist)
Thorsten Seelend
procedural languages like Java, Pascal/Modula and C/C++.
Some years ago we had an interesting home work at university that had
to be solved using Prolog. It was a kind of meta (meta-meta...) puzzle
known as the "Mister X problem". The explanation is (Don't blame me
about my strange englisch) :
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.
With the given informations (and the one indirectly given by the fact
that the question can be asked (implying that there really is exactly
one solution)), the task can be solved. In Prolog this isn't very
complicated: The approach is something like (informell):
Peter(1) ==> There exists an x (between 1 and 100) and an y so that
there exists more than one pairs of x' and y' so that
x' * y' = x * y.
Susan(1) ==> There exists an x (between 1 and 100) and an y so that
there exist more than one pairs of x' and y' so that
x' + y' = x + y
and
For all x' and y' with x + y = x' + y' `Peter(1)´ == true
and so on...
Those of you who are interested in the prolog program solving this (or
just in the original numbers to verify your solution), I can mail it.
But my question is: What approach I have to go to solve this task in a
non-logical programming language?
Any ideas?
P.S.: This really isn't a home work. I'm just interested in concepts
how to solve this.
Thanks in advance!
Thorsten Seelend
Subject: Don't read this (unless you are a masochist)W
I'd like to get advices how to solve a specific programming task in
procedural languages like Java and C/C++.
Some years ago we had an interesting home work at university that had
to be solved using Prolog. It was a kind of meta (meta-meta...) puzzle
known as the "Mister X problem". The explanation is (Don't blame me
about my strange englisch) :
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.
With the given informations (and the one indirectly given by the fact
that the question can be asked (implying that there really is exactly
one solution)), the task can be solved. In Prolog this isn't very
complicated: The approach is something like (informell):
Peter(1) ==> There exists an x (between 1 and 100) and an y so that
there exists more than one pairs of x' and y' so that
x' * y' = x * y.
Susan(1) ==> There exists an x (between 1 and 100) and an y so that
there exist more than one pairs of x' and y' so that
x' + y' = x + y
and
For all x' and y' with x + y = x' + y' `Peter(1)´ == true
and so on...
Those of you who are interested in the prolog program solving this (or
in the original numbers to verify your solution) I can mail it.
But my question is: What approach I have to go to solve this task in a
non-logical programming language?
Any ideas?
P.S.: This really isn't a home work. I'm just interested in concepts
how to solve this.
Thanks in advance!
Thorsten Seelend
Wolfgang Frech
I know that I knew this problem once, but I'm sure I did not solve it
with Prolog, though you could not verify this statement.
(meta-end:-)
I assume the prolog version does something like:
1. generate candidates
2. check them
3. backtrack when in dead end (implicitly in Prolog)
You can program that in procedural languages as well. For examples look
in a classic like N. Wirth's Algo.s + DS.
The problem space (100*100) is too large for paper and pencil, but not
for programs. There is no need to put too much sophistication in the
algorithm.
But just for the fun of it, I suggest a generator, pipe-and-filter
achitecture.
-Wolfgang
Thorsten Seelend wrote:
>
> 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.
>
Dennis Jones
the information presented in the problem, it appears that there are ~500 solutions, so I am
wondering, was the problem stated correctly?
- Dennis
Henry C. Grabowski III
Maybe I misunderstood the actual statement, but this is what my
code does...
1. Read two numbers from the command line, the first being the
sum, the second being the product.
2. Cycle through x and y from 2-100
3. if(x*y==product && (x+y)==sum) output the numbers.
Sounds like the Prolog algorithm made a mountain out of a molehill,
unless I've misinterpreted the problem statement.
Hank
Dennis Jones
sum or the product, so they cannot be input into the program. The second is that there is no
guarantee that you will enter numbers for the sum and product which will have a solution because
their domains are not defined.
- Dennis
Henry C. Grabowski III
dictate that there are multiple solutions to the problem. Actually
there are any number of solutions. In the problem statement the
only stipulation was that two numbers add to a sum and multiply
to a product. With that information no definite answer can be
attained. Even limiting the value of x and y to 2-99, you still
have many many solutions. You are right though my algorithm
doesn't solve that problem.
As far as the second problem, if there is no solution there is
no output. I suppose I could put a boolean operator in the
if statement and then before exiting the system could output
"no solution" if the value of the boolean was false (hence never
set to true).
Hank
kristof ulburghs
Just to elaborate on the problem, I don't have a solution ( yet ) :
Susan has obviously found a couple of possible solutions. She knows
Peter can't find the exact answer because there isn't one pair of
(solution) numbers that can be mulitplied and give a result that can't
be get by multiplying another pair. In other words, she has N pairs of
numbers and <= N/2 product results. Peter also had a couple of
solutions, but now he now knows that the sum of one of them yields pairs
of numbers solutions to Susan's problem, where N solutions has <=N/2
products. ( few ) Only one of his solutions had that property. Susan can
now reason along the same lines and test all of her solution products to
that fact.
This can of course be programmed but I don't know whether it's the most
efficient way of doing it.
Kristof
Thorsten Seelend
It was stated correctly. The one and only solution is (4, 13). See
the other posting for explanations
Thorsten Seelend
>
>
> Maybe I misunderstood the actual statement, but this is what my
> code does...
>
> 1. Read two numbers from the command line, the first being the
> sum, the second being the product.
> 2. Cycle through x and y from 2-100
> 3. if(x*y==product && (x+y)==sum) output the numbers.
>
> Sounds like the Prolog algorithm made a mountain out of a molehill,
> unless I've misinterpreted the problem statement.
>
> Hank
"...Read two numbers from the command line..."
Which `two numbers´? Don't forget that the sum and product are nowhere
mentioned in the task description. That makes it difficult to find
the solution. See my other posting for explanation.
Thorsten Seelend
Thorsten Seelend
>
> dictate that there are multiple solutions to the problem. Actually
> there are any number of solutions. In the problem statement the
> only stipulation was that two numbers add to a sum and multiply
> to a product. With that information no definite answer can be
> attained. Even limiting the value of x and y to 2-99, you still
> have many many solutions. You are right though my algorithm
> doesn't solve that problem.
>
> As far as the second problem, if there is no solution there is
> no output. I suppose I could put a boolean operator in the
> if statement and then before exiting the system could output
> "no solution" if the value of the boolean was false (hence never
> set to true).
>
> Hank
No. There really is exactly one solution (4, 13) that fullfills all
given facts. The reason of this is, that there only exists one pair of
given sum and product, that allows the stated dialog between Susan and
Peter to be correct. So there aren't "many many" solutions because
theren aren't many, many sums and products. See the other posting for
an explanation.
Thorsten Seelend
Thorsten Seelend
>
> 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
kristof ulburghs
I'll explain Susan(2) :
She tests all of the products against Peter(2).
i.e. Exactly one of these products has factorizations of which the sum
can be split in such a way that the products of all of those sum
combinations can be factorized in more than one way. I wrote it, it's
correct, but I sure as hell don't know what it means.
Kristof
kristof ulburghs
#include <iostream.h>
#include <math.h>
struct Pair_t
{
int x;
int y;
};
// Factorizes product for this problem area
void Factorize( int product, Pair_t * factors, int * pcount )
{
*pcount = 0;
for( int a = 2; a <= sqrt(product); a++ )
{
float b = (float)((float)product / a);
if( b != ceil(b) )
continue;
if( factors )
{
factors[*pcount].x = a;
factors[*pcount].y = b;
};
(*pcount)++;
};
};
void SplitIntoTerms( int sum, Pair_t * terms, int * pcount )
{
*pcount = 0;
for( int a = sum; (a >= sum/2) && (a >= 2 ); a-- )
{
int b = sum - a;
if( b < 2 )
continue;
if( terms )
{
terms[*pcount].x = a;
terms[*pcount].y = b;
};
(*pcount)++;
};
};
// Peter_1 receives a product and decides if the product has more than one
factorization
int Peter_1( int product )
{
int count;
Pair_t factors[10000]; // plenty
Factorize( product, factors, &count );
if( count > 1 )
return 1;
else
return 0;
};
// Susan_1 receives a sum and decides if the sum has more than one term
combination
// AND if all of those term pairs multiplied obey the Peter_1 rule
int Susan_1( int sum )
{
int count;
Pair_t terms[10000]; // again plenty
SplitIntoTerms( sum, terms, &count );
if( count <= 1 )
return 0;
// Check the peter_1 rule for all the terms multiplied
for( int i = 0; i < count; i++ )
{
int dummy;
if( !Peter_1( terms[i].x*terms[i].y ) )
return 0;
};
return 1;
};
// Peter_2 receives a product and decides if exactly one of the
factorizations as a sum
// obeys the Susan_1 rule
int Peter_2( int product )
{
int count;
Pair_t factors[10000]; // plenty
// Call Factorize first to get the factorizations
Factorize( product, factors, &count );
int times_Susan_1 = 0;
for( int i = 0; i < count; i++ )
{
if( Susan_1( factors[i].x + factors[i].y ) )
times_Susan_1++;
};
if( times_Susan_1 != 1 )
return 0;
else
return 1;
};
// Susan_2 receives a sum and decides if excactly one of all the terms of the
sum multiplied
// obeys the Peter_2 rule
int Susan_2( int sum )
{
int count;
Pair_t terms[10000]; // you know, plenty of course
SplitIntoTerms( sum, terms, &count );
int times_Peter_2 = 0;
for( int i = 0; i < count; i++ )
{
if( Peter_2( terms[i].x * terms[i].y ) )
times_Peter_2++;
};
if( times_Peter_2 != 1 )
return 0;
else
return 1;
};
void main()
{
for( int x = 2; x < 100; x++ )
for( int y = 2; y < 100; y++ )
{
cout << "x = " << x << " y = " << y << "\n"; cout.flush();
if( !Peter_1( x * y) )
continue;
cout << "Peter_1 ok\n"; cout.flush();
if( !Susan_1( x + y) )
continue;
cout << "Susan_1 ok\n"; cout.flush();
if( !Peter_2( x * y) )
continue;
cout << "Peter_2 ok\n"; cout.flush();
if( !Susan_2( x + y) )
continue;
cout << "Susan_2 ok\n"; cout.flush();
cout << "Solution : x = " << x << ", y = " << y << "\n"; cout.flush();
exit(0);
};
};
kristof ulburghs
also
4, 61
16, 73
looking into it, but if anybody spots it, let me know.
Wouldn't be surprised if it's a rounding error or something like it.
Kristof
kristof ulburghs
Got it, error in factorize, I didn't check the 2 and 99 boundaries for a and b
> for( int a = 2; (a <= sqrt(product)) && (a <= 99); a++ )
> {
> float b = (float)((float)product / a);
>
> if( (b != ceil(b)) || (b > 99) || ( b < 2 ))
Thorsten Seelend
>
> >
>
> #include <iostream.h>
> #include <math.h>
> ...
A really straight forward and understandable solution!
Thanks
With a very small mistake: Your solution also delivers
4 61 and
16 73
This is because there on the hand exists more than one
factorizations of 4*61 and 16*73 but those are
outside the bounds of [2,99].
Thorsten Seelend
kristof ulburghs
If you read my replies to myself you will see I already corrected that
bug :-)
Kristof
Philip Preston
>
>Here's an attempt to explain why the (one and only) solution (4, 13)
>fullfills the given facts.
I tried to solve this in Java using Hashtables and Vectors but I came up
with 86 possible solutions. Let me walk through one of them, (2, 9),
alongside your explanation:
>Susan knows 17 = 4 + 13
>Peter knows 52 = 4 * 13
Susan knows 11 = 2 + 9
Peter knows 18 = 2 * 9
>Peter(1) : "I don't know the numbers"
> From his view there are two possibilities:
> 52 = 4*13 and
> 52 = 2*26
Peter(1): "I don't know the numbers"
From his view there are two possiblilies:
18 = 2*9 and
18 = 3*6
>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), ...
Susan(1) : "I don't know either, but I knew that you couldn't know"
First part:
There are 4 possibilities to get a sum of 11, 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 9 18 (2,9), (3,6)
3 8 24 (2,12), (3,8), ...
4 7 28 (2,14), (4,7)
5 6 30 (2,15), (3,10), ...
>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.
Peter(2) : "So now I know the numbers"
Checking both possibilities -- (2,9) and (3,6) -- and do
thinking the way Susan did, he realizes that only the pair (2,9)
lets Susan knew that he can't know it. Assuming the pair (3,6)
and creating the according table like for (2,9) above, this table
starts with
x y product possible factorizations
======================================================
2 7 14 (2,7). !!!!!!!
3 6 18 (2,9), (3,6)
4 5 20 (2,10), (4,5)
As you can see, if (3,6) would have been the solution, then from
the view of Susan there would have been at least one way to split
the sum 9 (=3+6, what Susan would have been told by Mister X) --
the pair(2,7) -- for those product -- 14 -- there exist only one
factorization (2 and 7 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 (2,9) has to be the solution.
So, (2,9) seems to work just as well as (4,13).
What have I overlooked?
>Susan(2) : "Now I know them too"
> I better don't try to explain this ;-)
Please try! It must be the key to eliminating the other 85 possible
solutions, but I'm blessed if I can see it at the moment.
Philip Preston.
John Fletcher
>
> Thorsten Seelend wrote in message <36515191...@pixel.de>...
> >
> >Here's an attempt to explain why the (one and only) solution (4, 13)
> >fullfills the given facts.
>
>
> >Susan(2) : "Now I know them too"
> > I better don't try to explain this ;-)
>
> Please try! It must be the key to eliminating the other 85 possible
> solutions, but I'm blessed if I can see it at the moment.
>
> Philip Preston.
>
>
The problem builds up as follows:
After some time Peter says: "I can't say definitively which are the
original numbers."
[PETER1: There is more than one pair of factors]
Then Susan responds: "Neither can I, but I knew that you couldn't know
it."
[SUSAN1: The product of *every* pair of summands has the property
PETER1]
Peter: "Really? So now I know the original numbers".
[PETER2: *exactly one* pair of factors gives a sum with the property
SUSAN1]
Susan: "Now I know them too".
[SUSAN2: *exactly one* pair of summands gives a product with the
property PETER2]
Simplicity itself :)
--
Regards
John Fletcher
Philip Preston
(snip)
>Simplicity itself :)
Well it is when you put it like that :-)
Many thanks! Here it is in Java:
import java.util.*;
public class MisterX {
private static Hashtable answer, products, sums;
public static void main(String[] args) {
initTables();
peter1();
susan1();
peter2();
susan2();
printAnswer();
}
private static void initTables() {
answer = new Hashtable();
products = new Hashtable();
sums = new Hashtable();
for (int i = 2; i < 100; i++) {
for (int j = i; j < 100; j++) {
Pair pair = new Pair(i, j);
answer.put(pair, pair);
addToTable(products, new Integer(i * j), pair);
addToTable(sums, new Integer(i + j), pair);
}
}
}
private static void addToTable(Hashtable h, Integer key, Pair pair) {
Vector v = (h.containsKey(key)) ? (Vector)h.get(key) : new Vector();
v.addElement(pair);
h.put(key, v);
}
private static void peter1() {
for (Enumeration e = products.elements(); e.hasMoreElements(); ) {
Vector v = (Vector)e.nextElement();
if (v.size() < 2) answerRemove(v.elements());
}
}
private static void susan1() {
for (Enumeration e = sums.elements(); e.hasMoreElements(); ) {
Vector v = (Vector)e.nextElement();
if (v.size() < 2) answerRemove(v.elements());
else {
boolean ok = true;
for (Enumeration ev = v.elements(); ev.hasMoreElements(); ) {
ok &= (answer.containsKey(ev.nextElement()));
}
if (!ok) answerRemove(v.elements());
}
}
}
private static void peter2() {
for (Enumeration e = products.elements(); e.hasMoreElements(); ) {
Vector v = (Vector)e.nextElement();
int count = 0;
for (Enumeration ev = v.elements(); ev.hasMoreElements(); ) {
if (answer.containsKey(ev.nextElement())) count++;
}
if (count != 1) answerRemove(v.elements());
}
}
private static void susan2() {
for (Enumeration e = sums.elements(); e.hasMoreElements(); ) {
Vector v = (Vector)e.nextElement();
int count = 0;
for (Enumeration ev = v.elements(); ev.hasMoreElements(); ) {
if (answer.containsKey(ev.nextElement())) count++;
}
if (count != 1) answerRemove(v.elements());
}
}
private static void answerRemove(Enumeration e) {
while (e.hasMoreElements()) {
answer.remove(e.nextElement());
}
}
private static void printAnswer() {
for (Enumeration e = answer.keys(); e.hasMoreElements(); ) {
System.out.println((Pair)e.nextElement());
}
}
private static class Pair extends java.awt.Point {
Pair(int x, int y) {
super(Math.min(x, y), Math.max(x, y));
}
}
}