![]() | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||
|
Goldbach's conjecture
editIf I remember correctly, isn't it neccessary to assume the Goldbach's conjecture as valid while solving this puzzle? --Tone 08:54, 9 May 2007 (UTC)
- True, but Conjecture has been numerically proved up to (as of April 2007) - much larger, than necessary in puzzle. --AndrejJ 10:41, 9 May 2007 (UTC)
Right, it's quite obvious that it holds in this case :-) --Tone 10:46, 9 May 2007 (UTC)
I don't get it. -F
Although the original version of the problem stated upper bounds on the numbers, I believe that since then it's been proven to be unique even for the unbounded case -- and without assuming Goldbach. Perhaps someone can find a reference to this and add it to the article. Joule36e5 (talk) 01:30, 30 October 2009 (UTC)
- Hm, no, it seems that additional solutions appear when the bound is high enough. I must have misremembered whatever it was about the unbounded case. Joule36e5 (talk) 03:43, 24 February 2011 (UTC)
- Pray tell, how? byo (talk) 06:14, 1 April 2017 (UTC)
Explanation of the puzzle
editI don't understand the puzzle and the conversation between S and P just confuses me more. I'm sure I won't be the only one, could somebody provide a better explanation?--Czar Kirk (talk) 23:16, 11 December 2008 (UTC)
- Does this help?
- P is given the product (in fact 52 but we do not know that yet) and cannot work out the pair of numbers which give that product (either 2*26 or 4*13)
- S is given the sum (in fact 17 but we do not know that yet) and knows that P cannot work out the answer (since if 17=8+9 then 72=8*9=3*24=2*36=etc., if 17=7+10 then 70=7*10=2*35=5*14, if 17=6+11 then 66=6*11=2*33=etc., if 17=5+12 then 60=5*12=3*20=etc., if 17=4+13 then 52=4*13=2*26, if 17=3+14 then 42=3*14=2*21=etc., if 17=2+15 then 30=2*15=5*6=etc.)
- P can now work out the answer as 4 and 13 (since P knows S must have either 28=2+26 or 17=4+13, but if S had 28 then the previous S statement would have been false since for example 28=5+23 and 115=5*23 uniquely within the constraints)
- S can now work out the answer as 4 and 13 (by eliminating other possible products 70, 66, 60, 42, and 30 as being inconsistent with the previous statement, for example with product 70 the sum could have been 17, 19 or 37 from P's point of view, but both 17 and 37 could have allowed S to have made the earlier statement so P would not have been able to work the answer out)
- the reader can then go through all the potential solutions and find that 4 and 13 (with product 52 and sum 17) provide the only answer within the constraints.
- --Rumping (talk) 14:30, 12 June 2009 (UTC)
The sum of x and y is 100 or less
editCurrently, the formulation of of the initial Freudenthal Problem here in the Wikipedia article starts with the statement, 'X and Y are two different integers, greater than 1, with sum less than 100.' This statement is incorrect, according to the formulation presented by Axel Born, Cor AJ Hurkens, and Gerhard J Woeginger in "The Freudenthal Problem and its Ramifications (Part II)." Bulletin of the EATCS 91 (2007): 189-204 [1]. Here is the formulation of the initial Freudenthal Problem according to Born et al, freely translated by the authors from the original Dutch in Freudenthal's 1969 paper:
The teacher says to Peter and Sam: I have secretly chosen two integers x and y with 2 ≤ x < y and x + y ≤ 100. I have told the sum s = x + y to Sam (but not to Peter) and the product p = x y to Peter (but not to Sam).
1. Peter says: I don't know the numbers x and y.
2. Sam replies: I already knew you didn't know.
3. Peter says: Oh, then I do know the numbers x and y.
4. Sam says: Oh, then I also know them.
Determine x and y!
Note that, according to Born et al, in Freudenthal's original formulation of the problem, the sum of x and y is less than or equal to 100 (not less than 100 as currently stated erroneously in the Wikipedia article).
1) https://www.win.tue.nl/~gwoegi/papers/freudenthal1.pdf 1.121.105.43 (talk) 01:05, 16 April 2015 (UTC)
I hesitate to add another program
editI hesitate to add another program, but one involving an n × (n/2)2 array should also be considered. — Arthur Rubin (talk) 19:31, 1 January 2016 (UTC)
Something like the MATLAB program
[x,y] = ndgrid([1:100] ,[1:100]); % this one, I checked in the manual
A = sparse(x+y, x.*y, (1 < x) & (x < y) & ( (x+y) <= 100)); create (sparse) array with potential (S,P) pairs
clear x,y;
% OK, let's start processing
pn = sum(A) == 1;% P knows the number
sn = A * pn > 0; % S does not know P does not know the number
A[sn,:] = 0; % clear entries which do not meet the first condition
pn = sum(A) > 1; % P does not now know the number
A(:,pn) = 0; % clear entries which do not meet the second condition
sn = sum(A,2) > 1; % S does not now know the number
A(sn,:) = 0; % clear entries which do not meet the third condition
[s, p] = find(A); % find non-zero entries (I think it returns them as column arrays)
dis = (s.^2 - 4*p) .^ (1/2);
[(s-dis)/2 (s+dis)/2] % display x and y as an r by 2 array, where r is the number of solutions.
I don't have a copy of MATLAB, so I cannot check whether this runs correctly, but it is a differently written algorithm than any of the others. I intentionally wrote it so that A, sn, and pn remain sparse arrays (I hope). — Arthur Rubin (talk) 07:20, 3 January 2016 (UTC)
Made some change. The program works fine now.
I think the solution given here is wrong.
editIf the product of the two numbers is 52, then P actually cannot deduce the two numbers from the knowledge of the basic limitations plus the fact that S knew from the sum alone that P could not deduce the two numbers. The program given in the article does not take into consideration the fact that S knows the product must be less than 100. If the numbers were 4 and 13, then P cannot deduce the two numbers from the product since 52=4x13 but also 52=2x26. S can deduce P's inability to determine the numbers from the sum 17, since all the ways of adding up to 17, when multiplied together, have an alternate product. Specifically:
Sum | Product | Alternate factors |
---|---|---|
2+15 | 30 | 3,10 |
3+14 | 42 | 6,7 |
4+13 | 52 | 2,26 |
5+12 | 60 | 6,10 |
6+11 | 66 | 2,33 |
7+10 | 70 | 5,14 |
8+9 | 72 | 3,24 |
However, this is also true of the other possible sum P would consider if the product is 52, namely 28. Recall that products over 100 are impossible! So if the sum is 28, the possible products are 52, 75, and 96, all of which have at least two ways of being expressed. (5x23=115 has a unique factorization, but 115 is too large.)
All the sums with this property are: 11 (products: 18, 24, 28, 30), 17 (products: 30, 42, 52, 60, 66, 70, 72), 23 (products: 42, 60, 76, 90), 27 (products: 50, 72, 92), 28 (products: 52, 75, 96), 29 (products: 54, 78), 35 (products: 66, 96), and 36 (products: 68, 99).
I believe the correct solution is that the numbers are 25 and 3. Given a product of 75, P knows the sum must be either 20 (5x15) or 28 (3x25). Only one of these numbers has the required property of sums so that S can conclude P cannot tell the two numbers from the product: 28. Thus, hearing this, P can deduce that the numbers are 3 and 25. But this could not be done with either of the other possible products with a sum of 28. The other possible products are 52 and 96; for 52, P would not be able to deduce the two numbers even knowing S's claim. For 96, similarly, both (3,32) and (4,24) have sums with the property.
This seems to be the unique answer, too. The products with exactly one factorization being in {11, 17, 23, 27, 29, 35, 36} are: 24 and 28 (with 11), 70 (with 17), 60 and 90 (with 23), 50 and 92 (with 27), 75 (with 28), 54 and 78 (with 29), none with 35, and 68 and 99 (with 36). So only 75=3x25 and 70=7x10 are possible for P to make the second statement. However, of these (7,10) is not actually possible because S would be unable to tell if the numbers are (5,12) or (7,10) since both have a unique factorization producing one of the correct sums.
Mangojuicetalk 06:10, 3 January 2016 (UTC)
- Haha, never mind. I see now I was looking for a version of the problem with the X*Y < 100 constraint rather than X+Y < 100. Mangojuicetalk 06:14, 3 January 2016 (UTC)
A small error
editThe article says "for the product B·C of such a 2-split to be unique (i.e. there are no other two numbers that also when multiplied yield the same result), both factors must be prime numbers". This is not true. One factor can also be a prime and the other the square or the cube of the same prime. Example: the product 27 has to be 3·9 and the product 81 has to be 3·27 (as 9·9 is excluded due to Y>X). Episcophagus (talk) 09:30, 7 May 2018 (UTC)
Tables
editWhich tables? Madyno (talk) 19:00, 26 July 2022 (UTC)