Friday puzzle -- impossible puzzle

1/15/10, 11:05 AM #1

Alex Yeilding
Guest

Friday puzzle -- impossible puzzle

Well, not really impossible, but it has earned that name, since if you have not seen it before, it can look impossible.

Professors S and P are first-rate logicians, who make infallible deductions, and report them honestly. At a department gathering, a grad student presents them with a challenge. He says that he has chosen two distinct integers greater than 1. He announces that he has written the sum, which is less than 100, on one sheet of paper that he is folding and giving to Professor S. On another sheet of paper, he is writing the product, which he is giving to Professor P. Without telling each other the numbers on their sheets, P and S are to try to deduce the two original numbers.

Then this exchange takes place between the professors:

P: I don't know what the two numbers are.

S: I knew that. Neither do I.

P: Now I know what the two numbers are.

S: Now I do, too.

What are the two numbers?

Re: Friday puzzle -- impossible puzzle

1/15/10, 2:37 PM #2

Dan Donaldson
Member
Offline
5,264 posts

Registered: 9/17/01

Some musings

Haven't solved it, but have some thoughts ;-)

That P does not know shows that there is a set of numbers greater than 1 that could be a solution.

S would know that there is such a set, and has the same issue, mainly more than one possible answer.

There is an intersection of the two sets that has just one member, the answer.

Now, I just have to see if I am smart enough to figure out what it is. ;-)

- - -

I have been woodworking for about 25 years now, and would consider myself an enthusiastic amateur. My claim to fame (or infamy) has always been fixing stuff. I spent time in the Air Force in the 60's then went to work as an electronic technician for civil service. I finally got my EE, and being fed up with the civil service nonsense, took a job with Ford Motor Company until I went with the split to Visteon last year. I got interested in music and started playing in a bluegrass band. I wanted a new guitar, and that kind of led me into woodworking. I bought some books, a few tools, and built a guitar. Luckily, I didn't know any better than to try that as a first ever project. I still play it when I get a chance, so it must not be too bad if it can live for over 20 years. After a stint in Mexico for my job, I moved into a new house and built a small shop. Since then I have been collecting tools and skills, probably more of the former than the latter ;-). Finding this site has done more for my skills and enjoyment than anything else. I have learned a lot and really enjoy the friendships that I have made here. I have been married to LOML (Lori) for 32 years now and have 6 kids. When they are all gone, I want to get a 1 bedroom house (so there is not room for them to move back in) and at least a 6 car heated/air conditioned garage for a shop. (Dream on...)

Re: Friday puzzle -- impossible puzzle

1/15/10, 4:30 PM #3

Gary Smyth
Member
Offline
3,375 posts

Registered: 11/22/04

Work this and your weekend is in danger

I have to disqualify myself as I have one answer firmly etched in my mind. There may be others. I was part of a class that was guaranteed an "A" and no further attendance required if this could be mastered. Some of us thought that it could be done in a couple of days--HA! A semester later we ALL took the final exam with the numbers displayed on the front of the classroom blackboard. Without giving away an answer, look to Goldbach and non-prime and prime numbers. The possibilities are many but then they don't always fit the clues provided at the start. This is long form number bashing but thankfully it doesn't have to be. It's the proof that is the killer and one I could never achieve. I've been waiting to answer this for thirty five years. If no one succeeds I'll give my numbers (you work the proof) Sunday. Good luck.

Re: Friday puzzle -- impossible puzzle

1/15/10, 4:48 PM #4

Alex Yeilding
Guest

Re: Work this and your weekend is in danger

Gary advised me privately of the answer he remembers, which is correct.

Re: Friday puzzle -- impossible puzzle

1/17/10, 2:15 AM #5

Dan Donaldson
Member
Offline
5,264 posts

Registered: 9/17/01

Re: Some musings

One other thing that I thought of. The numbers cannot both be prime because if they were, the product would be unique.

- - -

