Lex Talionis

Argh. Narrowed down to 5 sums.

*head implodes*

Jesse

I got only 5 possible sums too, although I'm not confident about my math...were yours 13, 19, 25, 29 and 31?

Lex Talionis

Exactly those. Working on the relationship between the products now.

Jesse

Hmm. I got that the possible products associated with each of these sums looked like this:

13: 30 36 40 42
19: 48 60 70 78 84 88 90
25: 66 84 100 114 126 136 144 150 154 156
29: 78 100 120 138 154 168 180 190 198 204 208 210
31: 84 108 130 150 168 184 198 210 220 228 234 238 240

Now, based on Sam's answer, Polly will know the sum must be one of these five. If her product is associated with more than one sum, she won't be able to tell which sum is correct (for example, if her product was 100, then she wouldn't know if the sum was 4+25=29 or 5+20=25); so, based on her answer, the product must be associated with only a single sum. Crossing all the duplicates off the list:

13: 30 36 40 42
19: 48 60 70 88 90
25: 66 114 126 136 144 156
29: 120 138 180 190 204 208
31: 108 130 184 220 228 234 238 240

Either I've made an error in my math, which is quite possible, or else I think the problem as stated is wrong. There's no way Sam could know the numbers based only on Polly's answer. For that to work, there'd have to be a sum such that when you cross out all the duplicate products, there's only one product left on its row, but that doesn't seem to happen.

Scrambles

If Sam knows that Polly doesn't know then the sum must be odd, since if it was even then it could be the sum of two primes in which case Polly would know.

If the sum is odd it is the sum of an odd and an even number. Hence, one number must not have any 2's in it's prime decomposition. For polly to know the two numbers the prime factorization must be

2*2*...*2 * p (p a prime),

since otherwise if we had more than one odd prime factor we could have
2*2*...*q and p or 2*2*...*2*p and q
or 2*2*...*2 and p*q. In fact, you can have more that one prime factor if you take into account the possible range of number...

E.g. if you have 2*2*2*2*2*3*5. This can be decomposed (2*2*3)*(2*2*2*5) and (2*2*2*2*2)*(3*5). But if all 2's must be with one factor it must be (2*2*2*2*2)*(3*5).

Sam would then know what the numbers were if the sum could be uniquely expressed as a power of 2 (say 2^n) plus a number q_n which is either prime or has no prime factors (p) such that p*2^n <= 50.

Of course, Polly would know the decomposition straight away if it were of the form 4*p. Hence for Sam to know that Polly doesn't know in the beggining, we would need the sum to not be expressible as 4+p.

8 and 5 work:
(*)8+5 = 13, which is odd, and 13 can't be expressed as 4+p, so Sam knows it could be...
8+5: 8*5 = 4*10,
4+9: 4*9 = 3*12,
6+7: 6*7 = 3*21,
10+3: 10*3 = 5*6.

(*)Polly knows it must be 8*5 now.
(*)Can't express 13 as 16+x or as 4+q_2. Hence, Sam now knows the numbers.

I'm not convinced that the solution is unique though.



Scrambles

dolem98

Hmm, I have a list of more than 5 sums currently

13, 19, 25, 29, 31, 37, 43, 49, 53, 55, 59, 61, 67, 73, 79, 81, 85, 89, 91, 95

Although it does contain all the sums you two mentioned. What gives you cause to eliminate the higher ones that I have?

BTW, how are you doing this? I was using a c program.

Jesse

If it were 8 and 5, Sam could indeed say that Polly doesn't know, and his saying that would allow Polly to figure out that it was 8 and 5. But I don't think Sam would then be able to tell whether his sum of 13 came from 3+10, 4+9, 5+8, or 6+7; in each of these cases, Polly would be able to figure out the two numbers based on her product and Sam's comment that she doesn't know.

Lex Talionis

Jesse:

exactly what I have so far. Trying to see if there's something I'm missing, though.

Scrambles:

For the sum of 13, Polly couldn't possibly know the answer outright for the reasons you stated. However, 8+5 isn't the only solution: 4+9, 3+10, and 6+7 all work the same:

8+5=13; 8x5=40 or 4x10=40
4+9=13; 4x9=36 or 6x6=36
3+10=13; 3x10=30 or 5x6=30
6+7=13; 6x7=42 or 3x14

For the case of the sum 13, Sam knows that Polly can't identify the product because it isn't unique. In all cases, once Polly knows that Sam knows she can't identify the sum, she'll know which of the two it is.

The problem is this doesn't give Sam enough information to directly identify the number. Still working on that bit...

Jesse

The higher ones can all be eliminated because they can be expressed as a sum of (some number between 2 and 50) and (a prime number larger than 25). For example, 37 can be a sum of 8 and 29, which would give Polly the product 232 = 29*2*2*2. You can't group 29 with a 2 since you'll get a number higher than 50, so the only way to divide that into two groups whose product is between 2 and 50 is (29)*(2*2*2).

I spent like an hour last night doing this by hand. There are tricks that you can use to eliminate a lot of the possible sums right off the bat: for example, any sum that can be formed out of a prime number and 3, 4, or 5 you can automatically eliminate. And all sums above 31 can be eliminated based on my argument above (except 97 and 98, since the largest prime under 50 is 47 and 47+49= 96). That only leaves nine possible sums that need to be checked, although I didn't figure out all these tricks right away so I checked more of them by hand.

dolem98

I just found a problem with my code, will rerun and see if I get the same 5 sums.