Author |
Topic: Omnia mea mecum porto. (Read 583 times) |
|
rloginunix
Uberpuzzler
Posts: 1029
|
 |
Omnia mea mecum porto.
« on: Feb 22nd, 2015, 10:26am » |
 Quote  Modify
|
Omnia mea mecum porto.
A math professor R(iddler) tells two mathematicians, S(um) and P(roduct), so that both can hear:
R:
- I have two natural numbers in mind. Both are greater than one. Their sum is less than 100. To P I will whisper their product so that S can not hear it. (And R does). To S I will whisper their sum so that P can not hear it. (And R does).
Later on the following dialog between P and S ensues:
P:
- I can not name these numbers.
S:
- I knew ahead of time that you won't be able to.
P:
- But then I know them!
S:
- But then so do I!
And now you are invited to take a stab at deducing these two numbers. What are they?
To eliminate possible but irrelevant distractions: inject at will arbitrary finite time intervals between the statements to allow S and P to do their thing, no pair is in cahoots to mislead the remaining person, all three are not in cahoots to mislead you - the problem solver, all three tell the truth all the time and so on.
|
|
 IP Logged |
|
|
|
jollytall
Senior Riddler
Gender: 
Posts: 585
|
|
Re: Omnia mea mecum porto.
« Reply #1 on: Mar 7th, 2015, 1:30am » |
Quote Modify
|
4, 13
Edit: Could hide it 
|
| « Last Edit: Mar 7th, 2015, 1:33am by jollytall » |
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Omnia mea mecum porto.
« Reply #2 on: Mar 7th, 2015, 2:21am » |
Quote Modify
|
And the solution in details:
The Sum must be a sum that cannot be written as a total of two primes (otherwise S could not have been sure that P would not be able to solve). There are 24 such numbers between 11 and 97 (called T1 set).
The 24 numbers can be split into A+B pairs and from those 659 products can be composed between 18 and 2352 (T2 set).
From these 659 products some are the same, what need to be excluded, otherwise having any of those products, P would not know what A, B pairs it belongs to.
From the 659 products there are 335 single numbers (the other 324 is a collection of repeated numbers). The 335 numbers are between 18 and 2350. (T3 set).
From the numbers between 2 and 97 (min and max for A and B) there are 2351 products (1177 unique) where A<=B and A+B<100. These numbers are between 4 and 2450. (T4 set).
We need to exclude from T4 those that appear only once (otherwise P would immediately know the answer). That is left with 572 numbers in between 12 and 2352. (T5 set).
The common set of T3 and T5 is 208 numbers between 18 and 2340. (T6 set). These are the numbers where P cannot know immediately (T5), S knows that P will not know (T1), after getting this information P knows (T3 step).
We also know that once P knows, S also knows, so from T6 we have to check which are the ones where a given T3 has only one T6 element linked.
E.g. if the sum would have been 11 (cannot be made as the sum of two primes, i.e. in T1), but from A+B=11 we can make A*B=18 or 24 or 28, all three numbers are in T6, i.e. numbers that have only one C,D pairs where C*D=18, 24, or 28 and C+D is also appearing in T1.
The only number in T1 what has only one element in T6 is 17, with the product 52, hence the 4+13=17 and 4*13=52.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Omnia mea mecum porto.
« Reply #3 on: Mar 7th, 2015, 9:23am » |
Quote Modify
|
Expertly done, jollytall. Expertly done.
Your answer is correct and in my opinion your method is more algorithmic, more computer sciency if you will. For comparison purposes I will highlight my approach.
The share number of possibilities in analyzing the products was too much for my stomach - I went with the sum. Since both numbers can not be prime we recall Goldbach's conjecture - every EVEN integer greater than 2 can be represented as a sum of two primes. Hence, the sum can not be even and must be ODD - out of 96 possible sums eliminate 48. Now only 48 sums are left to work with. Next, it follows that (sum - 2) can not be prime - otherwise sum = 2 + (sum - 2) and P would know the answer immediately. Step through all the odd numbers from n = 5 to n = 99 and eliminate those for which n - 2 is prime. That left me with 24 sums: 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, 57, 59, 65, 67, 71, 77, 79, 83, 87, 89, 93, 95, 97.
Next, by contradiction we prove that sum < 55: if sum >= 55 then by subtracting 2 from both sides we can represent it as sum = (sum - 53) + 53 but then the product (sum - 53)*53 is unique: 53 is prime and hence the other factor must be 53*q, but q = 1 since if not then the factor is greater than 100 - not allowed. Hence, only 11 sums remain to analyze: 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53.
Then I eliminated 51: 51 = 17 + 34 and their product is 17*34 = 578 which can be represented only as 17*34 and 2*289 but 2 + 289 = 291 which is no good - it must be less than 55 at this point. Here is what was left: 11, 17, 23, 27, 29, 35, 37, 41, 47, 53.
Next I eliminated 35: 35 = 31 + 4 and their product 31*4 = 124 can be represented only as 31*4 and 2*62 but 2 + 62 = 64 which is no good - at this point it must be less than 55. In a similar way you can throw out all the numbers above 35.
And so on - the idea here is that as more and more sums are eliminated their values can be used as prohibitive filters for the next round of elimination.
It got a little tedious in the end. May be there is a more elegant (generic) way to cut the impossible numbers out.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print