tag:blogger.com,1999:blog-3722233.post115858553313714360..comments2020-10-22T06:46:11.232-05:00Comments on Computational Complexity: Back to School NightLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger26125tag:blogger.com,1999:blog-3722233.post-1158973057096257922006-09-22T19:57:00.000-05:002006-09-22T19:57:00.000-05:00anonymous#11, here's a hint, notice that the pairs...anonymous#11, here's a hint, notice that the pairs of 2, 3 through 7 all cancel each other (think of 7!/8!).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158642956077178032006-09-19T00:15:00.000-05:002006-09-19T00:15:00.000-05:00This comment has been removed by a blog administrator.Cheshire Cathttps://www.blogger.com/profile/07463645065346922684noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158645528766937172006-09-19T00:58:00.000-05:002006-09-19T00:58:00.000-05:00Anonymous of Comment 23, why would you want to rem...<I>Anonymous of Comment 23, why would you want to remain anonymous when all you're doing is making an intriguing book recommendation?</I><BR/><BR/>Some people are not so obsessed by notoriety that need credit for a book recommendation.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158640183212504192006-09-18T23:29:00.000-05:002006-09-18T23:29:00.000-05:00There is a fun mystery novel about this very parad...There is a fun mystery novel about this very paradox called "The Oxford Murders". It is written by a mathematician and does a good job of integrating mathematics into the plot. (Other aspects of the novel cannot be as highly acclaimed.) If you are interested, it is a fun, fast, and short read.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158634113430286102006-09-18T21:48:00.000-05:002006-09-18T21:48:00.000-05:00The first question: 1/8The second question: it all...The first question: 1/8<BR/>The second question: it all depends on how you look at it.<BR/> For example:<BR/> 1. T(wo) F(our) S(ix) E(ight)<BR/> answer= T, T, F<BR/> 2. T _ S _ R_ Q; F_ E_ D<BR/> answer=R,D,QAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158633424921656732006-09-18T21:37:00.000-05:002006-09-18T21:37:00.000-05:00Four people, with me.I just got the book"Puzzles 1...Four people, with me.<BR/><BR/>I just got the book<BR/>"Puzzles 101" by Nobuyuki Yoshigahara for puzzles at the middle school level. <BR/><BR/>Here's a silly puzzle in the same category as Lance's son's teacher's:<BR/>"2,4,6,30, 32,34,36, 40, 42, 44, 46, 50, 52, 54, 56, 60, 62, 64, 66, ?"Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158622609355218062006-09-18T18:36:00.000-05:002006-09-18T18:36:00.000-05:00I saw RDQ as well, which makes at least three peop...I saw RDQ as well, which makes at least three people who saw it that way.<BR/><BR/>When looking for an acronym I saw True False South East, which leads to North West and then I don't know what.<BR/><BR/>All of which adds to the question 'what on earth does this have to do with math?'Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158620968864219982006-09-18T18:09:00.000-05:002006-09-18T18:09:00.000-05:00Heck, I did not spot the pattern and had to transl...<I>Heck, I did not spot the pattern and had to translate letters by their rank in the alphabet (20,6,19,5), "guess" the next number (18) and translate it back in a letter (I leave it to you). And latin is my native alphabet!</I><BR/><BR/>This is by far my favorite answer--clearly the sequence T F S E is just 20,6,19,5 whose next three members are 18,4,17 i.e. R D Q!<BR/><BR/>Should those of us who saw the "obvious" answer of "two four six eight" feel like conformists lacking even a smidgeon of creativity?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158619991525132782006-09-18T17:53:00.000-05:002006-09-18T17:53:00.000-05:00# 1/2 × 2/3 × 3/4 × 4/5 × 5/6 × 6/7 × 7/8 Let's se...# 1/2 × 2/3 × 3/4 × 4/5 × 5/6 × 6/7 × 7/8 <BR/><BR/>Let's see now, 1/2 x 2/3 is 2/6. 2/6 x 3/4 is is 6/24...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158619459581337822006-09-18T17:44:00.000-05:002006-09-18T17:44:00.000-05:00I claim the previous comment on not welldefined al...I claim the previous comment on not welldefined algorithmic simplicity. Beware of previews! (And I didn't catch the unlinked links anyway.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158619237524984112006-09-18T17:40:00.000-05:002006-09-18T17:40:00.000-05:00On problems type 2, isn't the problem that one can...On problems type 2, isn't the problem that one can't welldefine the simplest algorithm producing a certain string?<BR/><BR/>"This is a result of some work done by Greg Chaitin in Algorithmic Complexity Theory. A fairly nifty version of this can be found on Greg's page. ( http://www.cs.auckland.ac.nz/CDMTCS/chaitin/rov.html ) <BR/><BR/>The fundamental result is: given a system S, you cannot in general show that there is no smaller/simpler system that performs the same task as S." ( http://scienceblogs.com/goodmath/2006/06/the_problem_with_irreducibly_c_1.php ) <BR/><BR/>Here the task is to produce valid strings in a computing system phi. If the simplest algorithm producing strings isn't welldefined it seems to me a continuation should be less welldefined too.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158616563067242092006-09-18T16:56:00.000-05:002006-09-18T16:56:00.000-05:00The fact that a simple "complete the sequence" puz...The fact that a simple "complete the sequence" puzzle has generated so much discussion is amusing. Don't you guys have any papers to work on?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158605332188200752006-09-18T13:48:00.000-05:002006-09-18T13:48:00.000-05:00I was playing a board game called Amun Re with fri...I was playing a board game called Amun Re with friends of mine. In the game, the cost to buy certain resources is triangle numbers, but it only shows the first 7 on the chart, because beyond that is very rarely useful. So I explained you could buy beyond what the chart showed following the obvious pattern. One of my wiseass friends commented that anything could follow. To which I responded to just fit the lowest degree polynomial he could to the given points and use that. :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158600006908308342006-09-18T12:20:00.000-05:002006-09-18T12:20:00.000-05:00Obviously the desired answer to the second problem...<I> Obviously the desired answer to the second problem is the one of minimal Kolmogorov complxity.</I><BR/><BR/>It's a shame Kolmogorov complexity is only uniquely defined to within an additive constant (depending on the particular universal Turing Machine being used), and so is useless for a fixed string unless the universal machine is given. The universal machine my brain runs may have different additive constants than yours, so we will disagree on the "simplest" continuation.<BR/><BR/>I also always hated those problems. In this case, given knowledge of the ordering of the latin alphabet the answer is reasonably clear (all the counterexamples people have been posting strike me as significantly less likely, though that is necessarily just an opinion), but on many tests they genuinely are ambiguous.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158598227066486922006-09-18T11:50:00.000-05:002006-09-18T11:50:00.000-05:00T F S E R D Q C P B= T _ S _ R _ Q _ P + _ F _ E _...T F S E R D Q C P B<BR/><BR/>= T _ S _ R _ Q _ P + _ F _ E _ D _ C _ BAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158598174578034652006-09-18T11:49:00.000-05:002006-09-18T11:49:00.000-05:00Can I get a hint for the first one ?Can I get a hint for the first one ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158592984601692052006-09-18T10:23:00.000-05:002006-09-18T10:23:00.000-05:00Obviously the desired answer to the second problem...Obviously the desired answer to the second problem is the one of minimal Kolmogorov complxity.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158592706776423372006-09-18T10:18:00.000-05:002006-09-18T10:18:00.000-05:00You need to be able to substract, permute the lett...You need to be able to substract, permute the letters and to manipulate abstract symbols.<BR/><BR/>And you must have logical thinking, and a mathematics class is a logical place to teach it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158591805799285922006-09-18T10:03:00.000-05:002006-09-18T10:03:00.000-05:00There are many reasonable solutions: "twelve, four...There are many reasonable solutions: "twelve, fourteen, sixteen and eighteen" followed T T T T T T T T T T, or<BR/>"twenty, fourty, sixty, eighty" followed by O O O O O T.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158591455747428912006-09-18T09:57:00.000-05:002006-09-18T09:57:00.000-05:00For questions like TFSE I either totally fail to s...For questions like TFSE I either totally fail to see the pattern as I'm not a native English speaker or rather quickly see three or four different answers and the rest of the exercise consists on guessing the aimed audience of the problem poser. Did he meant the obvious answer? the silly ha-ha answer? could the poser have known about the solution having to do with unique decomposition of "bitonic primes" (yes, if the poser is Muthu)?<BR/><BR/>Talking to a fellow at Dagstuhl who was a professional problem composer he said that he strived to design such puzzles in a way that there was a single answer which was much more likely than any other, and that not all such puzzles were designed that way. An example he gave is finish this sequence: ~!@#$%^&<BR/><BR/>AlexAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158591257349504042006-09-18T09:54:00.000-05:002006-09-18T09:54:00.000-05:00There are math-based solutions for this. One can t...There are math-based solutions for this. One can think of the sequence encoding the initials for TWO, FOUR, SIX, EIGHT, and the next three will be T(EN), T(WELVE), F(OURTEEN). Or, you can think of them as THREE, FIVE, SEVEN, ELEVEN, a prime sequence, which is followed by T, S, N. You can also use low-degree polynomial interpolation to obtain whatever you want.Mahdihttps://www.blogger.com/profile/12382401759237060260noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158590929290998442006-09-18T09:48:00.000-05:002006-09-18T09:48:00.000-05:00To second anon: there are also several patterns th...To second anon: there are also several patterns that you can apply in general. The uniqueness of the solution is only due to the limited imagination of who asks the question. One has to solve it by finding the simplest pattern, and there is no universally agreed measure of "simpleness" of patterns.<BR/>I guess the test here (for both problems) is more to see which parents are confident or not in math, and tackle the problem, rather than really test their skills<BR/><BR/>But I wish they would test this approach on a real math problem (even simpler), and one which does not depend on culture: I don't know if all the immigrants coming from cultures with a different alphabet know the ORDER of the latin alphabet...<BR/>Heck, I did not spot the pattern and had to translate letters by their rank in the alphabet (20,6,19,5), "guess" the next number (18) and translate it back in a letter (I leave it to you). And latin is my native alphabet!Anonymoushttps://www.blogger.com/profile/14825435867493579983noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158589818169746072006-09-18T09:30:00.000-05:002006-09-18T09:30:00.000-05:00This must be catching: someone else asked me about...This must be catching: someone else asked me about this second problem as well: It came up in their child's middle school classroom.<BR/><BR/>What I don't get is why the heck the second problem has any place in a math classroom. Since when is pattern discovery based on the english letter encoding of a sequence a math problem ? A puzzle, indeed. But a math puzzle ?Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158589135953364242006-09-18T09:18:00.000-05:002006-09-18T09:18:00.000-05:00To first Anon:Okay, just interpret the phrase"What...To first Anon:<BR/>Okay, just interpret the phrase<BR/>"What is the next three letters in this sequence:" as<BR/>"Can you spot a pattern in the sequence, and if so then what is the next three letters in this sequence according to it:"<BR/><BR/>(To be even more formal: 1. a pattern should include at least one application of its "rule"<BR/>2. Random "patterns" are not allowed).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1158588701307814202006-09-18T09:11:00.000-05:002006-09-18T09:11:00.000-05:00Maybe the right question is: "What does the author...Maybe the right question is: "What does the author think to be the next three letters in the sequence."Mahdihttps://www.blogger.com/profile/12382401759237060260noreply@blogger.com