Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Fri Apr 18, 2014 8:13 am

All times are UTC - 5 hours



Post new topic Reply to topic  [ 21 posts ] 
Author Message
 Post subject: Two numbers puzzle
PostPosted: Mon Feb 14, 2011 8:37 pm 
Offline
User avatar

Joined: Tue Feb 16, 2010 1:50 pm
This is one of my all time favorites:

Mr. S. and Mr. P. are both perfect logicians, being able to correctly deduce any truth from any set of axioms. Two integers (not necessarily unique) are somehow chosen such that each is within some specified range. Mr. S. is given the sum of these two integers; Mr. P. is given the product of these two integers. After receiving these numbers, the two logicians do not have any communication at all except the following dialogue:

  • Mr. P.: I do not know the two numbers.
  • Mr. S.: I knew that you didn't know the two numbers.
  • Mr. P.: Now I know the two numbers.
  • Mr. S.: Now, so do I.

Given that the above statements are absolutely truthful, what are the two numbers?


EDIT: I actually meant to post this in the "Enigmas, Riddles, and Paradoxes..." thread.
EDIT: slight re-wording of Mr. S. 2nd statement to make it clear he becomes aware of the 2 numbers after Mr. P's 2nd statement.

_________________
My Mods on Flickr


Last edited by roger on Tue Feb 15, 2011 11:05 am, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: Two numbers puzzle
PostPosted: Mon Feb 14, 2011 8:42 pm 
Offline
User avatar

Joined: Tue Mar 10, 2009 7:06 pm
Location: Nowhere in particular.
EDIT: Nevermind. I'll PM you in a minute with my answer.

_________________
~Kapusta

PB: At home (In Competition)
2x2 1.xx (2.88)
3x3 11.xx (15.81)
4x4 1:18.26 (1:24.63)
5x5 (3:00.02)
6x6 4:26.05 (6:34.68)
7x7 6:38.74 (9:48.81)
OH (35.63)

Current Goals:
7x7 sub 6:30
4x4 sub 1:10


Top
 Profile  
 
 Post subject: Re: Two numbers puzzle
PostPosted: Mon Feb 14, 2011 10:13 pm 
Offline
User avatar

Joined: Tue Aug 11, 2009 2:44 pm
You left out an important part of the puzzle!

BTW I know the two numbers. :-)


Top
 Profile  
 
 Post subject: Re: Two numbers puzzle
PostPosted: Mon Feb 14, 2011 10:16 pm 
Offline
User avatar

Joined: Tue Feb 16, 2010 1:50 pm
No winners yet, so here's a hint: both numbers are positive.

_________________
My Mods on Flickr


Top
 Profile  
 
 Post subject: Re: Two numbers puzzle
PostPosted: Mon Feb 14, 2011 10:22 pm 
Offline
User avatar

Joined: Sun Mar 08, 2009 9:21 am
Location: Massachusetts, USA
bhearn wrote:
You left out an important part of the puzzle!

BTW I know the two numbers. :-)

What part was left out? Is this why nobody has found a solution yet?

_________________
Katniss wrote:
Only on this forum would people use a V-cube 7 as a size comparison for a cat :lol:

My Shapeways shop


Top
 Profile  
 
 Post subject: Re: Two numbers puzzle
PostPosted: Mon Feb 14, 2011 10:28 pm 
Offline
User avatar

Joined: Tue Jul 27, 2010 10:17 am
Location: Missourica
I cheated :lol:

This is all over the internet, on one forum even a quantum physicist couldn't even figure out the solution!

You forgot to mention that EDIT: NEVERMIND, please refer to the next post by Roger.

Link to solution ***SPOILER ALERT***
http://everything2.com/title/Mr+Product ... 2527s+Quiz

Adam

_________________
Adam Brown, Puzzle Builder/Modder

Past project: The Geode
Current Project: Replica RPK-74
Future Project: Possibly another master mental
Oskar wrote:
I am now adding dummy cubes to my models to cross the 10% density threshold and save myself money big time.


Last edited by Adman234 on Mon Feb 14, 2011 10:53 pm, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: Two numbers puzzle
PostPosted: Mon Feb 14, 2011 10:50 pm 
Offline
User avatar

Joined: Tue Feb 16, 2010 1:50 pm
Adman234 wrote:
You forgot to mention that both the sum and product are less than 100. That is important.


