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 FalseREM If Not a * b < 140 Then Return FalseIf 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