tag:blogger.com,1999:blog-3722233.post258179996142064411..comments2020-07-09T17:10:19.118-04:00Comments on Computational Complexity: Is this problem too hard for a HS Math CompetitionLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger51125tag:blogger.com,1999:blog-3722233.post-22949997631784869462012-05-29T09:33:51.061-04:002012-05-29T09:33:51.061-04:00I am here to discuss about a simple topic in mathe...I am here to discuss about a simple topic in mathematics that is rational expression,Rational expressions is known as an expression that is the ratio of two polynomials.It is called as rational because one number is divided by the other that is like a ratio.<br /><a href="http://calculator.tutorvista.com/math/610/quadratic-formula-calculator.html" rel="nofollow">quadratic formula calculator</a>ankyhttps://www.blogger.com/profile/07652186909824449601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53341059585628224452012-04-11T18:20:58.324-04:002012-04-11T18:20:58.324-04:00It is not a solution. The condition 1 = 1/x1+...+1...It is not a solution. The condition 1 = 1/x1+...+1/x10 does'n holdTodor Bonchevhttps://www.blogger.com/profile/07333812201493175069noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34414717547425425382011-12-16T08:28:38.821-05:002011-12-16T08:28:38.821-05:00That's a few last solutions found by my progra...That's a few last solutions found by my program, which I wasn't patient enough to post in the previous post. I really enjoyed solving this problem.<br /><br />[1760, 2, 5, 11, 11, 40, 40, 32, 55, 55]<br />[1800, 2, 6, 12, 18, 20, 20, 40, 18, 75]<br />[1820, 2, 10, 14, 26, 26, 28, 65, 10, 10]<br />[1840, 4, 5, 8, 8, 10, 10, 23, 23, 80]<br />[1848, 4, 7, 8, 11, 22, 84, 9, 9, 9]<br />[1872, 3, 8, 8, 8, 13, 13, 16, 18, 52]<br /><br />Surprisingly, it didn't found the [1870,...] solution posted by Anonymous above, so it seems there are much more solutions to the problem.Иван Волосюкhttps://www.blogger.com/profile/10920361793240753883noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41694650415075111472011-12-16T08:01:50.150-05:002011-12-16T08:01:50.150-05:00Will I get extra points if I found more than 10 so...Will I get extra points if I found more than 10 solutions for the problem?<br /><br />[704, 4, 4, 4, 8, 704, 352, 176, 44, 11]<br />[864, 3, 6, 8, 8, 8, 16, 18, 864, 216]<br />[912, 3, 4, 4, 19, 24, 912, 57, 38, 38]<br />[920, 10, 5, 10, 23, 23, 920, 92, 4, 4]<br />[1080, 4, 4, 6, 9, 12, 12, 20, 432, 432]<br />[1188, 3, 4, 6, 9, 9, 297, 297, 99, 99]<br />[1232, 2, 7, 11, 14, 14, 16, 22, 616, 77]<br />[1260, 2, 6, 12, 21, 630, 20, 20, 20, 20]<br />[1440, 3, 5, 8, 12, 18, 480, 15, 15, 15]<br />[1500, 6, 10, 10, 10, 10, 12, 375, 75, 3]<br />[1560, 3, 6, 10, 10, 10, 10, 12, 312, 78]<br />[1584, 2, 4, 24, 33, 36, 16, 264, 24, 24]<br />[1680, 2, 4, 14, 14, 35, 35, 35, 96, 96]<br />[1700, 2, 5, 10, 10, 34, 100, 50, 50, 50]<br /><br /><br />I have virtually zero knowledge in the area and I don't know any theorems which can help me in this case. So, I have written a python program which tries to solve the problem with the starting number in 2.2000 range. Than, I subtract 1/n where n is one of divisors of the initial number with some extra magic.<br /> <br />I wasted a working day trying to find the right approach for the problem. That's my third one and it worked. I can send the source code if you interested: vol at google.comИван Волосюкhttps://www.blogger.com/profile/10920361793240753883noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56774735656615510792011-12-16T07:27:36.237-05:002011-12-16T07:27:36.237-05:00I have found another solution. I killed one work d...I have found another solution. I killed one work day programming this problem, most of the time I was moving in wrong direction:<br />[704, 4, 4, 4, 8, 704, 352, 176, 44, 11]Иван Волосюкhttps://www.blogger.com/profile/10920361793240753883noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69176429613366956622011-12-14T08:49:18.841-05:002011-12-14T08:49:18.841-05:00If it is allowed to use electronic devices, then t...If it is allowed to use electronic devices, then the problem is very easy:<br />2+10+11+17+17+20+20+22+22+1870 = 2011,<br />1/2+1/10+1/11+1/17+1/17+1/20+1/20+1/22+1/22+1/1870 = 1.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62882122903361633752011-12-13T22:49:08.169-05:002011-12-13T22:49:08.169-05:00In the second equation,
(x_1)*(x_2)*(x_3)*...*(x_9...In the second equation,<br />(x_1)*(x_2)*(x_3)*...*(x_9) + (x_2)*(x_3)*...*(x_10) + ... = (x_1)*(x_2)*(x_3)*...*(x_10),<br />RHS divides x_1, so in LHS (x_2)*(x_3)*..*(x_10) must divide x_1 ( and same for the rest of the terms ). If x_1 is a prime, then there should be an x_2 that divides x_1. RHS divides x_1*x_2, so in LHS, (x_3*x_4*x_5*...*x_10)(x_1 + bla*x_2) must divide (x_1)^2, which means one of x_3, x_4 etc must divide x_1, and so on. Primes have to proliferate. If x_1 is not a prime, then the same applies to it's prime factors. <br />So, x_i are either primes themselves, or they are multiples of product of all prime factors of all x_i. ( Not entirely true, for ex. 3, 4, 12, 12, 12, 12, 12 is possible...4 is not a prime, but enough for the argument )<br /><br />Applying...<br />If 2 is the only prime, then in the binary-expansion it doesn't fit. Only 3 obviously doesn't work as 2011 is quite close to twice 2^10. <br />If both 2 and 3 have to exist, then as Anon pointed out 2297 happens : 2 + 3 + ( can't have 6 ) + 12 + (can't have another 12 ) + ...<br />If both 2 and 5 have to exist, then you'll only get numbers ending in 10.<br />In case of 3 and 4, you'll get (1/3) + (1/4) which makes 7/12 leaving 5/12 for the rest, but minimum is 12 for the remaining numbers, and 5 12s only go to 60. Similar issues with (2,7), (3,5), (3,7), and the higher you go ( for the initial numbers ), the more trouble you'll have adding up the inverses to 1. <br /><br />Not a nice argument, doing it case-by-case, but any errors?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6074686451412912072011-12-13T17:37:26.067-05:002011-12-13T17:37:26.067-05:00A couple hours of programming and a some computing...A couple hours of programming and a some computing yielded an answer to the question. Doesnt mean I could do it during an exam. Wont spoil it before Wed by saying what the answer is.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78193496429057668742011-12-13T08:19:37.835-05:002011-12-13T08:19:37.835-05:00Dear Anon who send me correct solution which I blo...Dear Anon who send me correct solution which I blocked (to allow others to not be spoiled):<br />I will include your solution (which is different<br />from mine and my HS students and someone else who emailed me) in what I post on WED. If you email me your name and proof that you are you (e.g., the<br />solution) then I will include your name.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75994615221812352642011-12-13T08:15:29.796-05:002011-12-13T08:15:29.796-05:00Anon two back: sqrt(208...) is not rational,
so no...Anon two back: sqrt(208...) is not rational,<br />so not a solution.<br /><br />domotorp- I have added to the post a POINTER<br />to the answer to just the question of IS there<br />a solution or not. So you can click on that,<br />but people do not have to if they want to keep working on it without knowing.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51405061324184523662011-12-13T04:52:48.217-05:002011-12-13T04:52:48.217-05:00Solution can wait till WED, but could you tell us ...Solution can wait till WED, but could you tell us the answer? I think many of us worked a lot on the problem and we deserve it...<br /><br />What I really enjoy is that I still have no clue whether the statement is true or false... I think the nicest would be an existential argument for the existence of a solution without finding one. Is this the case?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8318268932803780382011-12-13T04:29:55.779-05:002011-12-13T04:29:55.779-05:00The answer by one of the last anons is pretty corr...The answer by one of the last anons is pretty correct to me :<br /><br /> x1 -> (1370685 -<br /> 3 sqrt[208548352065])/1370,<br /> x2 -> 6, x3 -> 10, x4 -> 15, x5 -> 6,<br /> x6 -> -3, x7 -> -7, x8 -> -16, x9 -> -1,<br /> x10 -> 2001 + (-1370685 + 3 sqrt[208548352065])/1370<br /><br />this constitutes a proof by explicit construction. voila!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83891494526280945812011-12-13T02:37:31.041-05:002011-12-13T02:37:31.041-05:00If x is represented by k numbers, than 2x+8 and 2x...If x is represented by k numbers, than 2x+8 and 2x+9 are represented by k+2 numbers. If x is represented by k numbers than 3x+8 and 3x+6 are representable by k+2 numbers. Such is a number of reductions. From 1= 1/4+1/4+1/4+1/4 and 1=1/2+1/4+1/6+1/12, we get that if x is representable by k numbers than 4x+12 and 4x+20 are representable by k+3 numbers. <br /><br />Now let us try use these reductions on 2011. 2011=2*1001+9<br />1001=3*331+8<br />331= 2*161+9<br />161= 3*51 +8<br />51 is divisible by 3, so we can apply either of the two reductions.<br />51=2*21+9<br />or<br />51=3*15+6<br />Now we are a bit stuck, but this method can help.<br />For instance if we can do 331 in 6 moves or 1001 in 8 moves we are done.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45636668653932282772011-12-12T23:24:50.770-05:002011-12-12T23:24:50.770-05:00> This raises a good question- how much does AV...> This raises a good question- how much does AVG(x_1,...,x_n)<br />> and 1/AVG(1/x_1,...,1/x_n)) differ? I think they can differ by a lot.<br /><br />Yes. There is one constraint on their relationship, which is that if all the x_i are positive, their harmonic mean cannot exceed their arithmetic mean. It follows that the product of the two series is at least n^2. (For a nice proof, see Proofs from the Book. Their proof uses the Cauchy-Schwarz inequality.)<br /><br />So if you were to replace 2011 with 199 in your question, it would be impossible even for real numbers.Jonathan Shewchukhttp://www.cs.berkeley.edu/~jrs/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47103163117349345212011-12-12T22:17:00.333-05:002011-12-12T22:17:00.333-05:00I think you mean `no more suspense''
Anyw...I think you mean `no more suspense''<br /><br />Anyway, on WED I will post three solutions<br />(the one I intended, the one a BRIGHT HS<br />student emailed me, and one that a reader<br />emailed me). I may post more if more people<br />send them to me. <br /><br />Problems worth of attack prove their worth by hitting back (Piet Hein quote)GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65028450191545323742011-12-12T22:13:37.909-05:002011-12-12T22:13:37.909-05:00ok no more dispense here ... Bill plz post solutio...ok no more dispense here ... Bill plz post solution!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85158581386373379272011-12-12T22:04:32.337-05:002011-12-12T22:04:32.337-05:00It would seem a good approach is to figure out whi...It would seem a good approach is to figure out which theorem was used to construct the problem. <br /><br />An obvious candidate is the Arithmetic-Geometric Mean Inequality but in this case (as I understand it) it only tells us Harmonic mean =< Geometric Mean =< Arithmetic Mean, and since Harmonic Mean = 10 and Arithmetic Mean = 201.1 this is not very useful.<br /><br />So there must be a stronger inequality that was used probably one that involves the Harmonic Mean, the Arithmetic Mean and maybe integrality conditions.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73754788705629244602011-12-12T19:22:49.973-05:002011-12-12T19:22:49.973-05:00x1 -> (1370685 -
3 sqrt[208548352065])/1370,...x1 -> (1370685 - <br /> 3 sqrt[208548352065])/1370,<br /> x2 -> 6, x3 -> 10, x4 -> 15, x5 -> 6, <br />x6 -> -3, x7 -> -7, x8 -> -16, x9 -> -1,<br /> x10 -> 2001 + (-1370685 + 3 sqrt[208548352065])/1370Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8872959832604848232011-12-12T19:12:09.011-05:002011-12-12T19:12:09.011-05:00The theorem must be something like - every odd num...The theorem must be something like - every odd number greater than X can be represented with Y elements, say every number greater than 1000 can be represented by 10 or so entries. We already have 2009, 2007 - so it seems that all numbers are representable like this, if sufficiently large. There is some freedom in choices but it seems that you "built" your problem around some theorem of this sort. <br /><br />The proof possibly goes by induction, building from a pool of numbers that are all representable. Also, possibly, you perhaps need C+log (n) entries to rerpresent each number of size <n, starting with some number. <br /><br />We can see heuristics, there are exponentially many representations of 1 as sum of k reciprocials (exponential in k), so that largest number does not rise more than exponentially; then by some sort of covering we can get all representations.<br /><br />But this is not a fair problem for HS. They have to guess representation, which is NP problem (in number of digits, that is, in log (n)). Probably the simplest way to check this is brute force search with some simple optimizations, so it is not particulary enlightening as a HS problem.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41901319640023731932011-12-12T19:00:35.533-05:002011-12-12T19:00:35.533-05:0060sdieting- an earlier comment noted that the prie...60sdieting- an earlier comment noted that the prie<br />2297 CAN be written as the sum of numbers whose<br />recips add up to 1. So your train of thought cannot work. (It would be enlightening for you to<br />do the argument and see where it breaks down.<br />I learn LOTS from failed proofs.)GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82160385275796375742011-12-12T18:58:43.424-05:002011-12-12T18:58:43.424-05:00Anon- ALAS, if only I had though of the problem in...Anon- ALAS, if only I had though of the problem in 2009 instead of 2011, then you would have gotten it right!GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6886713015601594262011-12-12T18:52:53.126-05:002011-12-12T18:52:53.126-05:002009=2+9+9+9+24+27+27+27+75+18002009=2+9+9+9+24+27+27+27+75+1800Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68948966905970702832011-12-12T18:52:20.252-05:002011-12-12T18:52:20.252-05:002011 is a prime. Do the standard algorithm for fra...2011 is a prime. Do the standard algorithm for fractions and you get 2011 over a composite. Can't be one.60sDietinghttps://www.blogger.com/profile/12555932773844102797noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34053947224103162272011-12-12T18:02:05.617-05:002011-12-12T18:02:05.617-05:00Anon with 7 instead of 10- interesting, but
not th...Anon with 7 instead of 10- interesting, but<br />not the answer to the question we are asking.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78594131569788573292011-12-12T17:59:50.683-05:002011-12-12T17:59:50.683-05:00solution found with 7 instead of 10 elements
2+3+...solution found with 7 instead of 10 elements<br /><br />2+3+14+14+86+86+1806=2011Anonymousnoreply@blogger.com