Let x and y be two integers with 1<x<y and x+y≤100. Sally is given only their sum x+y and Paul is given only their product xy. Sally and Paul are honest and all this is commonly known to both of them.
The following conversation now takes place:
- Paul: I do not know the two numbers.
- Sally: I knew that already.
- Paul: Now I know the two numbers.
- Sally: Now I know them also.
http://www.puzzle.dse.nl/teasers/index_us.html
ReplyDeletePlease do a web search before posting such "trivialities" (as you "high brow" people call these things)
To anonymous 1:
ReplyDeleteFirst, Lance is absolutely free to post anything to *his* blog, and you
don't have to tell him what to post.
Second, while the website that you point us to does contain the answer, it is hardly an elegant solution.
If you think that this problem is a "triviality", why don't you post an elegant solution?
Although the web page that the first commentator refers to includes a solution, the stated solution does not conform to the honesty of those Paul and Sally. As, following this solution, Paul, in the third step of conversation, couldn't have said that he knows the two numbers as he could have had so many options based on that solution.
ReplyDeleteI wonder if there is any other solution which conforms does not refute the validity of the stated sentences.
Shahab: Given that Paul knows the product, there is only split of the product of the numbers given that produces a sum that could be on Sally's list.
ReplyDeleteThere is a nice characterization of numbers after the 1st two rounds but the case analysis on the website posted is easily seen to be overkill.
"Please do a web search before..."
ReplyDeleteI "think" it's "clear" he wasn't "trying" "to" say the "puzzle" was "original".
In case anyone is interested in testing one's program for this: https://www.spoj.pl/problems/PLATON/
ReplyDeleteMost cases are much easier to eliminate than is implied by the solution. The only tricky cases: Why can't x+y=29, 41, or 55?
ReplyDeleteThat's a cute problem.
ReplyDeleteSome generalizations are also
discussed in the recent paper
THE FREUDENTHAL PROBLEM AND ITS RAMIFICATIONS (PART I), by
A. Born, C.A.J. Hurkens, and G.J. Woeginger,
appeared at EATCS Bulletin,
Number 90, October 2006.
I enjoyed reading it.
I agree with anonymous #7. The way it's stated is not unique. Say x=13, y=16, sum is 29. 29-2, 29-4, 29-8 are all composite, so this is a possibility.
ReplyDeleteWhen I give this puzzle, I usually say x+y<100, and xy<140. This rules out 13*16=208, and now indeed leaves 13 and 4 as only solutions (other larger sums like 41=37+4 also give larger products).
Yevgeniy
Actually, Paul can figure out in the 3rd round that with 54 the factorization must be 2*27 even though 27 is composite. The reason is that 6 * 9 and 18 * 3 both lead to sums of 15 and 21 that are 2+p for prime p which he can rule out after Sally's answer. Therefore with the sum of 29 Sally doesn't know if this came as 2+27 or 13+16.
ReplyDeleteAnonymous 7
Hi,
ReplyDeleteIf you define the numers to be between 1 and 100 (not including 1)
then it doesn't matter if you limit of the sum.
But if you limit the product you are messing up the riddle as by rulling out posibilities for one statement you increase them for another. In fact, if you limit the product to 140, 4 and 13 is not anymore the only solution but also 4 and 19, 2-25, 2-27, 3-35, etc.
Here is the program (vb.net) to compute the two numbers:
--------------------------------
Imports system.Math
Module Module1
Const maximum As Integer = 100
Sub main()
Dim a, b
For b = 2 To maximum
For a = 2 To b 'Not need to go further the b as a,b=b,a
If condition_met(a, b) Then
If Not P_knows(a * b) Then
If S_knows_that(a + b) Then
If P_knows_now(a * b) Then
If S_knows_now(a + b) Then
MsgBox(Format(a) + ", " + Format(b))
End If : End If : End If : End If : End If
Next a, b
End Sub
Function condition_met(ByVal a, ByVal b)
If Not a < maximum Then Return False
If Not b < maximum Then Return False
REM If Not a + b < 100 Then Return False
REM If Not a * b < 140 Then Return False
If Not a = Int(a) Then Return False
If Not b = Int(b) Then Return False
Return True
End Function
Function P_knows(ByVal Product As Integer) As Boolean 'Does P know the numbers?
Dim t = 0, a, b
For a = 2 To Sqrt(Product) 'Sqr to exclude the same numbers (e.g. 8 = 2 * 4 and 4 * 2)
b = Product / a
If condition_met(a, b) Then t = t + 1 'P knows when there is only one combination
If t > 1 Then Return False 'no need to check futher
Next
Return t = 1
End Function
Function S_knows_that(ByVal Sum) As Boolean 'Does S know that P can't know the numbers?
Dim a, b
For a = 2 To Sum \ 2 '\ 2 to exclude the same numbers (e.g. 17 = 2 + 15 and 15 + 2)
b = Sum - a
If condition_met(a, b) Then If P_knows(a * b) Then Return False 'for all the possible sums P should not be able to know
Next a 'the combination otherwise S won't know that
Return True
End Function
Function P_knows_now(ByVal Product) As Boolean 'Does P know the two numbers after S knows that P can't know them?
Dim t = 0, a, b
For a = 2 To Sqrt(Product)
b = Product / a
If condition_met(a, b) Then If S_knows_that(a + b) Then t = t + 1 'P can only say that if there is just one combination
If t > 1 Then Return False 'no need to check futher
Next a
Return t = 1
End Function
Function S_knows_now(ByVal Sum) As Boolean 'Does S know the two numbers too after P knows them?
Dim t = 0, a, b
For a = 2 To Sum \ 2 'S can only say that if there is just one combination
b = Sum - a
If condition_met(a, b) Then If P_knows_now(a * (Sum - a)) Then t = t + 1
If t > 1 Then Return False
Next a
Return t = 1
End Function
End Module
-------------------------------
Play around with the 2 REMmed out statements in the condition_met function and you will see what happens.
btw. any idea if there are more solutions if the two integers provided are between 1 and 1000?...
-Ronald