Author |
Topic: Product and Sum, a variation (Read 1877 times) |
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
 |
Product and Sum, a variation
« on: Jan 23rd, 2010, 7:49am » |
 Quote  Modify
|
This is a variation of the classic "product and sum" problem. I put this in hard, because I am not sure of the answer  . The problem was given to me but I find no solution. In fact, I find that there is no solution.
A and B are mathematicians, C is a common friend. One day, A, B and C meet. C tells that he chose 2 numbers X and Y, 1<=X<=Y<=100. He gives a number to A (and A only) and tells that it is the product of the numbers. He gives a number to B (and only B) and tells that it is the sum of the numbers. C then asks who can guess the numbers X and Y. The dialog goes as follows:
A: this product is not enough to find the numbers.
B: I knew that.
The next day, the three meet again. C explains that he mixed up the papers. Actually, he gave the sum to A and the product to B. Follows the dialog:
B: This product is insufficient to find the numbers, but I know that A knows that.
A: Then I know what the numbers are.
B: Me too.
What are the 2 numbers?
|
| « Last Edit: Jan 23rd, 2010, 7:53am by Grimbal » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Product and Sum, a variation
« Reply #1 on: Jan 23rd, 2010, 2:44pm » |
Quote Modify
|
There are less than 500 pairs of values X and Y can take, if there can be confusion whether A and B's numbers are products or sums. So maybe I'll have a look at it tomorrow.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Product and Sum, a variation
« Reply #3 on: Jan 24th, 2010, 3:29pm » |
Quote Modify
|
There is: 5 and 7.
Step 1. There are 455 options when they can be mixed up.
Step 2. A could not get a total that is a unique product. 400 left.
Step 3. B thinks he has a sum. He tries to split it into two numbers that forms a unique product. But he can't. Most of the options he could have got split at least one way to form a unique product. Only 14 options are that cannot be split.
Step 4. Now he knows that his number is a product. 7 out of the 14 is a unique product. So he is left with 7:
7*5=35; 12
9*3=27; 12
17*3=51; 20
26*2=52; 28
27*1=27; 28
35*1=35; 36
51*1=51; 52
Step 5.
52 falls out being alone. Left 6 options.
Step 6. A can have 12, 20, 28, 36, 52. He has 12, or 28 otherwise he would already say the right result when he hears the mixing up of sum and product.
Step 7. A needs the information that B does not have 52. Should he interrupt here and say now I know, it would mean that he has the 28, B has 27. Well assuming that it is not politeness, but lack of information, means that he has 12.
Step 8. Now A also hears the second part of B's sentence. "But I know that A knows that". If B had 27 he would not say this (should A has 28, then A could not be sure that B does not know). So B can have 35 or 51. But for 51, A has a unique number, it means B has 35, A has 12. The numbers are 7 and 5.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Product and Sum, a variation
« Reply #4 on: Jan 25th, 2010, 1:05am » |
Quote Modify
|
Well, I like my solution, still it could not let me sleep and now I realised it was wrong.
1. First problem that during the first day A does not speak again. Would he speak if he would assume that he has the solution after B's response? It worth looking at once we know the result.
2. But once they know the mix-up it gets more interesting.
B speaks first, so he cannot know whether A already knows the numbers or not. According to the riddle we know nothing about A's knowledge, so we can assume that B does not know it either. But it worth trying both:
2.1 If B KNOWS that A does not know (otherwise A would start the conversation), then it would mean that A has a sum that can be made on at least two ways, i.e. 12 or 28 in five different ways. If B knows that only these 5 options remained then either he knows the answer or not. Again the riddle does not say whether B KNOWS the answer just does not say, or he does not know it.
2.1.1 Assuming that B would say if he knew, but he does not, it would mean B has 27, A has either 28 or 12. There is a contradiction already, because in case of 27 B cannot know for sure that A knows that the product is not unique. In case of 12 it could be unique (1+11). So it means that even if B knows the answer he does not say.
2.1.2 B can know the answer but talks in riddle leaving all the 5 options open. 11 B excludes in the first part of his sentence, leaving 27, 35 or 52. Now comes one more question: Is 52 a unique product. 52 is unique among the 14 options, but not in total.
2.1.2.1 If B's sentence mean it is not unique among the remaining options, then 52 we can exclude, remaining 27 and 35. A can have 27 two ways (28 and 12) and 35 also two ways (36 and 12). From the four 36 we already excluded when assumed that he did not say the solution because he did not know. B cannot have neither 27 nor 35, because both could mean 12 for A and that is a contradiction with B's sentence (second part).
2.1.2.2 If 52 we do not exclude, since it is not really unique, then B can have 27, 35 or 52. A can have 27 two ways (28 and 12), 35 also two ways (36 and 12) and 52 one way (28 ). Since B knows that A has a number non unique number (since did not say), and 12 cannot have either (has a unique split), it means that A has 28 and B has 52 (X, Y= 2, 26).
2.2 B does NOT know whether A already knows the solution or not (maybe he is just polite and does not start the conversation). Again B might or might not know the solution when he speaks first.
2.2.1 Assuming that B would say if knew, means he has 27 or 35 or 51, i.e. A has 28 or 12 OR 36 or 12 OR 52 or 20. B cannot have then first two because 12 can be uniquly split, i.e. B has 51, A has 52 or 20. But A answers NOW I know, while he would know it earlies should he has either 52 or 20. Contradiction.
2.2.2 We have to assume that B wouldn't say even if he knows. So we start with 14 options. with the first part of his sentence he excludes a large part of the options, but again 52 is a question.
2.2.2.1 Excluding 52, only remains B= 27, 35, 51. A has 28 or 12 OR 36 or 12 OR 52 or 20. A cannot have 12 (being uniquely splitable), leaving B=51, but then A= 52 or 20, so he could not say NOW I know it. contradiction.
2.2.2.1 52 is not considered unique. B can have 27, 35, 51, 52, A has 28 or 12 OR 36 or 12 OR 52 or 20 OR 28. Because 12 can be uniquely split, B is left with 51 or 52. Because A ONLY NOW knows the solution, it excludes 52 and 20 on his side, leaving A=28 and B=52 again.
So the solutiuon is 2 and 26.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Product and Sum, a variation
« Reply #5 on: Jan 25th, 2010, 3:04am » |
Quote Modify
|
on Jan 24th, 2010, 3:29pm, jollytall wrote:| Step 2. A could not get a total that is a unique product. 400 left. |
|
I have 345 left at this stage.
A product is unique if it is a prime, or if it exceeds 100 and is the product of two primes.
Quote:| Step 3. B thinks he has a sum. He tries to split it into two numbers that forms a unique product. But he can't. Most of the options he could have got split at least one way to form a unique product. Only 14 options are that cannot be split. |
|
And I still have 33 at this point.
And from there on I can't get to a solution without additional assumptions. Of course, we can assume B at this point would have said so, if he thought he knew the numbers. That would leave 19, but still leads me nowhere.
Here's the code I used for these first two steps:
javascript Code:<script>
function uniquefac(prod)
{
var i, cnt=0;
for(i=1; i <= Math.sqrt(prod); i++)
{
if(prod % i == 0 && prod/i <= 100)
cnt++;
}
return cnt==1;
}
function notuniquesplit(sum)
{
var i,j,res=true;
for(i=1; i <= sum/2 && res; i++)
{
j = sum-i;
if(j <= 100 && uniquefac(i*j))
res=false;
}
return res;
}
for(x=1; x <=100; x++)
for(y=x; y <=100; y++)
{
if( (x*y <= 200) && !uniquefac(x+y) && notuniquesplit(x*y))
document.write(x+" " +y "<br>");
}
document.close();
</script> |
|
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Product and Sum, a variation
« Reply #6 on: Jan 25th, 2010, 3:51am » |
Quote Modify
|
I did it on a spreadsheet manually.
Step 1 - I guess we agree.
Step 2 - It is unique if it is less than 100 and prime or more than 100 and a product of two primes or a cube of a prime (125 the only one like that). Can the difference be that you deducted even primes that are more than 100.
I had 55 exceptions (25 prime, 29 pq and 1 p3).
Step 3 - 14 I got from the reduced set of 400. Did you do it on the 345 of yours or on all the 455 to get to 33?
Anyway the evening I will doublecheck my spreadsheets.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
on Jan 25th, 2010, 3:51am, jollytall wrote:Step 2 - It is unique if it is less than 100 and prime or more than 100 and a product of two primes or a cube of a prime (125 the only one like that). Can the difference be that you deducted even primes that are more than 100.
I had 55 exceptions (25 prime, 29 pq and 1 p3). |
|
I've just counted all ways to factor the number in two factors such that both factors are smaller or equal to 100. But it turns out they're all just prime anyway.
For example, you can't have a sum of 125, because if x+y=125, and x<=y<=100, then x*y > 200. So that isn't one of the 456 cases under consideration.
I've attached a text file with all sums and their factorizations.
Quote:| Step 3 - 14 I got from the reduced set of 400. Did you do it on the 345 of yours or on all the 455 to get to 33? |
|
On all, because it is something B said he knew, i.e. past tense, so before he heard A's answer. (Whether that makes a difference, I haven't checked). So I apply both those criteria at the same time.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Product and Sum, a variation
« Reply #8 on: Jan 25th, 2010, 8:47am » |
Quote Modify
|
on Jan 25th, 2010, 3:04am, towr wrote:
A product is unique if it is a prime, or if it exceeds 100 and is the product of two primes.
|
|
Actually any number like p*n where p is a prime>50 and n>1 would be unique.
And there are cases like 2*11*11 where the 11's cannot be together. It can only be 11*22.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Product and Sum, a variation
« Reply #9 on: Jan 25th, 2010, 10:29am » |
Quote Modify
|
I attached the Excel:
The first sheet contains as a reference all products that are available (455)
The second contains all the sums (2 less, since 101 cannot be a product).
The third excludes those that cannot be because A does not know (all primes).
The fourth excludes that would allow a split that gives a unique product. A unique product is either 1*p, so the thought-to-be sum (in the excel prod because of the mixing up) is 1+p (p<100), OR it is p*q so the total is p+q with dark purple. It can also be 5*5*5, or total 30 or p*n where n>1 and p>50 (light purple). This as Grimbal also pointed out, every number over 55 is excluded (53+2).
Grimbal's 22*11 does not play, because the largest number can only be 200 (he thinks it is a sum!).
Unless I made an error somewhere, it leaves 14 combinations for the second day. The rest see above.
Modify: wrong Excel removed.
|
| « Last Edit: Feb 6th, 2010, 12:00pm by jollytall » |
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Product and Sum, a variation
« Reply #10 on: Jan 25th, 2010, 11:11am » |
Quote Modify
|
Quote:| 1. First problem that during the first day A does not speak again. Would he speak if he would assume that he has the solution after B's response? It worth looking at once we know the result. |
|
Well, my worry was that when both A and B assumes on the first day that they have the product and sum respectively then after the first day one of them will already know the solution. But the beauty of the riddle is that they do not.
A gets 28 and it is said to be the product. So when he says that he does not know, he has 1+28, 2+14, 4+7 in his mind.
B corretly says from his "sum" 52 that he knew that A won't be able to solve it, since 52 is one of those numbers that cannot be split in anyway to give a unique product.
But now the extra thought: A thinks that B sees 29, 16 or 11. Should none of them be unsplittable number (all would be splittable) he would realise that there is an error. Should there be only one unsplittable number (and 2 splittable), he would get the -wrong- result (although might not say). But to have a really good riddle the best if from the three at least two are unsplittable.
And actually none of them are splittable.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Product and Sum, a variation
« Reply #11 on: Jan 25th, 2010, 1:26pm » |
Quote Modify
|
Do you know how many cells you marked red on the third page of that xls sheet? 110. There are 345 cells left you haven't excluded at that point. So that matches with what I said.
I haven't looked at the last page yet.
|
| « Last Edit: Jan 25th, 2010, 1:26pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Product and Sum, a variation
« Reply #12 on: Jan 25th, 2010, 1:51pm » |
Quote Modify
|
One of the values we disagree is X,Y=1,51 (you have it on your list, I don't have it on mine)
If B sees 51, he can, thinking it's a sum, split it into 17+34, if A had 17*34 (which to them is conceivable because they don't yet know the sum and product can be confused), he would know X,Y=17,34, because there is no other way to factor them within the constraint that both factors <= 100. Therefore if B has 51, he cannot have known that A cannot deduce X and Y.
Another value we disagree is X,Y=1,5 (you don't have it on your list, I do)
If B sees 5, he can split it into 1+4 or 2+3, which would give A either 4 or 6 to work with, in either case A would not be able to find X and Y; so in this case B knew that A could not.
|
| « Last Edit: Jan 25th, 2010, 2:41pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Product and Sum, a variation
« Reply #13 on: Jan 25th, 2010, 10:20pm » |
Quote Modify
|
Thanks, it seems I made the mistake. I will check at the evening.
51 I understand why the mistake, 5 is surprising.
If I see it correctly, but again I will check, it reduces to 13 instead of 14.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Product and Sum, a variation
« Reply #14 on: Jan 26th, 2010, 9:38am » |
Quote Modify
|
on Jan 25th, 2010, 1:26pm, towr wrote:| Do you know how many cells you marked red on the third page of that xls sheet? 110. There are 345 cells left you haven't excluded at that point. So that matches with what I said. |
|
This I figured out. Earlier I had a Excel version, where I counted those products that are possible (i.e. can also be a sum) and give a unique solution. This was looking backwards, when B says on the second day that his number cannot be split.
This gives the 400, although this information is useless, since on the second day we already excluded much more.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Product and Sum, a variation
« Reply #15 on: Jan 26th, 2010, 12:08pm » |
Quote Modify
|
on Jan 25th, 2010, 1:51pm, towr wrote:Another value we disagree is X,Y=1,5 (you don't have it on your list, I do)
If B sees 5, he can split it into 1+4 or 2+3, which would give A either 4 or 6 to work with, in either case A would not be able to find X and Y; so in this case B knew that A could not. |
|
Sorry for the wrong reply a bit earlier. I thought you only had problem with those 2 values. Now I realised that I listed many more incorrectly (any p+q, although only p+1 or p+n where p>50, n>1 matters). I also missed in my logic few, like 50 (19+31) even if it was included because of the wrong logic.
Anyway the solution (hope it is OK now) is attached. B22 means the second half of B's sentence on the second day, B21 is the first half, while A2 is A on the second day.
Please check and let me know if you find an error again.
Modify: wrong Excel removed
|
| « Last Edit: Feb 6th, 2010, 12:01pm by jollytall » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Product and Sum, a variation
« Reply #16 on: Jan 26th, 2010, 1:11pm » |
Quote Modify
|
We still don't agree on page B1, your list includes all of mine, but much more also.
I only have
1,5 1,7 1,9 1,11 1,13
1,15 1,17 1,19 1,21 1,23
1,25 1,27 1,29 1,31 1,35
1,37 1,41 1,43 1,45 1,47
1,49 1,53
2,8
3,3 3,5 3,7 3,9 3,15
4,4
5,5 5,7 5,9
7,7
So, for example, you have 1,26 on your list, but 13x13 is a unique factorization.
[edit]
1,26 -> 13x13
1,34 -> 17x17
1,50 -> 25x25
2,13 -> 13x13
2,14 -> 11x17
2,18 -> 17x19
2,20 -> 17x23
2,23 -> 23x23
2,25 -> 25x25
2,26 -> 23x29
3,11 -> 11x22
3,12 -> 17x19
3,13 -> 13x26
3,17 -> 17x34
4,8 -> 13x19
4,10 -> 17x23
5,10 -> 25x25
6,6 -> 17x19
7,28 -> 98x98
[/edit]
|
| « Last Edit: Jan 26th, 2010, 1:33pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Product and Sum, a variation
« Reply #17 on: Jan 26th, 2010, 3:19pm » |
Quote Modify
|
Thanks towr,
Actually I have also found some in the meantime but not all.
So now I corrected B1, let's hope that that is correct. I used a dark colour with bold to highlight the changes.
But then I also changed B22. It is very interesting. Earlier I thought that e.g. 1+49=50 should be green since we have just did it with 19+31, so if B has on the second day 49 then he can assume that A has 50 but 50 can be uniquely split, so he would not say that A knows that.
But then I realised that in this example if A has indeed 50 then he knows the numbers too (all other options we locked out) and he knows that B cannot solve it because 1*49 and 7*7 are still open.
So on B22 the key is that it is not 1+p or otherwise the unique split is not yet excluded (no such case).
So, now B22 has less green.
On B21 I used dark blue for those that can be uniquely solved (and by the was A also knows it). there are the 1,p pairs.
The next blue I wanted to use for unique numbers where A also knows it, but now no such pair was found.
The light blue is used for unsolvable pairs, where for at least one of the pairs with the same product, A can imagine a unique solution (green on B22).
The dark green I again wanted to use like the middle blue (i.e. unique numbers) where A is not aware of a unique split. But again there is no unique product left.
And finally the green ones are where it cannot be solved (not unique number) and none of the options can A split uniquely. I think I found 2 pairs like these:
1*25=5*5. A can have 10 or 26. If A has 10, he can think of 1*9, 2*8, 3*7 or 5*5 for B, none of the solvable. If he has 26, he can think of 1*25, not good again.
1*21=3*7. A can have 10 (as above) or 22. If A has 22 he knows that B cannot solve it.
So both pairs meet the requirements.
Now A knows the solution. So he cannot have 10, because it is still not unique. So he has 22 or 26 and he knows the solutions.
BUT, UNFORTUNATELY B still does not know and neither do I.
I hope you can find one more error and finally we find the result.
Modify: wrong Excel removed
|
| « Last Edit: Feb 6th, 2010, 12:01pm by jollytall » |
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
I cleared up the above solution. The outcome is still the same, although with a twist.
Following the logic, only 10,22,26 can be A's number, but because 10 is still not unique, it is either 22 or 26, but in this case B (and we) still does not know.
But reading more carefully A's second day sentence, he say "THEN I know it". It also means that before B speaks he could not know it either. Shoul he has 22 or 26, he would know the answer even without B speaking. (I added a new sheet called A before day 2).
So A can only has 10, but then he does not know it either so, no solution.
But, there might be a small typo in the riddle, and then it is solvable. See next post.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
If the riddle is the same with only one difference:
1<=X<Y<=100, then there is a solution.
Solution with the same logic attached.
Please check.
|
| « Last Edit: Feb 6th, 2010, 12:23pm by jollytall » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
Hello,
I apologize for dropping the problem here and not participating. I was a bit busy at that time.
Anyway, I got the official answer.
There are 2 possible answers: (1,21) and (1,25).
Then I met the person who organized the contest, and he told me that others also complained but after a number of mails were exchanged, they agreed with the answer.
So I wrote a careful analysis to prove them wrong and ended up finding the same answer. 
I am joining a txt file with my investigations.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Product and Sum, a variation
« Reply #21 on: May 18th, 2010, 11:50am » |
Quote Modify
|
I got the same numbers (see the Excel TWO posts earlier). Indeed if A knows the answer (i.e. not 10 he has), then B can also know (I said it wrong). So there are these 2 solutions. But 2 solution is not nice to have.
With excluding x=y there is a unique solution. See the Excel in my LAST post.
|
|
IP Logged |
|
|
|
abcbcdcdef
Newbie
Posts: 5
|
same with everyone else here,
spent some time to write up a written solution
|
| « Last Edit: Aug 5th, 2010, 3:38am by abcbcdcdef » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
asweytoewty.txt