Actually, it's not relevant to arrive at a solution. It's the range from which the numbers are picked that is relevant (the puzzle states "within some specified range"). Depending on the range, the solution may be a different one, but a solution nonetheless. So here is an additional hint, to ensure that everyone arrives at the same one: both numbers are within the interval [2,500].

_________________
My Mods on Flickr


Top
 Profile  
 
 Post subject: Re: Two numbers puzzle
PostPosted: Mon Feb 14, 2011 11:01 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
I've come up with a solving strategy. I see how the dialogue between the two can fill in the unknowns. If I have time tomorrow I'll write code to find two integers that meet the criteria.

I think if I were better at factoring and partitioning integers in my head I could just work through it for a few minutes to arrive at the answer.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Two numbers puzzle
PostPosted: Tue Feb 15, 2011 11:13 am 
Offline
User avatar

Joined: Tue Feb 16, 2010 1:50 pm
bmenrigh wrote:
I've come up with a solving strategy. I see how the dialogue between the two can fill in the unknowns. If I have time tomorrow I'll write code to find two integers that meet the criteria.

I think if I were better at factoring and partitioning integers in my head I could just work through it for a few minutes to arrive at the answer.


Writing a little bit of code is definitely helpful. You will find that initially there is a large set of numbers, i.e. don't try to do it in your head :-). When I first came across this puzzle a little over 10 years ago I was using 2D tables in Excel to keep track. I arrived at the solution manually, without the help of code, but it was a lot of work. It's kind of like solving Oskar's 17x17x17, once you know the algorithms, it's not that difficult, just a lot of work. The interesting part of the puzzle is coming up with the solving strategy.

_________________
My Mods on Flickr


Top
 Profile  
 
 Post subject: Re: Two numbers puzzle
PostPosted: Wed Feb 16, 2011 1:53 am 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Okay I wrote code to solve the problem. The way you worded it, I thought any sufficiently large interval would have a solution but that doesn't seem to be the case. There is no solution in the interval [50,500] for example.

In fact, there is only one solution in [2,500]. There are four solutions in [1,100].

I haven't actually manually verified that my program's output is correct though so I can't discount bugs.

bhearn, were you able to solve the puzzle that quickly using some mathematical trick? I haven't tried working out the properties to see if there is some way to arrive at the solution using algebra or a bit of number theory.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Two numbers puzzle
PostPosted: Wed Feb 16, 2011 11:23 am 
Offline
User avatar

Joined: Mon Oct 18, 2010 10:48 am
bmenrigh wrote:
Okay I wrote code to solve the problem. The way you worded it, I thought any sufficiently large interval would have a solution but that doesn't seem to be the case. There is no solution in the interval [50,500] for example.

In fact, there is only one solution in [2,500]. There are four solutions in [1,100].

I haven't actually manually verified that my program's output is correct though so I can't discount bugs.

bhearn, were you able to solve the puzzle that quickly using some mathematical trick? I haven't tried working out the properties to see if there is some way to arrive at the solution using algebra or a bit of number theory.


How is that possible? If four solutions are in the interval [1,100] then shouldn't they also be in [2,500]? Unless the solutions ALL contain a one.

_________________
--Noah

I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.


Top
 Profile  
 
 Post subject: Re: Two numbers puzzle
PostPosted: Wed Feb 16, 2011 11:30 am 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
NType3 wrote:
How is that possible? If four solutions are in the interval [1,100] then shouldn't they also be in [2,500]? Unless the solutions ALL contain a one.

If you are Mr. P and you are given the number 12 from the interval [2,500], the two numbers could have been (2,6) or (3,4). If they were picked from [1,100] they could have been (1,12), (2,6), or (3,4).

This difference in possible factors is significant.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Two numbers puzzle
PostPosted: Wed Feb 16, 2011 3:18 pm 
Offline
User avatar

Joined: Thu Jun 03, 2010 2:25 pm
Location: Farmington, NM
Answer PM'd

_________________
Autism Speaks can go away. I have Autism. I can speak for myself.

"You say tomater, I zader matermorts." - Coach Z


Top
 Profile  
 
 Post subject: Re: Two numbers puzzle
