tag:blogger.com,1999:blog-3722233.post116860230934986679..comments2020-05-25T04:05:03.716-04:00Comments on Computational Complexity: The Sum and Product RiddleLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-35967861882508253142007-08-10T16:27:00.000-04:002007-08-10T16:27:00.000-04:00Hi,If you define the numers to be between 1 and 10...Hi,<BR/><BR/>If you define the numers to be between 1 and 100 (not including 1)<BR/>then it doesn't matter if you limit of the sum. <BR/>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. <BR/><BR/>Here is the program (vb.net) to compute the two numbers: <BR/><BR/>--------------------------------<BR/>Imports system.Math<BR/><BR/>Module Module1<BR/><BR/> Const maximum As Integer = 100<BR/><BR/> Sub main()<BR/><BR/> Dim a, b<BR/><BR/> For b = 2 To maximum<BR/> For a = 2 To b 'Not need to go further the b as a,b=b,a<BR/> If condition_met(a, b) Then<BR/> If Not P_knows(a * b) Then<BR/> If S_knows_that(a + b) Then<BR/> If P_knows_now(a * b) Then<BR/> If S_knows_now(a + b) Then<BR/> MsgBox(Format(a) + ", " + Format(b))<BR/> End If : End If : End If : End If : End If<BR/> Next a, b<BR/><BR/> End Sub<BR/><BR/> Function condition_met(ByVal a, ByVal b)<BR/> If Not a < maximum Then Return False<BR/> If Not b < maximum Then Return False<BR/> <I>REM If Not a + b < 100 Then Return False</I><BR/> <I>REM If Not a * b < 140 Then Return False</I><BR/> If Not a = Int(a) Then Return False<BR/> If Not b = Int(b) Then Return False<BR/> Return True<BR/> End Function<BR/><BR/> Function P_knows(ByVal Product As Integer) As Boolean 'Does P know the numbers?<BR/><BR/> Dim t = 0, a, b<BR/><BR/> For a = 2 To Sqrt(Product) 'Sqr to exclude the same numbers (e.g. 8 = 2 * 4 and 4 * 2)<BR/> b = Product / a<BR/> If condition_met(a, b) Then t = t + 1 'P knows when there is only one combination <BR/> If t > 1 Then Return False 'no need to check futher<BR/> Next<BR/><BR/> Return t = 1<BR/><BR/> End Function<BR/><BR/> Function S_knows_that(ByVal Sum) As Boolean 'Does S know that P can't know the numbers?<BR/><BR/> Dim a, b<BR/><BR/> For a = 2 To Sum \ 2 '\ 2 to exclude the same numbers (e.g. 17 = 2 + 15 and 15 + 2)<BR/> b = Sum - a<BR/> 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 <BR/> Next a 'the combination otherwise S won't know that<BR/><BR/> Return True<BR/><BR/> End Function<BR/><BR/> Function P_knows_now(ByVal Product) As Boolean 'Does P know the two numbers after S knows that P can't know them?<BR/><BR/> Dim t = 0, a, b<BR/><BR/> For a = 2 To Sqrt(Product)<BR/> b = Product / a<BR/> 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<BR/> If t > 1 Then Return False 'no need to check futher<BR/> Next a<BR/><BR/> Return t = 1<BR/><BR/> End Function<BR/><BR/> Function S_knows_now(ByVal Sum) As Boolean 'Does S know the two numbers too after P knows them?<BR/><BR/> Dim t = 0, a, b<BR/><BR/> For a = 2 To Sum \ 2 'S can only say that if there is just one combination<BR/> b = Sum - a<BR/> If condition_met(a, b) Then If P_knows_now(a * (Sum - a)) Then t = t + 1<BR/> If t > 1 Then Return False<BR/> Next a<BR/><BR/> Return t = 1<BR/><BR/> End Function<BR/><BR/>End Module<BR/>-------------------------------<BR/><BR/>Play around with the 2 REMmed out statements in the condition_met function and you will see what happens.<BR/><BR/>btw. any idea if there are more solutions if the two integers provided are between 1 and 1000?...<BR/><BR/>-RonaldAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1168990369223143992007-01-16T18:32:00.000-05:002007-01-16T18:32:00.000-05:00Actually, Paul can figure out in the 3rd round tha...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.<BR/><BR/>Anonymous 7Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1168967093781957702007-01-16T12:04:00.000-05:002007-01-16T12:04:00.000-05:00I agree with anonymous #7. The way it's stated is ...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.<BR/><BR/>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).<BR/><BR/>YevgeniyZaumkahttps://www.blogger.com/profile/12342474039039410266noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1168733653618280852007-01-13T19:14:00.000-05:002007-01-13T19:14:00.000-05:00That's a cute problem.Some generalizations are als...That's a cute problem.<BR/>Some generalizations are also<BR/>discussed in the recent paper<BR/><BR/>THE FREUDENTHAL PROBLEM AND ITS RAMIFICATIONS (PART I), by<BR/>A. Born, C.A.J. Hurkens, and G.J. Woeginger,<BR/><BR/>appeared at EATCS Bulletin,<BR/>Number 90, October 2006.<BR/>I enjoyed reading it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1168720879906742432007-01-13T15:41:00.000-05:002007-01-13T15:41:00.000-05:00Most cases are much easier to eliminate than is im...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?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1168714663936818832007-01-13T13:57:00.000-05:002007-01-13T13:57:00.000-05:00In case anyone is interested in testing one's prog...In case anyone is interested in testing one's program for this: <A HREF="https://www.spoj.pl/problems/PLATON/" REL="nofollow" TITLE="This problem on the Sphere Online Judge">https://www.spoj.pl/problems/PLATON/</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1168704920821475522007-01-13T11:15:00.000-05:002007-01-13T11:15:00.000-05:00"Please do a web search before..."I "think" it's "..."Please do a web search before..."<BR/><BR/>I "think" it's "clear" he wasn't "trying" "to" say the "puzzle" was "original".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1168652667340379692007-01-12T20:44:00.000-05:002007-01-12T20:44:00.000-05:00Shahab: Given that Paul knows the product, there ...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. <BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1168649807184585872007-01-12T19:56:00.000-05:002007-01-12T19:56:00.000-05:00Although the web page that the first commentator r...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.<BR/>I wonder if there is any other solution which conforms does not refute the validity of the stated sentences.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1168641651874281232007-01-12T17:40:00.000-05:002007-01-12T17:40:00.000-05:00To anonymous 1:First, Lance is absolutely free to ...To anonymous 1:<BR/><BR/>First, Lance is absolutely free to post anything to *his* blog, and you<BR/>don't have to tell him what to post.<BR/><BR/>Second, while the website that you point us to does contain the answer, it is hardly an elegant solution. <BR/><BR/>If you think that this problem is a "triviality", why don't you post an elegant solution?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1168638433415041292007-01-12T16:47:00.000-05:002007-01-12T16:47:00.000-05:00http://www.puzzle.dse.nl/teasers/index_us.htmlPlea...http://www.puzzle.dse.nl/teasers/index_us.html<BR/><BR/>Please do a web search before posting such "trivialities" (as you "high brow" people call these things)Anonymousnoreply@blogger.com