Really hard Brain teaser I with.

[Gelsamel Epsilon]

Answer selects two natural numbers from the range [2,100] (x, y). He tells one man Sum' 's' (where s = x+y) and another man 'Product' 'p' (where p = x*y).

The men are asked to find x and y.
Both men have perfect logic.
Know that the starting numbers were selected from [2,100]
And are good mathematicians.

The following conversation occurs:

Product: I don't know what the numbers are.
Sum: I knew you didn't know what the numbers were, but I don't know them either.
Product: I know what the numbers are.
Sum: I know what the numbers are.

What were the numbers?
-----------------------------------------

I've tried brute forcing this but it was taking WAY too long for me to care. Is there any intuitive and easy way of figuring this out?

 

[texas_kiwi]

well i tried but it seems to me that a piece of information is missing. but that's just me.

 

[Gelsamel Epsilon]

Well what I've got so far >> Product's number can't be the product of 2 Prime numbers because otherwise it would have a solution (since the range doesn't include 1).

Also Sum -knew- that Product didn't know, which means the sums of the number cannot be the sums of 2 prime numbers, because then there would be a possibility of Product knowing.

From just these bits of information Product figures out x and y, and then sum does knowing that these bits of information are sufficient.

[/color]<<

I don't want to brute force all those numbers and figure out which numbers are left because it would just take too long and not be any fun. So I'm curious as to whether there is an easy or intuitive way to do it.

 

[davee123]

A few more tidbits:

A) Neither of the numbers can be a prime that's greater than or equal to 51. Take (for example) 97 and 44. The product is 4268, which has prime factors 2, 2, 11, and 97. Therefore, Product would know the answer, since those factors are only combinable in one way such that two factors are produced, with each one being less <= 100. For any two numbers where the prime factorization yields a prime >= 50, the factors are only combined in one such way.

B) The numbers can't have a sum of 4, 5, 199, or 200, or the answer would be known to Sum.

C) The product must not be uniquely derived from two numbers in [2,100]. For example, the product 9600 is ONLY possible from 96 and 100, which would immediately be known to Mr. P.

D) By way of elimination, (here comes the fun part) any combination which was precluded above MAY have the added bonus of making a particular sum be unique. Say, for example, that you ruled out the combination of 44 and 97, this MIGHT have the bonus (it doesn't) of making the *SUM* (which is 141) be unique, because you've just ruled out one of the possibilities.
[/color]

Commence answer bashing:

Taking D) into account, there are 7 unique sums which are:

6: from 2 and 4
7: from 3 and 4
173: from 77 and 96
178: from 88 and 90
179: from 80 and 99
180: from 90 and 90
181: from 81 and 100

Hence, if I've written my little bash-away-at-the-answer script correctly thus far and I haven't gone completely off course, the product MUST be one of 8, 12, 7392, 7920, or 8100. And right away we can rule out 8100 and 7920 because they appear in our list twice.

We can rule out 8 as a product because the only possible solution would've been 2,4, which Mr. P would have known without any input from Mr. S.

Let's look at 12. Mr. P can conclude right away that it's either 2,6 or 3,4. But he doesn't know which. If Mr. S were given the sum '8', then he could've had solutions (2,6), (3,5), or (4,4). When Mr. S hears that Mr. P can't figure it out, he knows that (3,5) is invalid. But he still can't pick between 2,6 and 4,4. But I don't see any way further. Strike 12.

So, the product appears to be 7392. Let's check it out.
Mr. P is given the product 7392. This means the numbers are either (77,96) or (84,88). He doesn't know which. But because Mr. S doesn't know, and the sum 173 is supposedly unique, we *should* see that the only answer left is (84,88).

Let's verify that 173 bit, and make sure that Mr S. would know the solution if he were given 173 as a sum. Commence ugly:
73,100 - violates A)
74,99 - violates C)
75,98 - violates C)
76,97 - violates A)
77,96 - !
78,95 - violates C)
79,94 - violates A)
80,93 - violates C)
81,92 - violates C)
82,91 - violates C)
83,90 - violates A)
84,89 - violates A)
85,88 - violates C)
86,87 - violates C)

