tag:blogger.com,1999:blog-3722233.post1022174979072899610..comments2024-03-03T22:21:38.304-06:00Comments on Computational Complexity: A nice problem from a Romanian Math Problem BookLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-51956817949203329202015-01-31T13:03:17.582-06:002015-01-31T13:03:17.582-06:00YES, I would be interested in your solution to see...YES, I would be interested in your solution to see how it differs from mine (which is linked to). It sounds like you are doing a greedy solution which I don't think works.<br />IGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46318214362760867712015-01-30T17:28:46.772-06:002015-01-30T17:28:46.772-06:00I have solved it for n = 6 and I should be able to...I have solved it for n = 6 and I should be able to generalize for the others using the same thing. Basically start by checking for the largest part. assume there is no ai =2 then the max sum for 6 terms in 6/9 . so there must be a ai=2 and so on and so forth... Ok to post the outline so far here? :)Anonymoushttps://www.blogger.com/profile/12027683044768177322noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57613524307015058422015-01-30T15:20:05.301-06:002015-01-30T15:20:05.301-06:00(This is bill but for stupid tech reasons I need t...(This is bill but for stupid tech reasons I need to do this anon)<br />The ai's NEED NOT be distinct.<br />For example, for n=4 we COULD use (2,2,2,2) since 1/4+1/4+1/4+1/4=1.<br /><br />bill g.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3728590084989446742015-01-30T15:02:54.367-06:002015-01-30T15:02:54.367-06:00ai 's are distinct?ai 's are distinct?Anonymoushttps://www.blogger.com/profile/12027683044768177322noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50628777653446183662015-01-28T14:06:22.871-06:002015-01-28T14:06:22.871-06:00I like this problem a lot, and I'm assigning i...I like this problem a lot, and I'm assigning it in both Formal Language Theory (Sipser<br />book) and Discrete Math this semester.DaveMBhttps://www.blogger.com/profile/00779581893863396042noreply@blogger.com