GeeCON Prague 2014*
The moose likes Programming Diversions and the fly likes [medium]Challenge the mathematicians Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "[medium]Challenge the mathematicians" Watch "[medium]Challenge the mathematicians" New topic
Author

[medium]Challenge the mathematicians

Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
This was quite famous puzzle in 80s.See if you can solve.
--------------------------
Two mathematicians are placed in two rooms and one is given the sum of
two *distinct* numbers between 2 and 99 (2 and 99 *excluded*) and the
other is given the product of same two numbers. They both come out of the room and the following conversation takes place.
Mathematician with product : "I don't know the two numbers".
Mathematician with sum : "I know, you won't know the two numbers".
Mathematician with product : "Now, I know the numbers".
Mathematician with Sum : "Now, I too know the numbers".
The question is what are the numbers and how did they find it out ?
[ September 02, 2003: Message edited by: Capablanca Kepler ]

MH
HS Thomas
Ranch Hand

Joined: May 15, 2002
Posts: 3404

Mathematician with product : "I don't know the two numbers".
Mathematician with sum : "I know, you won't know the two numbers".

This part of the conversation suggests that there are 2 distinct numbers but that there are more than two numbers involved in the product or sum:
The series 3,3,98 have two *distinct* numbers.
Am I right in following this line of thinking ?
regards
[ September 02, 2003: Message edited by: HS Thomas ]
Greg Harris
Ranch Hand

Joined: Apr 12, 2001
Posts: 1012
i think we need more information to solve this...
P = product person
S = sum person
we do know that the two numbers are not both primes because the product would be prime and P would know the answer.
when P says he does not know the numbers, S knows that they are not both primes.
obviously, the product will not be numbers such as 30 and 81 because they factor as (2*15, 3*10, 1*30) and (3*27, 9*9, 1*81), which only leave one possibility.
...back to work... more on this later.
[ September 02, 2003: Message edited by: Greg Harris ]

what?
Mark Herschberg
Sheriff

Joined: Dec 04, 2000
Posts: 6037
I think they ke is the following. Given

We must then consider the properties of

And consider the relation of a and b to a' and b'

--Mark
Greg Harris
Ranch Hand

Joined: Apr 12, 2001
Posts: 1012
more things i thought of...
1. as i said before, because P does not know the numbers, the product is not prime and therefore the numbers are not prime.
2. because S can say, "you would not know the two numbers," we can assume that 1 number is odd and 1 is even. with 1 odd and 1 even number, the sum is odd, and therefore S also knows that the product is not prime and thus S knows that P could not know the answer. (if the sum was even, the numbers could both be odd, or both even and S would not be able to make this assumption).
i think there has to be a bound for the product or the sum... otherwise we have multiple combinations that reach all the way up to 96*97. of course, there are limits on the combinations when the numbers get too big because the product or the sum would be obvious.
Greg Harris
Ranch Hand

Joined: Apr 12, 2001
Posts: 1012
this seems too simple, but i think the numbers are 8 and 3.
1. The product is 24, which could be (4,6) or (3,8)
2. The sum is 11, which could be (3,8), (4,7) or (5,6)
When P says, "i do not know the numbers", S now knows that it is not (4,7) because that would be 4*7=28 and P would have known the answer because there is not another pair that would give 28.
Now, S says "you won't know the numbers" and P knows that the sum of the numbers is odd (see prime number idea above). the numbers cannot be (4,6) - so they have to be (3,8).
When P says , "i know the numbers" S knows that the numbers are (3,8) because until the previous step, P did not know the sum was ood. now that P knows the answer, S knows the numbers cannot be (4,6) because P was able to rule out 24=(4,6).
obviously (if my odd/even idea is correct), there are too many combinations for the sum above the first few integers...
of course, i could be totally crazy.
Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8815
    
    5
I think we're missing a clue...
Case 1:
product guy = 60, sum guy = 17 or 19, (5x12 or 4x15)
Case 2:
product guy = 70, sum guy = 17 or 19, (7x10, or 5x14)
In both cases the product guy can't know the numbers, and the sum guy's sum can work for more than one set too!
So for example, I'd say that 5-12, 4-15, 7-10, or 5-14 are all unresolvable with the information given.


Spot false dilemmas now, ask me how!
(If you're not on the edge, you're taking up too much room.)
Greg Harris
Ranch Hand

Joined: Apr 12, 2001
Posts: 1012
following my logic, one has to be odd and one has to be even... that is the only way S can know anything about the two numbers. because the sum is odd, S knows that at least one of the numbers is not prime, and therefore P cannot know the answer.
now, assuming that is correct, start writing a table of sums with the even integers in a column and the odd numbers in a row.