So, indeed, if Mr. S were given the sum 173, he would KNOW that the answer would be 77,96. But he doesn't know, so it CAN'T be 173.

So, indeed, the answer is 84 and 88.
[/color]
DaveE

 

[DaveC426913]

Wow.
10 char[/color]

 

[Gelsamel Epsilon]

Is there anyway to verify these answers, I can't find anywhere on the net that gives the answer and explination.

 

[davee123]

Is there anyway to verify these answers, I can't find anywhere on the net that gives the answer and explination.

My post sort of does a flyby as I was solving it while writing... sorry 'bout that, I'll try and do a more detailed explanation later.

Possibly important point, however:

Now that I look at it again, however, there is one particular problem with the wording. Notice that Mr. S says "I knew you didn't know what the numbers were". This actually invalidates my former solution, and I think makes the problem unsolvable uniquely. This actually restricts the problem PHENOMENALLY, and I believe isn't intended.

If, for example, Mr. S were given the sum "10", then he knows that the solution is one of:

(2,8)
(3,7)
(4,6)
(5,5)

Mr. S is unable to tell which of these it might be, BUT he knows that if the answer were (3,7), Mr. P would know the answer right away, because the product would be 21, the product of two primes. But since Mr. S *knows* that Mr. P *didn't* know the answer before Mr. P admitted that fact, the sum cannot be 10.

We can go through sums like this via brute force, and determine whether or not it's a possible sum:

4 could be:
(2,2) <-- product is 2 primes

5 could be:
(2,3) <-- product is 2 primes

6 could be:
(2,4) <-- unique product
(3,3) <-- product is 2 primes

7 could be:
(2,5) <-- product of 2 primes
(3,4)

8 could be:
(2,6)
(3,5) <-- product of 2 primes
(4,4)

etc, etc.

Notice what happens when we get to 11:

11 could be:
(2,9)
(3,8)
(4,7)
(5,6)

There's no reason that this can't be a sum, again, since Mr. S knows BEFOREHAND that Mr. P doesn't know the answer.

If you're really bored, you can go through and verify these, but according to this rule, the sums that are possible by this rule are:

11, 17, 23, 27, 29, 35, 37, 41, 53

Since we've narrowed that list down, we can further narrow down the list of possible products, because we know that the product must be from a combination of numbers whose sum is one of the above sums.

Further, the assumption would be that the product must NOT have been unique before, but must be unique NOW, which is why Mr. P is able to solve it now, but couldn't before.

For example, the product 170. Mr. P doesn't know if the solution is (2,85) or (5,34) or (10,17). If it were (2,85), the sum would be 87. However, if this were the case, Mr. S could not have guaranteed that Mr. P didn't already know, because that's not on our list of valid possible sums. Similarly, if the answer were (5,34), the sum would be 39, which again isn't on our list, and again, Mr. S couldn't have guaranteed his assertion. However, the answer COULD still be (10,17), which is the ONLY viable solution left.

So a possible solution, given the present wording is (10,17).

However, the same is true for (3,38). And (18,35). And (11,16). And many more. In fact, there are 86 different solutions.

Hence, I expect that the CORRECT wording of the problem is (Note I've taken to calling them Mr. S and Mr. P since it's easier to distinguish when you're talking about the product and the person who was given the product):

Mr. P: I don't know what the numbers are.
Mr. S: I don't know them either.
Mr. P: I know what the numbers are.
Mr. S: I know what the numbers are.

This is the problem that I solved in my last post. As shown above, I think the problem as stated does not have a unique solution.

DaveE

 

[davee123]

Alright. Go #2 at explanation of the problem:

First, let me state what I stated above, that I am attempting to solve a slightly modified version of the stated problem. The modification is:

Mr. P: I don't know what the numbers are.
Mr. S: I don't know them either.
Mr. P: I know what the numbers are.
Mr. S: I know what the numbers are.

This is NOT the problem as stated, but it yields a better solution. I must admit, however, in re-examining the problem, I have found 2 possible solutions, which rather suprises me. Somehow before I was able to eliminate one of them, but I can't seem to do that again for whatever reason.

Anyway:

Immediately, we can eliminate many combinations of numbers and specific answers. We can eliminate:

1) Any two numbers which generate a unique product
1a) Any two prime numbers are guaranteed to be a unique product
2) Any two numbers which generate a unique sum

