well, another riddle - a logic one

[covise]

After all your riddles I had to post this one. Well, it's more a logic one with some (slight) mathematical background

Here we go:

Two natural numbers n, m within ]1,100[ are to find. One person, called Mr. Product, knows the product n*m of these two numbers. Another person, Mr. Sum, knows the sum n+m of these two numbers. Now, the following dialog arises:

Mr. Product: I don't know the two numbers.
Mr. Sum: I also don't know the two numbers, but I know you didn't know it.
Mr. Product: Now I know the two numbers.
Mr. Sum. Now I know the two numbers, too.

What are the two numbers?

a) 3 and 5
b) 2 and 7
c) 8 and 11
d) 4 and 13

[veribus]

Hmm. I don`t think it is solvable.

Since PRODUCT is unable to find the individual numbers, the PRODUCT is not expressible as Product of two prime numbers.

Since SUM tells that he knows for sure that PRODUCT would not have found the numbers, the SUM is not expressible as SUM of two PRIME NUMBERS. It the SUM is expressible so, then SUM cannot make such a statement with 100% surety. He can only make a GUESS

[covise]

Nice try But it's solvable - especially concerning the 4 solutions I have given.

BTW, this is part of an entrance test for
computer science students. They have 20
minutes to solve

[Minerva]

I think thats what ****** is studying.

[veribus]

Okay,

4 and 13.

Do you have a program solving that? I would like to see the semantic solution.

[Robot]

Ah damn it, i was working on that right now!!
You ruined all the fun!! ?
I was about to post my answer and I got the same answer as you so your probably right... It would taken alot longer to work it out without the multiple choice though.

******

[Toelover]

Hmm .... I had started with it but couldn't find a solution, but since I was curious about the explanation I did a quick search and found following answer on the same riddle (without the multiple choice) :

The answer is 2 and 6. The smallest number with two permissible product decompositions is 12=2*6=3*4. If the second mathematician had 7=3+4, he would have to be deciding between 3,4 and 2,5. Since 10=2*5 has only one product decomposition, it is out, so the second mathematician would have know the answer (3,4) after the first mathematician answered no the first time. Therefore it could not have been 7=3+4. If the numbers were larger, the negative answer of the second mathematician would not have given enough information to the first.

[veribus]

Sorry, ******! Didn`t mean to.
How did you solve it? I had help (Lisp):

;-*- Mode: Lisp; tab-width: 2; indent-tabs-mode: nil; -*-
;
; Copyright 2002 Bill Clagett
;
; Prints solutions to the Mr. P and Mr. S puzzle.
;
; There are two integers a and b, such that 2<=a<=b<=99. Mr. P
; knows the product of the two numbers. Mr. S know the sum of
; the two numbers. This conversation takes place:
;
; Mr. P: I don't know the numbers.
; Mr. S: I know you don't know the numbers.
; Mr. P: I know the numbers now.
; Mr. S: I know the numbers now too.
;
; What are the two numbers?


(defun make-series (a b)
"This function makes a list containing integers in a range."
(labels ((rec (a b accum)
(if (< b a)
accum
(rec a (1- b) (cons b accum)))))
(rec a b nil)))

(defun exactly-one (f l)
"This function returns true if f evaluates true for exactly one element of l"
(eq 1 (count-if f l)))

(let ((MIN 2)
(MAX 99))
(let
((all-products nil)
(all-sums nil)
(sum-to-products (make-array (+ 1 (+ MAX MAX))))
(product-to-sums (make-array (+ 1 (* MAX MAX))))
(product-to-factor (make-array (+ 1 (* MAX MAX)))))

(do ((a MIN (1+ a))) ((> a MAX))
(do ((b a (1+ b))) ((> b MAX))
(let ((p (* a b))
(s (+ a b)))
(push p all-products)
(push p (aref sum-to-products s))
(push s (aref product-to-sums p))
(push a (aref product-to-factor p)))))

(setf all-products (remove-duplicates all-products)
all-sums (make-series (+ MIN MIN) (+ MAX MAX)))

(let*
(
; Initially, we know nothing.
(possible-products all-products)
(possible-sums all-sums)

; Mr. P says "I don't know the numbers."
(possible-products (remove-if-not
(lambda (p)
(rest (aref product-to-factor p)))
possible-products))

; Mr. S says "I know you don't know."
(possible-sums (remove-if
(lambda (s)
(some (lambda (p)
(not (member p possible-products)))
(aref sum-to-products s)))
possible-sums))

; Mr. P says "I know the numbers now."
(possible-products (remove-if-not
(lambda (p)
(exactly-one (lambda (s)
(member s possible-sums))
(aref product-to-sums p)))
possible-products))

; Mr. S says "I know the numbers now too."
(possible-sums
(remove-if-not (lambda (s)
(exactly-one (lambda (p)
(member p possible-products))
(aref sum-to-products s)))
possible-sums)))

(dolist (s possible-sums)
(dolist (p possible-products)
(dolist (a (aref product-to-factor p))
(let ((b (/ p a)))
(if (= s (+ a b))
(format t "a=~s b=~s" a b)))))))))

[veribus]

The answer you have, toelover, is for numbers n, m within ]1,10[

[Funkster]

it was simple, just ask Mr Sum he would have told you the answer