obviously, the numbers cannot be (3,4), (4,5), (3,6), (4,7), (5,6) because the product would be 12, 20, 18, 28, 30 and P would know the answer.
the first pair that would not be obvious to P and can still be determined by S are (8,3). the prodcut for P is 24 and there are only 2 possiblilities (8,3) and (4,6).
the last sum that can be determined by S is 11 because there are only 3 pairs (3,8), (4,7) and (5,6) that give the sum... after that, there are too many combinations and S would never know the answer.
so, given (3,8), we have
product = 24, combinations (3,8) (4,6)
sum = 11, combinations (3,8) (4,7) (5,6)
when P says, "i do not know the numbers," S knows that the pair is not (7,4) because that would be 28 and that is the only combination for the product. which leaves (3,8) and (5,6) for S.
when S says, "i know, you won't know the numbers," P knows that at least one number is odd, so that only leave (3,8) for P.
when P says he knows the numbers, S realizes that the numbers are (3,8) because (5,6) would give 30 and P would not have been able to chose between (5,6) and (3,10).
if you write the first 6 or 7 columns and rows of the addition table, you will quickly see that this is the only way S could ever chose 1 pair of numbers. there are numbers at the high end of the table, but those pairs generate unique products and P would have known the answer immediately.
i hope this is clear as mud (and that i am correct)
[ September 03, 2003: Message edited by: Greg Harris ]
Greg Harris
Ranch Hand

Joined: Apr 12, 2001
Posts: 1012
Bert:
i see what you are saying, but with the sum being 17, S has way too many possibilities: (3,14) (4,13) (5,12) (6,11) (7,10) (8,9)... obviously, the set of combinations gets bigger for any sum greater than 17 (up to 101 when it starts getting smaller).
i think the only way P and S can figure out the numbers is if the sum is fairly small so that S can determine his numbers because there are very few combinations for each product, so i think we have to look at it from the sum.
[ September 03, 2003: Message edited by: Greg Harris ]
Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8815
    
    5
Aha !
I got it ! (I think )
4 and 6

If I'm right it's because Greg got me back on the right track
Greg Harris
Ranch Hand

Joined: Apr 12, 2001
Posts: 1012
does anyone actually know the answer to this?
i still think 1 must be even and 1 must be odd for S to be able to know anything about the two numbers...
Michael Dunn
Ranch Hand

Joined: Jun 09, 2003
Posts: 4632
One link from google had the answer as 13,16
The explanation was over about 5 paragraphs (I got lost after 1, so gave up)
Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8815
    
    5
All right, I'll explain 4 and 6
The product is 24, the sum is 10...
The ONLY possibilities from the Sum-guy's perspective are 4-6 or 3-7
1 - The sum guy knows that if the product guy's number is 21, he'll know the answer.
2 - The sum guy ALSO knows that if the product's number is 24, he can't know.
When the sum guy says he knows the product guy can't know, he's confirming that it's option 2.
Yes? No?
Greg Harris
Ranch Hand

Joined: Apr 12, 2001
Posts: 1012
your solution sounds correct... however, if that was the case then S would have said, "i know the numbers" as soon as P said, "i do not know the numbers." we would not have needed statements 3 and 4.
with 3 and 8, S needs one more level of cancellation before he can determine which combination gives 11 and P only needs one level to determine 24.
of course, i am taking statement 4 literally based on the language and the placement in the conversation. it looks like S could not determine the answer until P did, and therefore (4,6) are not the numbers.
oh well... i guess we will never know the real answer.
Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8815
    
    5
Hmmm...
I see your point, and I agree in the purest sense... so back to the drawing board, I didn't put any effort into it after I came up with 4-6...
Junilu Lacar
Bartender

Joined: Feb 26, 2001
Posts: 4474
    
    6

Originally posted by Greg Harris:

1. as i said before, because P does not know the numbers, the product is not prime and therefore the numbers are not prime.

I don't quite follow this logic. If you multiply two prime numbers, the product will not be prime either.
Here's how I'm starting to analyze the puzzle:
An eligible factoring is one that has exactly two factors and each factor is a number in the range of 3..98 inclusive, denoted as [3..98].
The product will range from 12 (product of the two smallest possible numbers 3 & 4) to 9506 (the product of the two largest possible numbers, 97 & 98)
You would first eliminate all prime numbers between 12 to 9506 because their only factors are 1 and the number itself. Since 1 is not in [3..98], the product would not be a prime number.
Obviously you would eliminate any other products that have 0 eligible factorings as well.
Then you would eliminate products that have exactly 1 eligible factoring because the first mathematician said he didn't know what the numbers were, therefore the product had to have a least 2 eligible factorings.
Hmmm... seems like we could write a program to actually help solve this...
[ September 04, 2003: Message edited by: Junilu Lacar ]

Junilu - [How to Ask Questions] [How to Answer Questions]
Greg Harris
Ranch Hand

Joined: Apr 12, 2001
Posts: 1012
Originally posted by Junilu Lacar:

I don't quite follow this logic. If you multiply two prime numbers, the product will not be prime either.


sorry, i should have been more clear. if you multiply 2 prime numbers, the product will factor as the product of 2 prime numbers (obviously).
if the product was 21, P would automatically know the numbers were 3 and 7 and therefore the two numbers cannot both be prime.
i started this problem by looking at the products and i even made a table of all the products (even*odd)... after staring at that mess for a while, i made a table of the sums (even+odd) and it made sense.
[ September 04, 2003: Message edited by: Greg Harris ]
Junilu Lacar
Bartender