We can rule these out because if the product or sum were unique, the answer would have been instantly be known to Mr. P or Mr. S, and we know that it wasn't.

For instance, if Mr. P were handed the product "9600", he would know the answer was (96,100), because that's the only way of creating that particular product from 2 numbers in the range [2,100]. Similarly, if Mr. S were handed the sum "5", he would know that the answer was (2,3).

So. There are 4950 possible combinations of numbers that could have been picked. From those, there are a grand total of 2880 different products. 1793 of them are unique, and 1087 of them are non-unique. There are only 4 unique sums (4, 5, 199, and 200), and 193 non-unique sums. Not suprisingly, the set of answers that are precluded from unique sums are totally encompassed by the set of answers precluded by unique products.

Hence (as you would expect), there are 3157 different possible answers left, which neither Mr. P nor Mr. S could guess immediately.

The key pieces of information are A) Mr. S cannot guess the answer, even after he learns that Mr. P does not know it. B) Knowing that Mr. S still cannot guess the answer, Mr. P is able to determine the answer.

So. How does this happen? Well, the truth is that by removing a whole bunch of possibilities, we've POSSIBLY created some sums which weren't unique before, but which are unique now. How'd we do that?

Take a look at the sum "7". Initially, Mr. S does not know if the solution is (2,5), or (3,4). It could be either for all he knows. BUT. Mr. S suddenly learns that Mr. P doesn't know the answer, because the product isn't unique. If the answer had been (2,5), then Mr. P WOULD have known it, because "10" is a unique product, which you can ONLY generate from 2*5 within the given range. So if this were the case, Mr. S would have known that (2,5) was eliminated, and the only possibility left would be (3,4). Hence, the sum "7" wasn't unique before, but after we learn that Mr. P doesn't know the answer, "7" becomes a unique sum.

For anyone who wants to bash away with brute force, you will find that there are now 6 unique sums:

7: from 3 and 4
173: from 77 and 96
178: from 88 and 90
179: from 80 and 99
180: from 90 and 90
181: from 81 and 100

So what does this mean? Well, it means that because Mr. S *still* doesn't know the answer, the sum CANNOT be one of these combinations. If it were one of these, Mr. S could figure it out.

But this is the clue that allows Mr. P to determine the answer! He now *knows* that the answer is NOT one of the above 6 possibilities. What this means is that just as before how we made particular sums unique that weren't previously unique, we've now potentially made particular *products* unique that weren't previously unique. And by doing this, we've eliminated one or more of Mr. P's options, and allowed him to make a conclusion.

Now our task is actually manually calculable. If we know that the above 6 sums were able to eliminate one of the possible product combinations, then we KNOW that the product must match one of the products of the 6 possible answers shown above, which are:

3 and 4 => 12
77 and 96 => 7392
88 and 90 => 7920
80 and 99 => 7920
90 and 90 => 8100
81 and 100 => 8100

First, look at 8100 and 7920, which each appear twice in our list:

If the product were 8100, there are only two possibilities, which are (81,100) and (90,90)! Hence, if that were the product, Mr. S would have known the answer either way, but he didn't.

Same goes for 7920. The only possible ways to obtain that product are (88,90) and (80,99). And again, Mr. S would have known the answer, but didn't.

Two possibilities remain. And for reasons I can't seem to fathom, I can't exclude either one.

Let's take a look at 12. If 12 is the product, then Mr. P knows that the answer is one of:
(2,6)
(3,4)

