Friday, January 12, 2007

The Sum and Product Riddle

A cute problem that I got off Steve Fenner's door that he got from FOM.

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.
What are the numbers?
Posted by at 5:44 AM

11 comments:

  1. http://www.puzzle.dse.nl/teasers/index_us.html

    Please do a web search before posting such "trivialities" (as you "high brow" people call these things)
    ReplyDelete
  2. To anonymous 1:

    First, 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?
    ReplyDelete
  3. 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.
    I wonder if there is any other solution which conforms does not refute the validity of the stated sentences.
    ReplyDelete
  4. 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.

    There 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.
    ReplyDelete
  5. "Please do a web search before..."

    I "think" it's "clear" he wasn't "trying" "to" say the "puzzle" was "original".
    ReplyDelete
  6. In case anyone is interested in testing one's program for this: https://www.spoj.pl/problems/PLATON/
    ReplyDelete
  7. Most 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?
    ReplyDelete
  8. That's a cute problem.
    Some 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.
    ReplyDelete
  9. 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.

    When 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
    ReplyDelete
  10. 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.

    Anonymous 7
    ReplyDelete
  11. Hi,

    If 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
    ReplyDelete

Subscribe to: Post Comments (Atom)