tag:blogger.com,1999:blog-3722233.post2459572605947631029..comments2022-05-17T19:30:53.024-05:00Comments on Computational Complexity: Are you a Ringer? A Reverse Ringer?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger39125tag:blogger.com,1999:blog-3722233.post-62240212228693521092011-01-30T10:30:25.702-06:002011-01-30T10:30:25.702-06:00Does light from the caboose count?Does light from the caboose count?jim blairnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-308235920940765272011-01-23T20:42:29.973-06:002011-01-23T20:42:29.973-06:00It's only anecdotal, but I have 2 nephews that...It's only anecdotal, but I have 2 nephews that are both (independently) fascinated by trains, and could tell you quite a bit about them.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73315184724425170652011-01-20T15:04:17.419-06:002011-01-20T15:04:17.419-06:00Last Anonymous- the Anonymous a few back had it ri...Last Anonymous- the Anonymous a few back had it right- first drop off floor 14,<br />then floor 14+13, etc...<br /><br />You can also see either of the two papers that this post pointed to.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66354578343413782382011-01-20T14:47:36.074-06:002011-01-20T14:47:36.074-06:00Prof. Bible Freak,
How do you get 14? Is that (s...Prof. Bible Freak, <br /><br />How do you get 14? Is that (say) the mathematical expectation of the number of attempts needed to surely know the correct floor, assuming a discrete uniform distribution across floors? <br /><br />I get 19, like some others here. <br /><br />I have the honor to be, with the highest consideration, Your Excellency's most humble and most obedient servant.<br /><br />- The low-IQ atheist man-pig. <br /><br />PS: Chazisop, you have, perhaps, a lower IQ than even me, and I'm just a low-IQ man-pig.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33855805424102358552011-01-19T07:05:08.224-06:002011-01-19T07:05:08.224-06:00YES, one can show that 14 is optimal.
Exact upper ...YES, one can show that 14 is optimal.<br />Exact upper and lower bounds are known for f floors, b bowling balls.<br />The papers I pointed to in the post tell you how to do this, but its more fun to do it yourself.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70070125693058749412011-01-19T01:50:32.087-06:002011-01-19T01:50:32.087-06:0014 for the bowling balls problem. Can we prove tha...14 for the bowling balls problem. Can we prove that one cannot do better than 14 ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27436332006684851832011-01-19T00:09:11.525-06:002011-01-19T00:09:11.525-06:00John Sidles, dont u have to do anything better ? i...John Sidles, dont u have to do anything better ? it is nice to see you spend so mAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61018460913806404142011-01-18T07:52:11.680-06:002011-01-18T07:52:11.680-06:00Regarding the bowling ball puzzle.
You have alread...Regarding the bowling ball puzzle.<br />You have already said that the answer is 14 (lines in a Sonnet), without mentioning how it works.<br />Correct me if I am wrong. (I am not even sure you do mean the 14-line sonnet.)<br />First throw one ball from floor 14.If it breaks start from the first floor and throw the ball from every floor going up until it breaks.You have 13 throws left which are enough. If the ball does not break from floor 14, then go to floor 14+13=27 and try. If it breaks here you have 12 throws left to test floors 15 until 26.Otherwise go to floor 14+13+12=39 and continue similarly.If you reach floor 99 and the ball does not break, you know the answer is the 100th floor having only thrown the ball 11 times.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39069416863134003192011-01-17T08:18:27.639-06:002011-01-17T08:18:27.639-06:00GASARCH asks: What has been your experience with s...GASARCH asks: <i>What has been your experience with solving (or not) problems that are, in some sense, below your ability and knowledge level?</i><br /><br />As an exercise, and as a counterpoint to anonymous' post (immediately above)—a post whose rhetorical excesses to me made no sense—by writing a explicitly constructive response to GASARCH's question.<br /><br />It very commonly happens that I encounter natural mathematical questions that seemingly are "below my ability and knowledge level" ... and yet to my dismay, <i>I cannot answer them</i>. <br /><br />Whenever this happens, "the danger signal is up"—to borrow a phrase from von Neumann's essay <i>The Mathematician</i> (1947)—and it is natural to ask myself, "Hmmmm ... so maybe this question is in fact <i>above</i> my ability and knowledge level?" <br /><br />Moreover, when this question arises naturally in the context of daily activities, then I have ask myself whether perhaps the problem is that the style of my mathematical understanding is not "classical", but rather is excessively "baroque and even very high baroque" ... again to use von Neumann's descriptive language.<br /><br />The question "What keeps a railroad train on its tracks?" is a good example of a mathematical question, arising naturally in daily life, that we tend to think is below our ability to answer ... when actually it is <i>above</i> our ability to answer.<br /><br />I maintain a BibTeX database of STEM roadmaps, and it is these troublesome "below our ability" mathematical questions that often have been the primary obstruction to creating viable STEM enterprises.<br /><br />So for me, the answer to GASARCH's question is something like: "The great virtue of simple mathematical questions, arising naturally in daily life, that we can't answer, is that these questions induce in us a feeling of humility that is healthy, by reminding us that a broadly integrated mathematical understanding is a classical virtue."<br /><br />Our planet has seven billion people on it—which is a lot—and yet there is *NO* risk of any shortage of these humility-inducing questions ... and it is very fortunate that these questions, and the global-scale enterprises that are naturally associated to them, are plenty enough to keep a planet-full of people busy.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16339030203690192422011-01-17T02:49:06.040-06:002011-01-17T02:49:06.040-06:00john, i really question your comments. I am not aw...john, i really question your comments. I am not aware of anyone else who comments so much. You probably know, quality prevails, it's not quantity in such circumstances.<br /><br />regarding ur remark that we will need to import trains from china. well, the chinese have done remarkable well in importing all kinds of different technology related to high speed trains. eventually, they reverse engineered everything and now start producing items domestically. <br /><br />They have shown once again the lack of commitmment to copyright and their total disprect to intellectual property. <br /><br />This is something that will backfire on us, if we continue to tolerate their political trade agenda and their stealthy and dirty way of lurking technology companies into mainland china so that tthese companies have to partner up with domestic chinese ones which in turn will have 100% access to trade secrets.<br /><br />what we see is the analog of brain drain for leading u.s. companies. in the short run, setting up these companies in mainland china might seem like a profitable venture (particularly for share holders), but surely nobody seems to be remotely interested about the consequences ...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77454832498720690952011-01-16T19:43:54.226-06:002011-01-16T19:43:54.226-06:00GASARCH, perhaps you and Lance should ask your kid...GASARCH, perhaps you and Lance should ask your kids "What it is it that keeps a railroad car from leaving the tracks?"<br /><br />If they answer "Oh, the train probably has computers to prevent *THAT*!" ... then oh well ... maybe it means the US is destined to import a lot of trains from China. :)John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13965561385910026622011-01-16T17:39:46.043-06:002011-01-16T17:39:46.043-06:00Anony just above Chazisop- do you understand that ...Anony just above Chazisop- do you understand that solution? I don't<br />Whats a flange? Could a kid really get this now? How about back in 1979?<br />(These last two questions ARE rhetorical- I think the answer is NO.)<br /><br />Thanks for telling us the answer!GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63446918520413331912011-01-16T17:38:05.786-06:002011-01-16T17:38:05.786-06:00Chazisop- Binary search does not work since if the...Chazisop- Binary search does not work since if the Bowling ball<br />(or egg or glass crystal...)<br />shatters then you cannot resuse it.<br /><br />Say your first move is to drop the ball off of the 50th floor (which I<br />assume you would do with binary search). The ball SHATTERS. All you know now is that the desired floor is<br />one of 1,2,3,...,49. You only have one ball left so you HAVE TO drop it off floor 1, then2, then 3.,,,<br />until it shatters. Worse case: 50 drops. (I may be off by one here.)<br /><br />Think some more- its a nice problem that I am sure you can do.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36043688942010696792011-01-16T17:23:07.623-06:002011-01-16T17:23:07.623-06:00I've heard two more formulations of the bowlin...I've heard two more formulations of the bowling balls problem. The one is with magician crystal balls and the other with Galileo and the Pisa tower. I prefer the Galileo one. <br /><br />Anyway, in its essense, this is a simple search problem. By using binary search, you use only logN balls on the worst case , which for 100 is 7 balls.Anonymoushttps://www.blogger.com/profile/09364120444779754928noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25223442185440310852011-01-14T13:24:00.988-06:002011-01-14T13:24:00.988-06:00I have the book the train problem came from which ...I have the book the train problem came from which contains the intended answer.<br />It is<br /><br />``The contrary piece on each car is the flange of the wheel. The flange lies below the rail and moves south as the wheel turns.''Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82456011039086398782011-01-14T13:12:45.650-06:002011-01-14T13:12:45.650-06:00The lowest part of the wheels are lower than the t...The lowest part of the wheels are lower than the top of the track.science and mathhttp://oscience.infonoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48939529798096067292011-01-14T10:02:19.975-06:002011-01-14T10:02:19.975-06:00GASARCH, you ask a very difficult question—in esse...GASARCH, you ask a very difficult question—in essence "What (if anything) is different about kids today, and about what they are learning?"—for which diverse good answers exist.<br /><br />For me, there is one crucial difference that is only peripherally related to physical-versus-abstract problem-solving, but rather, has mainly to do with rank-driven versus narrative-driven educational environments.<br /><br />In rank-driven education, the objective is to achieve a high-rank score in testing, then be admitted to a high-rank school, then earn a high-rank degree, then be hired by a high-rank corporation.<br /><br />Narrative-driven educational environments focus upon a very different class of objectives. As Garrison Keillor says in the introduction to his anthology <i>Good Poems:</i><br /><br />---------<br />What makes a poem memorable is its narrative line. A story is easier to remember than a puzzle.<br />---------<br /><br />Carl Barks' story <i>The Runaway Train</i> is (it seems to me) an outstanding example of narrative-driven mathematical education.<br /><br />Of course, narrative-driven mathematical expositions are not solely for children ... researchers like Saunders Mac Lane and Bill Thurston have used narrative techniques at the highest levels of mathematics.<br /><br />Famously, Richard Feynman was yet another narrative-driven researcher, and so perhaps this is a good opportunity to remind people of today's TEDxCalTech Event, <i>Feynman's Vision: the Next 50 Years</i>.<br /><br />If we are lucky, at least some of the TEDxCalTech speakers will echo the memorable words of Steve Martin's character Navin R. Johnson:<br /><br />------<br />Waiter, take away these old narratives ... bring us some *fresh* narratives! The freshest you've got. This year!<br />-------<br /><br />Because heck ... don't pretty much *all* of Feynman's most famous lectures lay out fresh narratives?<br /><br />Moreover, we should all admire the courage of the TEDxCalTech speakers for even taking the stage at this event ... because they're going to have to share that stage with none other than Kongar-Ol Ondar:<br /><br />-------<br />Kongar-Ol Ondar (Tuvan: Коңар-өл Ондар) is a master Tuvan throat singer and a member of the Great Khural of Tuva.<br />-------<br /><br />As Feynman might have said ... it's gonna be <i>terrific!</i> :)John Sidleshttp://sidles@u.washington.edunoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79964671948017415062011-01-14T09:31:11.207-06:002011-01-14T09:31:11.207-06:001) John S and others- YES, seems likely that in an...1) John S and others- YES, seems likely that in an earlier time kids were more interested in mechanical things (like trains) then now. Stories of kids taking apart their parents Vaccum cleaners for example.<br />Kids no longer seem to do this. What are they interested in now? Are we better of worse because of it?<br />(I do not know.)<br /><br />2) YES the answer to the bowling ball puzzle is the same as the number of lines in a Sonnet.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84158169752953907752011-01-14T09:23:25.136-06:002011-01-14T09:23:25.136-06:00The number of lines in a sonnet?The number of lines in a sonnet?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41127445152641991672011-01-14T09:21:19.881-06:002011-01-14T09:21:19.881-06:00Perhaps times have changed ... I seem to remember ...Perhaps times have changed ... I seem to remember this same railroad wheel puzzle being posed in <i>Boy's Life</i> in the early 1960s, but cannot locate the precise episode.<br /><br />There is a terrific wheel-related Donald Duck comic episode, illustrated by Carl Barks, titled <i>"The Runaway Train"</i>, in which Donald's nephews Huey, Dewey, and Louie use their Junior Woodchucks training to predict, solely from considerations of wheel and track geometry, the precise point at which a runaway freight train is destined to collide with a passenger train (and all the details of the calculation are given in the comic book). <br /><br />Their calculations prove correct, and by switching one of the trains to a side-track, a terrible disaster is averted. The ducks are heroes! :)<br /><br />This wonderful illustrated story made a deeply favorable impression upon my young mathematical imagination ... and I see it has been reprinted in at least ten languages. :)John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87777986114367122222011-01-14T08:59:24.308-06:002011-01-14T08:59:24.308-06:00AH- I checked and the puzzle was reprinted from a ...AH- I checked and the puzzle was reprinted from a book from 1979.<br />Did kids know more about trains then?<br />Possibly.<br /><br />You can do much better than 19.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30795844177214687242011-01-14T08:56:47.714-06:002011-01-14T08:56:47.714-06:00Bill, it was probably a "nicer" puzzle w...Bill, it was probably a "nicer" puzzle when it was thought up and children were more familiar with trains having seen them more often and more obviously.<br /><br />For the bowling ball, the answer would seem to be 19, which isn't that much better than 20, in the worst case.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19772661606575893472011-01-14T08:48:53.378-06:002011-01-14T08:48:53.378-06:00ruiaf: You can do better than 20.
Much better (for...ruiaf: You can do better than 20.<br />Much better (for the bowling ball problem). Its a nice problem- think about it some more.<br /><br />others: I agree that the Train problem is not a logic puzzle. I also do not think it is a nice problem, especially for a children.<br />(Your comments on it help confirm this point of view since nobody said<br />HEY, BILL, YOU MISSED THIS CLEVER SOLUTION...)GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20973904642284906662011-01-14T08:35:19.932-06:002011-01-14T08:35:19.932-06:00Arvind Narayanan's answer lead-off answer is &...Arvind Narayanan's answer lead-off answer is "correct" in the sense that it by far the simplest and most geometrically natural answer given, and thus is almost certainly the answer intended by the question-posers.<br /><br />It is necessary to appreciate that the question-askers had in mind, not an idealized mathematical train, but a physical train. The wheels of physical trains <a href="http://www.starmans.net/content/image/NDT%20equipment%202008_10_html_1770393e.jpg" rel="nofollow">all look pretty much alike</a> ... they are as tightly constrained in their design as the wings of jet aircraft ... and the flange to which Arvind's answer refers is a vital part of their design.<br /><br />Deep mathematical issues associated to non-holonomic constraint forces arise, for which a satisfactory geometric understanding is still lacking; see for example Anderson, Elkins, and Brickle, <i>Rail Vehicle Dynamics for the 21st Century</i>.<br /><br />Today, even simpler dynamical systems like rattlebacks and Chaplygin Sleighs evade our full dynamic, thermodynamic, informatic, and geometrical understanding ... if you are thinking "how hard can it be?" ... well ... just try to quantize their dynamics ... or predict their thermodynamical properties in ensemble! :)<br /><br />Thus, students who believe that quantum mechanics is more subtle than classical mechanics are deplorably misguided, not about the subtleties of quantum dynamics, but about the subtleties of classical dynamics. As Saunders Mac Lane says in his <i>Mathematics, Form and Function:</i><br />-----------------<br />It has taken me over fifty years to understand the derivation of Hamilton's equations ... the point of this cautionary tale is the difficulty in getting to the bottom of it all.<br />-----------------John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76071097174188266082011-01-13T21:30:42.326-06:002011-01-13T21:30:42.326-06:00There are gears in the gearbox that drive the whee...There are gears in the gearbox that drive the wheels that are spinning faster wheels are. Depending on where they are relative physically to the final gear, either the top or bottom is moving towards the rear of the train faster than the train is moving forward. That is the wayward component of the train.Another Davidnoreply@blogger.com