tag:blogger.com,1999:blog-3722233.post4627102744392926965..comments2024-03-29T08:55:55.727-05:00Comments on Computational Complexity: More funny answers on math olympiadLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-3722233.post-68491035981283715622011-10-24T17:07:47.509-05:002011-10-24T17:07:47.509-05:00[a_(n+1); b_(n+1)]=[sqrt(3) -1;1 sqrt(3)]*[a_n ; b...[a_(n+1); b_(n+1)]=[sqrt(3) -1;1 sqrt(3)]*[a_n ; b_n]<br />Solve for [a_n ; b_n]=inv[sqrt(3) -1 ; 1 sqrt(3)]*[a_(n+1);b_(n+1)]<br />[a_99;b_99]=inv[sqrt(3) -1 ; 1 sqrt(3)]*[a_100;b_100]<br />[a_98;b_98]=(inv[sqrt(3) -1 ; 1 sqrt(3)])^2*[a_100; b_100]<br />[a_1;b_1]=(inv[sqrt(3) -1 ; 1 sqrt(3)])^99*[a_100; b_100]<br />[a_1;b_1]=(1/2^100)*[0 2;-2 0]*[2; 4]=[1/2^97 ; -1/2^98]<br />Therefore a_1+b_1=1/2^97-1/2^98=1/2^98Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58796020257846284492011-04-05T16:02:53.770-05:002011-04-05T16:02:53.770-05:00If the n choices provided are either
1) not mutual...If the n choices provided are either<br />1) not mutually exclusive, or<br />2) not exhaustive<br />then it is not possible to prove either choice is correct or incorrect.<br />In the case of 1) multiple choices will apply unless there is another qualifier.<br />In the case of 2) [which is the case in this question] the missing choices may be correct.<br />It is not possible show that either of these two statements is correct or incorrect.<br /><br />Poor questions must result in poor answers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82756409082909825632008-06-04T12:00:00.000-05:002008-06-04T12:00:00.000-05:00you need to know how many colours are avalable fir...you need to know how many colours are avalable first.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24308859755191814792008-02-29T09:39:00.000-06:002008-02-29T09:39:00.000-06:00If you interpret "are the same color" as either "l...If you interpret "are the same color" as either "look the same color" or "are within a given tolerance of each other", then the relation becomes intransitive (i.e. if A and B are the same color, and so are B and C, then A and C are not necessarily the same color). So then the given statement becomes: any graph on n nodes has either a clique or an independent set of size sqrt(n). Is this true, by the way?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3217168753329300792008-02-22T19:17:00.000-06:002008-02-22T19:17:00.000-06:00Is it still provable in intuitionistic logic? "At ...Is it still provable in intuitionistic logic? "At least one of these statements is true" suggests intuitionistic disjunction to my mind.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1081455955991785912008-02-22T15:27:00.000-06:002008-02-22T15:27:00.000-06:00There's no way either is serious. Both are despera...There's no way either is serious. Both are desperate attempts at humor. Neither uses math, just extraneous real world 'facts'.Mitchhttps://www.blogger.com/profile/06352106235527027461noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84729031670792919842008-02-21T09:13:00.000-06:002008-02-21T09:13:00.000-06:00Anonymous #1, that's a cute problem and I did get ...Anonymous #1, that's a cute problem and I did get it in five minutes -- if I haven't screwed up the arithmetic the answer is a_1 = -2^{-98} and b_1 = 2^{-99}, so a total of -2^{-99}.<BR/> <BR/>I suppose if you don't see the trick, you could get to the right answer by cranking through three steps of the recurrence, _if_ you don't mess up all the sqrt{3}'s.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55329562444486446972008-02-20T14:22:00.000-06:002008-02-20T14:22:00.000-06:00Sorry pal, you must admit that this is not a math ...Sorry pal, you must admit that this is not a math problem. It is a ill defined problem, there must be better specified scientific wariables, like what shop, how many colours out of the pantone scale are different (20 000 ?!), wether it is the can or not. <BR/><BR/>Say I was a 6 y old genius who has been with my father only to the wood pile shop. There is only linoleum there and certainly not even 45 brands (less than 45 outside colours) and the inside colour is - colourless - is that a colour? House colours are in so many nuances so they are ordered from a catalouge and arrive later.<BR/>So my answer could be zero as well!<BR/><BR/>OR, I certainly could prove at least 45 nuances/hues by comparing by the pantone scale, even if they are the same colour all, except if they are linoleum all.<BR/><BR/>You can really spoil a career for a genious!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88972681607663327352008-02-20T08:40:00.000-06:002008-02-20T08:40:00.000-06:00The first one is a joke. Or, at least, I would hav...The first one is a joke. Or, at least, <B>I</B> would have been <I>very</I> tempted to write that down as a joke.rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86476694526550238292008-02-20T05:30:00.000-06:002008-02-20T05:30:00.000-06:00Then: ``2. There are at least 45 cans of all diffe...Then: ``2. There are at least 45 cans of all different colors.''Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15962421920284834952008-02-20T04:06:00.000-06:002008-02-20T04:06:00.000-06:00I don't see how you can answer the question withou...I don't see how you can answer the question without the number of colors available... Why could you not have 2000 different colors?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39580754515524317382008-02-19T23:05:00.000-06:002008-02-19T23:05:00.000-06:00Further, tough questions should be given as proof ...<I>Further, tough questions should be given as proof so that partial credit can be awarded to students with an approach, or idea.</I><BR/><BR/>Why do you care about giving partial credit?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52816057204261247842008-02-19T22:55:00.000-06:002008-02-19T22:55:00.000-06:00The difference between multiple choice type questi...The difference between multiple choice type questions and proof type questions is the depth of the material.<BR/><BR/>Traditionally, multiple choice questions are small nuggets which do not require very deep thought, but one needs to be fast. There is no point writing down proofs as they are very short anyway.<BR/><BR/>Proof-type questions test depth in understanding and perseverance of the student. Further, tough questions should be given as proof so that partial credit can be awarded to students with an approach, or idea.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29022939496921081832008-02-19T21:00:00.000-06:002008-02-19T21:00:00.000-06:00It could be that both of them were serious. In my ...It could be that both of them were serious. In my high school there were people who wrote these type of answers in exams and they were serious. Just because you are way too intelligent doesnt bring any right to you to mock at these students. Anyone can mock at you as well in certain circumstances.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48231666668376060462008-02-19T20:58:00.000-06:002008-02-19T20:58:00.000-06:00I know I was much better at the multiple choice se...<I>I know I was much better at the multiple choice sections of math contests in high school than at proofs.</I><BR/><BR/>What do you mean by this? Were your proofs correct (at least in your head) but not well written?<BR/><BR/>I think what matters most of all here is insight -- not well written proofs.<BR/><BR/>Getting difficult multiple choice questions correct is an indication that the student understands the major steps in a well written proof.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52015308320983510142008-02-19T19:51:00.000-06:002008-02-19T19:51:00.000-06:00I'm not so sure they will develop good proving ski...I'm not so sure they will develop good proving skills later in university or that you can make that assumption from the multiple choice. I know I was much better at the multiple choice sections of math contests in high school than at proofs. Also, it probably depends on the school and major as to whether they will develop any proving skills at all.Jason M. Adamshttps://www.blogger.com/profile/14396075067541286700noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31307428733531193362008-02-19T14:56:00.000-06:002008-02-19T14:56:00.000-06:00What's the point of requiring proofs in these cont...What's the point of requiring proofs in these contests?<BR/><BR/>If a high school student is good enough to solve difficult multiple choice questions, doesn't it follow that his/her proof skills would probably be pretty good -- or at least easily developed later in university?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38225576046095542752008-02-19T13:49:00.000-06:002008-02-19T13:49:00.000-06:00In an exam, ones mind becomes foggy to see the obv...In an exam, ones mind becomes foggy to see the obvious such as (44)^2 < 2000<BR/>Any tinge of sarcasm is injurious to young minds (IMHO) <BR/>Please look at this years AMC 12 last question and see whether the readers of this blog can solve it in less than 5 minutes. a_{n+1} = \sqrt(3) * a_n - b_n and b_{n+1} = \sqrt(3) * b_n + a_n. Given that (a_{100},b_{100})=(2,4), find a_1+b_1Anonymousnoreply@blogger.com