PostPosted: Wed Feb 16, 2011 8:03 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Jorbs3210 wrote:
Answer PM'd
Did you solve it by hand? Is there some trick to narrowing possibilities? My algorithm is roughly O(N^4) where N is the size of the range.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Two numbers puzzle
PostPosted: Thu Feb 17, 2011 4:56 am 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
I haven't gone through the maths (too lazy), but I think I've worked out the underlying logic:

  • Mr. P.: I do not know the two numbers. - means that there are at least 2 pairs of numbers which give that product.
  • Mr. S.: I knew that you didn't know the two numbers. - means that for all possible pairs of numbers that give the known sum, the product of each possible pair of numbers has at least 2 pairs of numbers which give that same product.
  • Mr. P.: Now I know the two numbers. - means that there is only one possible pair of numbers that satisfy both combinations above, given the actual product.
  • Mr. S.: Now, so do I. - means that the same pair of numbers can be deduced knowing the above conditions and the actual sum, without knowing the product.

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: Two numbers puzzle
PostPosted: Thu Feb 17, 2011 5:56 am 
Offline
User avatar

Joined: Tue Jan 13, 2009 8:23 pm
I figured out some parts, but had to look up the answer. I still don't understand it though, :cry:

_________________
For Jasmine Rose... Happy 2nd Birthday in Heaven, 2nd Dec 2013 xxx


Top
 Profile  
 
 Post subject: Re: Two numbers puzzle
PostPosted: Thu Feb 17, 2011 11:29 am 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Kelvin Stott wrote:
Mr. S.: Now, so do I. - means that the same pair of numbers can be deduced knowing the above conditions and the actual sum, without knowing the product.
This is by far the hardest step. Once Mr. P has deduced the solution, Mr. S must run through the same Logic Mr. P used but he has to do it for every product you can make from all of the ways you can partition the sum into two integers within the given range. It is quite easy for Mr. P to know the answer but quite a bit harder for Mr. S. There are tons of pairs of numbers that Mr. P could deduce the solution to but that Mr. S could not.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Two numbers puzzle
PostPosted: Wed Feb 23, 2011 8:00 pm 
Offline
User avatar

Joined: Tue Feb 16, 2010 1:50 pm
bmenrigh wrote:
NType3 wrote:
How is that possible? If four solutions are in the interval [1,100] then shouldn't they also be in [2,500]? Unless the solutions ALL contain a one.

If you are Mr. P and you are given the number 12 from the interval [2,500], the two numbers could have been (2,6) or (3,4). If they were picked from [1,100] they could have been (1,12), (2,6), or (3,4).

This difference in possible factors is significant.


Correct. In fact, you will find that a unique solution only exists for the ranges [2,62] through [2,865] and [3,94] through [3,957]. Ranges starting at 1 will always have more than one solution, and ranges starting at 4 or above have no solution.

_________________
My Mods on Flickr


Top
 Profile  
 
 Post subject: Re: Two numbers puzzle
PostPosted: Wed Feb 23, 2011 8:19 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
roger wrote:
Correct. In fact, you will find that a unique solution only exists for the ranges [2,62] through [2,865] and [3,94] through [3,957]. Ranges starting at 1 will always have more than one solution, and ranges starting at 4 or above have no solution.

Interesting. Can you describe the logic you used to arrive at those ranges?

For [2,y] I have
p=52 s=17; (4, 13)
p=244 s=65; (4, 61)

For [3,y] I have:
p=208 s=29; (13, 16)
p=1168 s=89; (16, 73)

My algorithm is really inefficient so checking larger values of y is horribly slow. There are some obvious optimizations I could do that would bring it down to around O(N^2) rather than whatever horrible runtime it is at now. Something like O(N^4).

Are there an infinite number of solutions? in [2,infinity)? My gut tells me no.


Edit: I just realized that the y upper bound matters. The solution [3,y] of (16, 73) doesn't work when y=2000 but does when y=1000. This should be obvious from the problem but it just occurred to me.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Two numbers puzzle
PostPosted: Thu Mar 10, 2011 2:57 pm 
Offline
User avatar

Joined: Thu Jun 03, 2010 2:25 pm
Location: Farmington, NM
Okay. I'll give. Here's how it works.


First of all, trivially, xy cannot be prime. It also cannot be the square of a prime, for that would imply x=y.

We now deduce as much as possible from each of the logicians' statements. We have only public information: the problem statement, the logicians' statements, and the knowledge that the logicians, being perfect, will always make correct and complete deductions. Each logician has, in addition, one piece of private information: sum or product.