Joined: Feb 26, 2001
Posts: 4474
    
    6

Continuing my analysis:
The second mathematician, the one who was told the sum, says that the first mathematician would not know the numbers.
Let's look at how numbers work in terms of operation vs. odd/even:
odd + odd = even
even + even = even
odd + even = odd
odd * odd = odd
even * even = even
odd * even = even
The two mathematicians obviously both make the same calculations and must use this information somehow to eliminate the remaining eligible pairs left.
How does the statement "I know, you wouldn't know" help the first mathematician figure out what the numbers are?
Greg Harris
Ranch Hand

Joined: Apr 12, 2001
Posts: 1012
to make this easy, let us assume that my answer (3,8) is correct.
Product guy has a prodcut of 24, which means the pairs can be (4,6) or (3,8). obviously, he cannot determine the correct pair without more information.
Product guy says that he does not know the answer.
Sum guy has the sum of 11, which is odd. this means that one number is even and the other number is odd. this means that at least one number is NOT prime (the even number). if both numbers were prime, Product guy could factor the product into the product of 2 primes and then know the answer. this is why it is important that the sum is odd because this is the only way Sum guy can determine anything definite about the two numbers.
Sum guy says, "i know, you would not know the numbers" because he (Sum guy) knows that one of the numbers is even.
the importance of that statement to Product guy is this: with this information, Product guy knows that the sum is odd, and therefore exactly one number is even and one number is odd. because of this fact, Product guy can eliminate (4,6) and the pair must be (3,8).
Product guy says "i know the answer"
with this information, Sum guy knows what Product guy did to determine the pair, so Sum guy knows the pair is (3,8).
the possibilities for Sum guy were (3,8) (4,7) and (5,6).
(5,6) is eliminated becuase the product is 30 and Product guy would not be able to determine between (5,6) and (3,10) which, coincidentally is just (2*3*5) in a different order.
(4,7) is eliminated because the product is 28 and Product guy would have known the answer immediately because the only other pair is (2,14) which is not allowed.
thus, when Product guy says, "now, i know the answer" - Sum guy can eliminate (5,6) and he knows the answer is (3,8).
Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
I also got same answer 3,8.But I am not sure whether its right.I'll read the above stuff on week end.
Greg Harris
Ranch Hand

Joined: Apr 12, 2001
Posts: 1012
well, after all my effort, i am not so sure that (3,8) is the answer anymore. a friend came up with (13,16) - which michael posted above - and his reasoning sounds logical.
basically, sum guy gets 29 and then sum guy looks at all the possible pairs
(3,26)
(4,25)
(5,24)
(and so on ... )
notice that they are odd/even.
then sum guy looks at the product of each pair and then factors the product. interestingly, all the pairs except (13,16) can be factored into 3 or more primes. for example:

for (4,25) you have to look at 5^2 as 5*5. the explanation takes longer than i have now, but i think it sounds good.
[ September 05, 2003: Message edited by: Greg Harris ]
George Harris
Ranch Hand

Joined: May 05, 2003
Posts: 84
Greg,

I don't think the answer (3, 8) is correct because as you stated:

(4,7) is eliminated because the product is 28 and Product guy would have known the answer immediately because the only other pair is (2,14) which is not allowed.

Therefore the SUM guy would not have said:
Mathematician with sum : "I know, you won't know the two numbers".

Because there was a chance the PRODUCT guy would have know the two numbers.
Greg Harris
Ranch Hand

Joined: Apr 12, 2001
Posts: 1012
the product guy never considers (4,7)... only the sum guy considers that because the sum is 11.
product guy considers (3,8) and (4,6).
sum guy considers (3,8) (4,7) and (5,6).
when product guy says he does not know the numbers, sum guy eliminates (4,7).
George Harris
Ranch Hand

Joined: May 05, 2003
Posts: 84
My point is that the phrase used:
Mathematician with sum : "I know, you won't know the two numbers".

Implies that nothing was 'ruled out' but rather the SUM guy knew that all possible combinations produced a PRODUCT that was impossible to know the two numbers. It is assumed that the SUM guy does not do any filtering based on the response from the PRODUCT guy.
Junilu Lacar
Bartender

Joined: Feb 26, 2001
Posts: 4474
    
    6

Found this: http://mathforum.org/library/drmath/view/51609.html
A few differences in the problem but I think the factoring logic should be the same. As you'll see in the last message in that thread, the professor wrote a computer program to prove that there was a unique solution. Who can come up with that program? I was working on something along similar lines but it eliminates the solution so I guess that's out the window :roll:
[ September 05, 2003: Message edited by: Junilu Lacar ]
Greg Harris
Ranch Hand

Joined: Apr 12, 2001
Posts: 1012
the conversation is much more specific in that version... it is obvious that SUM knew before PRODUCT said anything that PRODUCT could not know the numbers. our version was not so clear.
however, i find it interesting that someone on that thread chose the same numbers that i did (3,8).
my friend wrote a program as well and it seems that the above mentioned (13,16) could be an answer. i will have to tell him about this solution and see what we can come up with.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: [medium]Challenge the mathematicians