I have been woodworking for about 25 years now, and would consider myself an enthusiastic amateur. My claim to fame (or infamy) has always been fixing stuff. I spent time in the Air Force in the 60's then went to work as an electronic technician for civil service. I finally got my EE, and being fed up with the civil service nonsense, took a job with Ford Motor Company until I went with the split to Visteon last year. I got interested in music and started playing in a bluegrass band. I wanted a new guitar, and that kind of led me into woodworking. I bought some books, a few tools, and built a guitar. Luckily, I didn't know any better than to try that as a first ever project. I still play it when I get a chance, so it must not be too bad if it can live for over 20 years. After a stint in Mexico for my job, I moved into a new house and built a small shop. Since then I have been collecting tools and skills, probably more of the former than the latter ;-). Finding this site has done more for my skills and enjoyment than anything else. I have learned a lot and really enjoy the friendships that I have made here. I have been married to LOML (Lori) for 32 years now and have 6 kids. When they are all gone, I want to get a 1 bedroom house (so there is not room for them to move back in) and at least a 6 car heated/air conditioned garage for a shop. (Dream on...)

Re: Friday puzzle -- impossible puzzle

1/17/10, 2:28 PM #6

Gary Smyth
Member
Offline
3,375 posts

Registered: 11/22/04

As I said.

This is a hard trivia. Those are very smart Professors. One answer is 4 and 13. As I said, I remember ONLY the answer because I spent time on this a long time ago and never got close. The answer was posted as a reminder we were not a bright as we thought we were. If anyone wants to pursue perhaps this will help�or not. From the clue the �P� professor knows that the number (between 1-100) cannot both be prime numbers or they could be A x B�which from his statement they are not. 1 is out, therefore start identifying other primes 2, 3, 5, 7, 11, 13�

The second clue from professor �S� brings in Goldbach (who I barely remember�I had to search for it for this�all even numbers (except 2) are some combination of prime numbers added together) and from possible alternatives starts the number crunching. It�s a winnowing process. From here you are on your own.

Re: Friday puzzle -- impossible puzzle

1/17/10, 3:23 PM #7

Dan Donaldson
Member
Offline
5,264 posts

Registered: 9/17/01

Re: As I said.

I think that I am out of my league on this one ;-)

- - -

I have been woodworking for about 25 years now, and would consider myself an enthusiastic amateur. My claim to fame (or infamy) has always been fixing stuff. I spent time in the Air Force in the 60's then went to work as an electronic technician for civil service. I finally got my EE, and being fed up with the civil service nonsense, took a job with Ford Motor Company until I went with the split to Visteon last year. I got interested in music and started playing in a bluegrass band. I wanted a new guitar, and that kind of led me into woodworking. I bought some books, a few tools, and built a guitar. Luckily, I didn't know any better than to try that as a first ever project. I still play it when I get a chance, so it must not be too bad if it can live for over 20 years. After a stint in Mexico for my job, I moved into a new house and built a small shop. Since then I have been collecting tools and skills, probably more of the former than the latter ;-). Finding this site has done more for my skills and enjoyment than anything else. I have learned a lot and really enjoy the friendships that I have made here. I have been married to LOML (Lori) for 32 years now and have 6 kids. When they are all gone, I want to get a 1 bedroom house (so there is not room for them to move back in) and at least a 6 car heated/air conditioned garage for a shop. (Dream on...)

Re: Friday puzzle -- impossible puzzle

1/17/10, 9:18 PM #8

Alex Yeilding
Guest

Further clarification

Gary is right, and in fact, 4 and 13 are the only possibilities with the given restriction that the sum has to be less than 100.

First, look how 4 and 13 works:

Professor P is looking at "52" and says he doesn't know the numbers, since they could be 2 and 26 or 4 and 13. (BTW, professor P's statement is not even necessary--S can just state that he knows that P doesn't know the answer.)

Professor S is looking at "17". From that, he knows that the two numbers are (2,15), (3,14), ..., (8,9), none of which is a pair of primes. So he knows that P is not looking at the product of two primes, from which P would be able to deduce the answer.

Professor P knows that the numbers are (4,13) or (2,26). He tests whether S could be looking at "28". But if that were the number S were looking at, S would have to consider the possibility that the numbers were (11,17), in which case P would immediately know the two numbers. So if he were looking at 28, S would not have said that he knew P didn't know the answer. When P checks out the 4x13 factorization, he saes that 17 must be the number that S is looking at, so he knows the answer.

S can then back into the only possibility for P to know the answer based on the exchange to date, and states his knowledge of the answer.

And that is the easy part! We are asked to find 4 and 13, and show them to be unique.

This puzzle even has its own wikipedia page:

http://en.wikipedia.org/wiki/Impossible_Puzzle

And here is a discussion, with a link at the end to another discussion of solutions:

http://people.sc.fsu.edu/~burkardt/fun/puzzles/impossible_puzzle.html

Friday puzzle -- impossible puzzle

Posts