P: I do not know the two numbers.

P's statement implies that xy cannot have exactly two distinct proper factors whose sum is less than 100. Call such a pair of factors eligible.

For example, xy cannot be the product of two distinct primes, for then P could deduce the numbers. Likewise, xy cannot be the cube of a prime, such as 33 = 27, for then 3×9 would be a unique factorization; or the fourth power of a prime.

Other combinations are ruled out by the fact that the sum of the two factors must be less than 100. For example, xy cannot be 242 = 2×112, since 11×22 is the unique eligible factorization; 2×121 being ineligible. Similarly for xy = 318 = 2×3×53.

S: I knew that you didn't know the two numbers.

If S was sure that P could not deduce the numbers, then none of the possible summands of x+y can be such that their product has exactly one pair of eligible factors. For example, x+y could not be 51, since summands 17 and 34 produce xy = 578, which would permit P to deduce the numbers.

We can generate a list of values of x+y that are never the sum of precisely two eligible factors.

Eligible sums: 11, 17, 23, 27, 29, 35, 37, 41, 47, 53.

(We can use Goldbach's Conjecture, which states that every even integer greater than 2 can be expressed as the sum of two primes, to deduce that the above list can contain only odd numbers. Although the conjecture remains unproven, it has been verified empirically up to 1018.)

P: Now I know the two numbers.

P now knows that x+y is one of the values listed above. If this enables P to deduce x and y, then, of the eligible factorizations of xy, there must be precisely one for which the sum of the factors is in the list. The table below shows all such xy, together with the corresponding x, y, and x+y. The table is sorted by sum and then product.

Note that a product may be absent from the table for one of two reasons. Either none of its eligible factorizations appears in the above list of eligible sums (example: 12 = 2×6 and 3×4; sums 8 and 7), or more than one such factorization appears (example: 30 = 2×15 and 5×6; sums 17 and 11.)

S: Now, so do I.

If S can deduce the numbers from the table below, there must be a sum that appears exactly once in the table. Checking the table, we find just one such sum: 17.

Therefore, we are able to deduce that the numbers are x = 4 and y = 13.

Eligible products and sums
Product x y Sum


18 2 9 11
24 3 8 11
28 4 7 11
52 4 13 17
76 4 19 23
112 7 16 23
130 10 13 23
50 2 25 27
92 4 23 27
110 5 22 27
140 7 20 27
152 8 19 27
162 9 18 27
170 10 17 27
176 11 16 27
182 13 14 27
54 2 27 29
100 4 25 29
138 6 23 29
154 7 22 29
168 8 21 29
190 10 19 29
198 11 18 29
204 12 17 29
208 13 16 29
96 3 32 35
124 4 31 35
150 5 30 35
174 6 29 35
196 7 28 35
216 8 27 35
234 9 26 35
250 10 25 35
276 12 23 35
294 14 21 35
304 16 19 35
306 17 18 35
160 5 32 37
186 6 31 37
232 8 29 37
252 9 28 37
270 10 27 37
322 14 23 37
336 16 21 37
340 17 20 37
114 3 38 41
148 4 37 41
180 5 36 41
238 7 34 41
288 9 32 41
310 10 31 41
348 12 29 41
364 13 28 41
378 14 27 41
390 15 26 41
400 16 25 41
408 17 24 41
414 18 23 41
418 19 22 41
132 3 44 47
172 4 43 47
246 6 41 47
280 7 40 47
370 10 37 47
396 11 36 47
442 13 34 47
462 14 33 47
480 15 32 47
496 16 31 47
510 17 30 47
522 18 29 47
532 19 28 47
540 20 27 47
546 21 26 47
550 22 25 47
552 23 24 47

_________________
Autism Speaks can go away. I have Autism. I can speak for myself.

"You say tomater, I zader matermorts." - Coach Z


Last edited by Jorbs3210 on Sat Mar 12, 2011 8:02 pm, edited 2 times in total.

Top
 Profile  
 
 Post subject: Re: Two numbers puzzle
PostPosted: Thu Mar 10, 2011 8:30 pm 
Offline
User avatar

Joined: Tue Feb 16, 2010 1:50 pm
Jorbs3210 wrote:
Okay. I'll give. Here's how it works.


Great explanation! You nailed it! :D

_________________
My Mods on Flickr


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 21 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group