And we know that the answer isn't (3,4), because otherwise Mr. S would have gotten the answer immediately, since 7 was a unique sum. The answer *could* still be (2,6), however. And re-tracing my steps, I'm not sure how I assumed that that answer could be eliminated before. Hm.

The answer I got before, however, was with the remaining product, 7392, which is possible with (77,96) or (84,88). Again, if the answer were (77,97), the sum would have been 173, which was a unique sum, and Mr. S could have known the answer after hearing that Mr. P wasn't able to solve it initially. Hence, the only possibility left is (84,88).

So, for some reason, I'm coming up with two answers now: (2,6), or (84,88).

Any further ideas?

 

[Gelsamel Epsilon]

I know the riddle is solveable. But I don't have any idea how to cut down the numbers more.

 

[davee123]

I know the riddle is solveable. But I don't have any idea how to cut down the numbers more.

How do you know the riddle is solveable uniquely? Do you know what the solution is, but not know how to achieve it? Any idea on whether or not the problem is correctly stated?

DaveE

 

[davee123]

Ahh, alright, here we go. I was talking to a friend about this who was able to find the problem online. Indeed, the wording is correct, and my list of possible sums above is correct, but my code to figure out the answer was a bit flawed, since I wasn't verifying that Mr. S was able to deduce the answer given that Mr. P was able to deduce the answer.

DaveE

 

[grant9076]

I may be wrong but I believe that the answer is 2 and 6. The reason is because if the numbers are 2 primes, then Product would be able to figure it out on the first try. If the numbers were the product of 2 composite numbers, then neither one would be able to figure it out on the second try because there would be too many choices. Therefore, the product of the 2 numbers have to be expressible as the product of a prime number and a square of another prime number (12,18,20,etc). In addition, if the product (from this group) is greater than 12, there would be too many sum choices for Sum to narrow down the answer on the second try. So the product has to be 12.

This means that the choices for Product are: (2,6) and (4,3)


If the sum was 7 then the choices would be (4,3) or (5,2). Since (5,2) would have instantly given away the answer for Product, then Sum would have deduced the answer to be (4,3) on the first try.


If however, the sum was 8, then the choices would be (6,2) (4,4) and (5,3). Since (5,3) would have given away the answer on first try, that has to be eliminated leaving Sum with 2 choices.

To sum it up, each mathematician had to have only 2 choices. This is the only combination that I could find that did that.

I hope that my reasoning is correct.

 

[davee123]

I may be wrong but I believe that the answer is 2 and 6.

Nope-- the key thing to look at is that somehow, Mr. S *already* *knows* that Mr. P doesn't know the answer.

If the answer were (2,6), then the sum would be 8 and the product would be 12. Mr. S looks at his sum, and determines that the answer is one of:

(2,6)
(3,5)
(4,4)

Now, Mr. S looks at it and thinks "I don't know the answer, but if the answer turns out to be (3,5), then Mr. P will surely know the answer instantly!"

But that's not how it happened. Mr. S *knows* before Mr. P says anything that Mr. P can't guess the answer. See my post earlier in this thread, but the sum is necessarily one of:

11, 17, 23, 27, 29, 35, 37, 41, 53

DaveE

 

[shmoe]

(2,6) and (84,88) aren't possible answers, their sums are also the sums of two primes so mr S wouldn't have known that Mr P didn't know.

I'm not sure if this problem can be simplified enough that brute force isn't painfull by hand, but with a computer you can do the following:


Make a big list consisting of (i,j,i*j,i+j) for i ranging from 2 to 100, j from 2 to i.

Remove any from this list where i+j is the sum of two primes less than 100, these are what Mr S was able to remove.

When Mr P learns that Mr S was able to remove those from the list (since Mr S knew that Mr P didn't know the two numbers), Mr P now looks through this list to find which entries have his product i*j. Since Mr P is able to deduce what i and j are, we know that i*j will appear exactly once on this list. So remove all products i*j that appear multiple times. e.g we'll remove i*j=30 as a possibility here since (i,j)=(6,5) and (15,2) are two possibilities that give different sums.

From this remaining list, we know that Mr S can determine i,j. So whatever he knows i+j to be must appear on this list exactly once, just find the unique i+j. (as I've described it, i+j=199 and 200 will be on it exactly once as well, these can be tossed out as either would have determined i,j from the start for mr S)
[/color]

 

[0rthodontist]

Shmoe, that's not quite correct. This is how it should be done:

1- Make a list of all (i, j) where 2 <= i <= j <= 100

2- Remove all pairs (i, j) where for any two numbers x, y in your list such that x + y = i + j, then you have the product x*y not equal to the product of any other pair on your list. THIS is what S was able to remove when he said he knew Product did not know the numbers.

Also: note that it is not enough here just to stipulate that x and y are not both prime. For example if the numbers were (12, 97) then Product would know them immediately.

3- Remove from the resulting list all numbers that have a unique sum in the list. This is what mr. Sum eliminates in the second line when he says he doesn't know the #'s either.

4- Remove from the resulting list all numbers that do not have a unique product in the list. This is what mr. Product says in the third line, "I know what the numbers are."

5- Remove from the resulting list all numbers that do not have a unique sum in the list. This is what mr. Sum says in the fourth line, "I know what the numbers are."

 

[shmoe]

Shmoe, that's not quite correct.

Oh? What do you think is wrong with it?

If your complaint was I'm not removing as much as possible in the first batch of removals, then I'm claiming that's irrelevant. Removing just the sums of two primes is sufficient to get the unique answer in the end, except the (100,100) and (100,99) pair I mentioned. I didn't think it was worthwhile to go back and use Mr S's first statement more fully (or mr P's first statement at all) to get rid of these two pairs in with a bunch of other redundant removals.

 

[0rthodontist]

Well, maybe you are right and maybe you are not--I haven't written a program that follows my proposed algorithm. But if your program follows your algorithm, then after step 4 (removing duplicate products) it doesn't guarantee either that it didn't exclude a number that should have been included, or that it included a number that should have been excluded.

1- Make a list of all (i, j) where 2 <= i <= j <= 100

2- Remove all pairs (i, j) where for any two numbers x, y in your list such that x + y = i + j, then you have the product x*y not equal to the product of any other pair on your list.

Your algorithm makes a list that is a superset of this list.

3- Remove from the resulting list all numbers that have a unique sum in the list. This is what mr. Sum eliminates in the second line when he says he doesn't know the #'s either.

You skip this step, but the list you have is still a superset of the list produced at this step.

4- Remove from the resulting list all numbers that do not have a unique product in the list. This is what mr. Product says in the third line, "I know what the numbers are."

It is not clear now what your algorithm has after this step. Since it had a superset after step 3, it may eliminate numbers here that my algorithm does not eliminate. And for the same reason, my algorithm may keep numbers here that your algorithm does not.

5- Remove from the resulting list all numbers that do not have a unique sum in the list. This is what mr. Sum says in the fourth line, "I know what the numbers are."

You may have gotten the right answer, but you don't absolutely know it's the right one.

 

[0rthodontist]

Well, I implemented my algorithm and got as the answer (select) (4, 13)[/color]. I also implemented your algorithm and got (100, 99), (100, 100), and also (4,13)[/color]. So you did get the right answer in the end--though again your algorithm does not guarantee it is right.

 

[shmoe]

I mentioned removing the (100, 99), (100, 100) in the end.

I think you are correct that I may have removed other valid answers. given any pair (i,j) you can run through their statements and verify it is a possible answer though, which I did do with the last pair my algorithm left. So I knew it was an answer, but this didn't ensure there were no other valid ones. Possibly if you expanded the ranges for i and j more my algorithm would eventually have chopped off some valid possibilities (expanding the range and their won't be a unique answer I believe).

 

[0rthodontist]

Your algorithm may have chopped off a valid answer, but it also may have included a non-valid answer (as it did). So it doesn't guarantee that (4,13)[/color] is an answer. Theoretically, it could have chopped off all valid answers and included only non-valid ones, although it didn't.