tag:blogger.com,1999:blog-8056628635264688872017-10-09T13:56:21.916-07:00Fails to Acceptjonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.comBlogger39125tag:blogger.com,1999:blog-805662863526468887.post-85436663254011055342017-05-31T00:05:00.000-07:002017-05-31T00:16:10.300-07:00Chicken FarmingA chicken farmer can make 6kg, 9kg and 20kg bags of chicken. However he can't make anything else, so for example if you asked him for 7kg of chicken he couldn't do it. On the other hand if you asked him for 15kg he would be able to do that by selling you both a 6kg bag and a 9 kg bag.<br /><br />A natural question to ask is which amounts can he make and which amounts can he not make, a sub-question here is to ask what the largest integer amount he cannot make is. It should be noted that he can make as many bags of each weight as he wants.<br /><br />The solution (stop here if you want to play with it yourself for a few minutes, because spoilers ahead) is to notice that if you don't use any 20 kg bags you can make a lot of multiples of 3. In particular one can make 0,6,9,12,15,18 and so on bags every non-negative multiple of 3 except 3 itself.<br /><br />The next thing to notice is that if you don't use a 20kg bag that that's all you can do! Adding 6s and 9s isn't ever going to give you something which isn't a multiple of 3.<br /><br />Now if we use just one 20kg bag? Well then we can make 20,26,29 32,35,... . In other words we can make most positive integers which leave a remainder of 2 when divided by 3 (in a more formal phrasing numbers which are 2 mod 3) and nothing else. The exceptions being things less than 20 and 23.<br /><br />That only leaves those weights which are 1 mod 3. We need at least two 20kg bags to get anything which is 1 mod 3, but using exactly two 20s we can make 40,46,49 and so on. This means the largest integer weight we can't make is 43kg.<br /><br />Now the trick here was to notice that 6 and 9 share a common factor of 3. That's all well and good but what if the farmer can make lots of 3 arbitrary positive integers a,b and c? It turns out that this is an open problem but I'll leave it for another post.jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com0tag:blogger.com,1999:blog-805662863526468887.post-54608584131951696192017-05-19T04:25:00.000-07:002017-05-19T04:29:26.490-07:00Frequentist and blogging frequencySo I haven't used this blog in a while, but I'm back-ish. Which means I'm panning to start blogging again but may or may not actually get around to it this time.<br /><br />In my <a href="http://failstoaccept.blogspot.co.za/2013/12/whats-in-name.html">first ever post</a> I discussed the idea of a hypothesis test. However I didn't get into any of the technical details in that post. For example suppose I believe that my null hypothesis is that my coin comes up head 50% of the time for data I've flipped it 30 times and gotten 20 heads and 10 tails. <br /><br />Does this mean that I need to give up the idea of a coin which produces heads exactly half the time? In the last post we spoke about the idea of rejecting a hypothesis which is inconsistent with the data, if we had 29 out of 30 heads we'd chuck the idea of a 50-50 coin, if we had 16 heads (again out of 30) we'd keep it. For 20 however it's less obvious. Where is the cutoff?<br /><br />More generally where should the cutoff be? The usual answer to this is ask "How likely would I be to see data this or more strongly against the null hypothesis if the null hypothesis was indeed true?". We then reject the null hypothesis if this probability, which we call a p-value, is "small" and fail to reject it otherwise.<br /><br />By tradition "small" is usually taken to mean less than 0.05, sometimes this tradition is broken, some fields have different traditions and some statisticians absolve themselves of this by saying "the p-value is... ".<br /><br />Going back to our original question of 20 heads in 30 flips, how likely would I be to see data this or more strongly against the null hypothesis if the null hypothesis was indeed true? The surprising answer is: "It depends". A fuller version of this answer is "It depends on what you mean by more strongly against".<br /><br />The probability of getting 20 or more heads from 30 flips works out to about 0.04937, just under the traditional 5% (0.05). However the probability of getting 20 or more heads OR 10 or less heads is twice that. Would 3 heads out of 30 stronger evidence that our null hypothesis is wrong than getting 20? Before you say "yes of course" what if we had exactly 15 heads but they alternated? i.e. HTHTHTHTHTHTHTHTHTHTHTHTHTHTHT.<br /><br />Again the answer here seems like it should be "yes of course that's different" but this dependency isn't something we were thinking about beforehand. Worse it's pretty easy to find patterns in a lot of sequences so we could in principle keep adding in things more surprising than our (unnamed) string of 20 heads in 30 flips.<br /><br />For this reason we need to specify in advance what counts as stronger evidence against our null hypothesis. This is called an alternate hypothesis. Sometimes it's appropriate to make the alternate hypothesis "p>1/2" (or "p<1/2") and sometimes it's appropriate to say p is not 1/2, sometimes it's appropriate to say p depends on the last flip or two in this some way. <br /><br />Of course this isn't the only way to do things. There are others which perform better in some situations and worse in others. I'll (maybe) discuss these in a later post.<br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br />jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com0tag:blogger.com,1999:blog-805662863526468887.post-83225458964890921672015-09-06T04:41:00.001-07:002015-09-06T04:41:37.745-07:00SATMO 2015I'ma little late on this one but never the less.<br /><br />On Saturday August 22nd the 4th South African Tertiary Maths Olympiad was held. The final results can be seen <a href="http://math.sun.ac.za/~swagner/TMO/Scores2015.html">here</a>. A large thanks to <a href="http://math.sun.ac.za/~swagner/">Stephan Wagner</a> for organizing the contest, and to <a href="http://www.wits.ac.za/staff/margaret.archibald.htm">Margaret Archibald</a>, Steven James, Celeste Johnson and Shunmuga Pillay for helping out with invigilating at Wits.<br /><br />Also I must thank the Mathematical Science Students Council at Wits for advertising the event far far better than I could ever have done. In the end we had 35 Wits students sat the <a href="http://math.sun.ac.za/~swagner/TMO/SATMO2015.pdf">exam</a>.<br /><br />I plan to do another post on the statistics of the exam over the last few years fairly soon but for now I'll simply say congrats to the winners and to everyone who took part.<br /> <br /><br /><br /><br />jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com2tag:blogger.com,1999:blog-805662863526468887.post-52783403633451862172015-05-24T23:01:00.003-07:002015-05-24T23:01:29.476-07:00Math BeeI've been asked to set a competition style maths contest for first year students at wits. For some reason or another the organizers decided to call this a (the?) math bee. The goal is 20 multiple choice questions of a level somewhere between the <a href="http://www.samf.ac.za/QuestionPapers.aspx">SAMO Seniors 2nd round</a> and the <a href="http://math.sun.ac.za/~swagner/TMO/index.html">SATMO</a>.<br /><br />I'd like to avoid the paper having too many of my own personal biases. To that end this post is a call for questions. If anyone has any that seem appropriate then please <a href="mailto:lordvirak@gmail.com">e-mail me</a> them to me, I will thank you via blog post.<br /><br />jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com0tag:blogger.com,1999:blog-805662863526468887.post-68683613144838842812015-05-17T05:06:00.001-07:002015-05-17T05:06:58.738-07:00Jury DutyI've been playing with some problem's from the book "50 Challenginh problems in probability with solutions by Frederick Mosteller (my great grand advisor as it happens).<br /><br />Anyway one of the first problems compares two different juries.<br />The first is a one man jury where the juror gets it right with probability p. As there is only one juror his ruling applies.<br /><br />The second is a three man jury with two jurors getting it right with probability p (independently) and the third coin-flipping juror who gets it right with probability 1/2 (again independently). In this jury majority rules. Which is to sy we need two of the three jurors to get things right.<br /><br />Now the question asked is "which is better". A little algebra shows that they're both equally good, which is to say that the second jury reaches the right verdict with probability p.<br /><br />So adding one "regular" (right with probability p) juror and one coin flipper doesn't change anything! What if we ad yet another coin flipper and another regular juror? Now we need three of five correct. Now things <u>do</u> change.<br /><br />A little more algebra shows that we now get the correct verdict with probability, <br /><br />ppp+2.25ppq+0.75pqq=<br />pp(p+q)+1.25ppq+0.75pqq=<br />pp+0.75pq+0.5ppq=<br />p-0.25pq+0.5ppq=<br />p+pq(2p-1)/4<br /><br />Which means that is p>1/2 that adding two jurors to our three (as we did to our one) now improves the verdict. Similarly if p<1/2 (why we're using jurors who're worse than coin flips I don't know but if we did) adding jurors 4 and 5 makes things worse.<br /><br />Does anyone have any intuition for why adding the first pair of jurors does nothjign but adding the second pair helps?<br /><br /><br /><br /><br />jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com0tag:blogger.com,1999:blog-805662863526468887.post-56359776884442149232015-04-04T10:04:00.000-07:002015-04-04T10:04:03.670-07:00Another lightbulb puzzleSo last week was the first weekly Joburg Math meetup. Which basically means a bunch of friends meeting up and playing with math olympiad type problems. If anyone is interested these meetups happen on Sundays at noon in Motherland coffee Rosebank Mall, and of course everyone is welcome. hopefully they'll also give me new ideas for more regular math type blog posts.<br /><br />Anyway here is a problem from The book Creative Mathematics by Alan Beardon, and soem generalizaions due to those involved in the meetup<span style="color: #222222; font-family: arial, sans-serif;"><span style="background-color: white; font-size: 12.8000001907349px;">.</span></span><br /><span style="color: #222222; font-family: arial, sans-serif;"><span style="background-color: white; font-size: 12.8000001907349px;"><br /></span></span><span style="color: #222222; font-family: arial, sans-serif;"><span style="background-color: white; font-size: 12.8000001907349px;">Problem 1. I have a line of n lightbulbs. Each lightbulb has a switch associated to it. The switch toggles (if on changes to off, if off changes to on) all bulbs except the one it's associated to. If all the bulbs start out as off, for whcih n can they be changed to all on?</span></span><br /><span style="color: #222222; font-family: arial, sans-serif;"><span style="background-color: white; font-size: 12.8000001907349px;"><br /></span></span><span style="color: #222222; font-family: arial, sans-serif;"><span style="background-color: white; font-size: 12.8000001907349px;">Problem 2. What if I put the bulbs in an n1 by n2 grid. Again each bulb has a switch associated to it. The switch toggles all bulbs sharign either a row or coloumn with it's bulb. Another way to say that is that it toggles bulbs agreeing in with it's position in exactly one coordinate.</span></span><br /><span style="color: #222222; font-family: arial, sans-serif;"><span style="background-color: white; font-size: 12.8000001907349px;"><br /></span></span><span style="color: #222222; font-family: arial, sans-serif;"><span style="background-color: white; font-size: 12.8000001907349px;">Problem 3. What if I have an n1 by n2 by... by nk grid. Now each switch toggles bulbs which agree in exactly k-1 co-ordinates.</span></span><br /><span style="color: #222222; font-family: arial, sans-serif;"><span style="background-color: white; font-size: 12.8000001907349px;"><br /></span></span><span style="color: #222222; font-family: arial, sans-serif;"><span style="background-color: white; font-size: 12.8000001907349px;">Problem 4. We have the same grid as problem 3 but now the switches toggle bulbs agreeing with our bulb in exactly l coordinates for general l. </span></span><br /><span style="color: #222222; font-family: arial, sans-serif;"><span style="background-color: white; font-size: 12.8000001907349px;"><br /></span></span><span style="color: #222222; font-family: arial, sans-serif;"><span style="background-color: white; font-size: 12.8000001907349px;">I won't say how far we got with these at the meetup because it would spoil the fun somewhat. I will say that only problem 1 actually occurs in Beardon's excellent book, so it's not to be taken as a given that there are nice solutions beyond that. </span></span>jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com0tag:blogger.com,1999:blog-805662863526468887.post-52788857664387608772015-01-12T12:37:00.004-08:002015-01-12T12:37:35.297-08:00The condom problemToday I'm going to share a problem which I learned from <a href="http://www.wits.ac.za/staff/v.jejjala">Prof Vishnu Jejjela</a> . As usual I won't spoil the solution for a few days so that people can mull over it. In the mean time I'll lay out the problem and a few special cases which I think are worth thinking about.<br /><br />n men and m women want to have sex with each other. In particular they want all mn pairings to occur. The problem is that they all have a different STD and they all want to avoid getting anyone else's STD. For this they have condoms, these condoms have some fairly well defined properties.<br /><br />1. They can be nested.<br />2. They can be used in either direction.<br />3. They never break.<br />4. Diseases never get through them.<br />5. On the other hand if a side of condom A is in contact with a side of condom B with disease x then disease x jumps to condom A.<br />6. If a person with disease y uses condom C then disease y appears on the side of condom C actually used.<br /><br />The problem of course is to minimize the number of condoms used. The naive solution of course involves using mn condoms (1 for each encounter).<br /><br />Two classically special interesting cases are<br />1. m=n=2.<br />2. n=1, m an arbitrary odd integer.<br /><br />jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com1tag:blogger.com,1999:blog-805662863526468887.post-63862914985168409972015-01-04T10:02:00.002-08:002015-01-04T10:02:22.470-08:00Happy New Year!!!Happy new year guys (yes both of you). Anyway it's 2015 and I'm going to try to be a more active blogger this year (yes, yes easy to say at the start of the year when everything else going on is comparatively quite).<br /><br />Anyway what better way to kick of the year than with the 2015 <a href="http://failstoaccept.blogspot.com/2013/12/problem-of-year-2014.html">problem of the year</a> . I've played with it a bit but I think I'll leave the ones I have out for a bit. There are a few nice tricks which I don't really want to spoil for anyone reading. I'll leave it for a commenter to spoil. :-)<br /><br />jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com0tag:blogger.com,1999:blog-805662863526468887.post-25439395529081192312014-10-20T04:49:00.003-07:002014-10-20T04:52:13.887-07:00Problem of the year 5775OK so it's 5775 according to the Hebrew calendar. Which means of course that it's <a href="http://failstoaccept.blogspot.com/2013/12/problem-of-year-2014.html">Problem of the year</a> time (well ok it's a bit late but so what).<br /><br />5775 turns out to be kinda tough (or I'm being silly).<br /><br />(5+7)/(7+5)=1 is pretty easy.<br />getting 5-sqrt(7+7-5)=2 took me quite a while.<br /><br />I have at the time of writing no way to get 3.<br /><br />5-(7/7)^5=4<br />5*((7/7)^5)=5<br />5+(7/7)^5=6<br /><br />all sort of fit together. <br /><br />7 like 3 I don't have yet, although I've spent less time on it.<br /><br />5+sqrt(7+7-5)=8<br /><br />5-(7/7)+5=9<br />5*(7/7)+5=10<br /> 5+(7/7)+5=11<br /><br /> again fit into a nice group.<br /><br />This is about where I stopped thinking about these (because 3 and 7 where incomplete).<br /><br /> So naturally the point of this post is to see what people come up with for the 3,7 and things bigger than 11. Enjoy!jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com1tag:blogger.com,1999:blog-805662863526468887.post-51286565781504526832014-08-28T01:45:00.002-07:002014-08-29T05:50:44.119-07:00SATMO 2014Last Saturday, the 3rd annual South African Tertiary Mathematics Olympiad was held. For US based readers think of an SA version of the Putnam contest. Full results, questions and solutions, can be found <a href="http://math.sun.ac.za/~swagner/TMO/index.html">here</a>.<br /><br />Two of the questions (8 and 17) this year where submitted by me. Question 8 I first heard from <a href="http://gottwurfelt.com/">Michael Lugo</a> and question 17 I first heard from <a href="http://www.wits.ac.za/staff/pravesh.ranchod.htm">Pravesh Ranchod</a>. <br /><br />A huge thank you for organizing the event goes out to <a href="http://math.sun.ac.za/~swagner/">Stephan Wagner</a> of <a href="http://www.sun.ac.za/english">Stellenbosch Univesity</a>, as does a huge congrats to the winners.<br /><br /><br /><h1></h1>jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com0tag:blogger.com,1999:blog-805662863526468887.post-16399019338824701192014-07-28T02:47:00.000-07:002014-07-28T02:47:13.580-07:00I've recently been involved in the formation of the <a href="https://www.facebook.com/groups/294498770731916/">Wits Undergrad Maths Society</a><br /><br />This has involved going to a bunch of lectures and handing out sign up sheets. It's also involved a lot of talking to lecturers and other organizers to timetable this but I want to focus on the signup sheets.<br /><br />Turns out that a fair number of students use there wits e-mail addresses and a fair number use something else (g-mail the most common). By inspection there seems to be a very very large correlation between what sheet you signed and which e-mail you put down. that is to say that some of the sheets are almost completely (or in some smaller cases completely) covered with students using there wits e-mail while others are almost devoid of student e-mails. <br /><br />Presumably students look at the first few people putting down a wits e-mail address and decide to copy or see the first few haven't and decide to use the non-wits address. Anyone have any thoughts on what causes this?jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com1tag:blogger.com,1999:blog-805662863526468887.post-41218862868391757442014-07-18T02:16:00.002-07:002014-07-18T02:16:32.369-07:00Hats<a href="http://www.math.upenn.edu/~dmytroy/">Dmytro Yeroshkin</a> and myself have uploaded a paper to the archive <a href="http://arxiv.org/abs/1407.4711">here</a> .<br />It's on a hats game which is well described <a href="http://blog.tanyakhovanova.com/?p=323">here</a> by Tanya Khovanova, and originally proposed by <a href="http://www.math.cornell.edu/~levine/">Lionel Levine</a><br /><br />There are a lot of opportunities for future work left. In particular the original problem with alot of wise men instead of the 2 player case described in our paper.<br /><br />jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com0tag:blogger.com,1999:blog-805662863526468887.post-52183536249794317902014-06-27T14:38:00.000-07:002014-06-27T14:38:19.595-07:00and the next line is...An old puzzle today. this one is great for a blog format as it allows someone who has solved the puzzle to verify that they know the answer without giving away the answer to everyone<br />The problem is to find the next line. Enjoy and show the next line when you have it.<br /><br />1<br />1 1<br />2 1<br />1 2 1 1<br />1 1 1 2 2 1<br />3 1 2 2 1 1jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com1tag:blogger.com,1999:blog-805662863526468887.post-59743969146381554112014-05-08T23:58:00.000-07:002014-05-08T23:58:00.143-07:00I'm thinking of a number...Here is a game. You are presented with countably infinitely many boxes. Each containing a single real number, you're allowed to open as many boxes as you like and view the number inside the now opened box. However to end this game you need at some point in time to point to a specific box and before opening it guess the number inside it. Due to horribly unimaginative rules, you win if you guess right and lose if you guess wrong.<br /><br />At first glance this seems like a game you're bound to lose all the time. However if you arm yourself with the axiom of choice it is possible to win with large probability. Your challenge is to find the optimal solution.<br /><br />Hat tip to <a href="http://www.math.dartmouth.edu/~zhamaker/home">Zach Hamaker</a> for showing me this problem which I believe originally comes from his advisor <a href="http://www.math.dartmouth.edu/~pw/">Peter Winkler</a>jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com6tag:blogger.com,1999:blog-805662863526468887.post-82231752533529647882014-04-05T08:23:00.001-07:002014-04-05T08:23:36.152-07:00Proofs from the bookI came across a really nice thread on Quora today. It asks about the most beautiful proofs in mathematics.<br /><br />Alot of people gave alot of really nice answers. The <a href="http://www.quora.com/Mathematics/Which-are-the-coolest-mathematical-proofs-youve-ever-come-across">thread</a> is here. Anyone have any other good ones?jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com0tag:blogger.com,1999:blog-805662863526468887.post-74268078328866264892014-03-29T20:26:00.004-07:002014-03-29T20:26:46.536-07:00Really really ridiculously cuteApologies to Zoolander for the title. But if you're feeling down about the various things to feel down about in the world, then <a href="http://cuteoverload.com/">Cuteoverload</a> is really cute and cheer uppy.jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com0tag:blogger.com,1999:blog-805662863526468887.post-65413668071722645202014-03-25T03:59:00.004-07:002014-03-25T03:59:50.500-07:00Just a cool link today.<br /><br />Ever wonder how many people are in space? At time of writing 3<br />http://www.howmanypeopleareinspacerightnow.com/jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com0tag:blogger.com,1999:blog-805662863526468887.post-6676624210586597962014-03-24T02:20:00.000-07:002014-03-24T02:20:01.442-07:00A puzzle of primesThis is a fairly old one I first saw in a high school, at one of the Stellenbosch university olympiad camps. Enjoy.<br /><br />It's possible to find a string of 1000 consecutive integers with no primes. For example<br />1001!+2,1001!+3,...,1001!+1001. Does there exist a string of consecutive integers with exactly 5 primes?jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com3tag:blogger.com,1999:blog-805662863526468887.post-15309745098064747482014-03-16T13:15:00.002-07:002014-03-16T13:16:17.432-07:00Another powers of two postI've been negelectign this blog of late.<br />To keep the posts flowing <a href="http://gabrielecirulli.github.io/2048/">here</a> is one of the internets great time sinkers.<br /><br /><br /><br />jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com0tag:blogger.com,1999:blog-805662863526468887.post-12061128262069287282014-03-03T02:36:00.002-08:002014-03-03T12:05:11.444-08:00Odin takes quizzo way too seriouslyRecently I've reread parts of <a href="http://www.amazon.com/Myths-Norsemen-Retold-Puffin-Classics/dp/0140367381">Tales of the Norsemen</a> by Roger Lancelyn Green. Who does an excellent job of describing various mythologies (there is a series). Anyway one of the myths described is of Odin and the wise giant <a href="http://en.wikipedia.org/wiki/Vaf%C3%BEr%C3%BA%C3%B0nir">Valfthrudnir</a> having a "quiz to the death". As described in the link they agree to ask each other questions until someone gets one wrong and then the winner cuts off the loser's head and keeps it.<br /><br />I've got a question about this. First up how do they decide weather a particular question is right assuming they disagree? In this tale they don't but what exactly stops a conversation like this happening?<br /><br />Valf: Which Stallion draws the chariot of the moon?<br />Odin: It's called "Milky".<br />Valf: No it's called "Snowy" I get your head!!<br />Odin: No I'm pretty sure it's "Milky" so I get your head.<br />Valf: SNOWY!!!!!!<br />Odin: MILKY!!!!!!!!! <br /><br />How do they go about judging this?<br /><br /><br />jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com0tag:blogger.com,1999:blog-805662863526468887.post-48791101025393659392014-02-11T10:28:00.003-08:002014-02-11T10:28:28.273-08:00Chain Rule Intuition -Guest Post by Greg Henselman<div><span style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;">My friend <a href="https://alliance.seas.upenn.edu/~paatrn/wiki/index.php?n=People.GregHenselman">Greg Henselman</a> has some really nice intuition about the chain rule. He put it on facebook and this is the thing reposted </span><span style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;">with some mild modifications. It was initially a reply to a student who didn't quite seem to get the chain rule. Anyway I thought this explanation was freaking awesome. In fact I wish someone had taken me aside when I was learning calculus and given me this or something like it. I spent a couple of years thinking of the chain rule as a formal thing rather than having anything remotely resembling intuition for it. When I got to the multivariate version I was even more confused. Anyway this explanation would have saved me a few years worth of grief, so if you ever need to explain the chain rule to someone please give them this or something like it.</span></div><div><span style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;"><br /></span></div><div><span style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;">Anyway without further adieu here is Greg's post.</span></div><div><span style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;"><br /></span></div><div><span style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;">....</span></div><span style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;"><div><span style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;"><br /></span></div>Imagine a long, narrow canal populated with a complex ecosystem of fish. Because many of these live in schools, some parts of the canal have more fish than others. Let g(y) be the number of fish living in the first y meters of the canal (measured from one end, let's assume it's the West end). In this context g'(y) has a concrete meaning: it is the density (or, if you prefer, it is just the number) of fish living exactly y meters (no more, no less) from the West end of the canal.</span><br style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;" /><br style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;" /><span style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;">Suppose a fishing boat has been hired to catch the fish and chop them into edible pieces for bigger fish being grown in a nearby lake. It enters from the West and travels East. If the boat's distance from the West end of the canal at time t is denoted f(t), then the boat's velocity at time t is f'(t).</span><br style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;" /><br style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;" /><span style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;">Assuming the boat catches every fish it passes over, and that the unfortunate fish never get wise and swim East, then the total number of fish in the boat's chum barrels at time t is exactly the number of fish who lived Westward of the position of the boat at time t. We can write this as </span><span style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;">g(f(t)) = (g \circ f)(t)</span><span style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;">. </span><br style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;" /><br style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;" /><span style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;">What is the rate at which fish are being caught at time t? Without using any calculus at all you can probably see that it is the boat's velocity </span><i style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;">times</i><span style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;"> the number of fish living directly below it at time t. The velocity at time t is f'(t), and since the boat's position at t is f(t), the number of fish living directly below it is g'(f(t)).</span><br style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;" /><br style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;" /><span style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;">Putting these pieces together, and remembering that the rate at which fish are caught is the rate of change of (g \circ f)(t), </span><i style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;">i.e.</i><span style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;">(g \circ f)'(t), we see</span><br style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;" /><br style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;" /><span style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;">\[(g \circ f)'(t) = f'(t)g'(f(t)), \]</span><br style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;" /><span style="background-color: white; color: #555555; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 21px;">which is exactly the Chain Rule!</span>jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com0tag:blogger.com,1999:blog-805662863526468887.post-84656866525082759302014-02-09T10:33:00.000-08:002014-02-09T10:33:00.877-08:00Ruler and compass constructions.The ancient Greeks liked ruler and compass constructions. <a href="http://sciencevsmagic.net/geo/#">Here</a> is a web site which challenges you to find some of these. Go forth and conquer in the name of Zeus.jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com0tag:blogger.com,1999:blog-805662863526468887.post-14588123166214586462014-02-02T10:24:00.000-08:002014-02-02T10:24:02.851-08:00Bad MathOne of my favorite internet black holes is sporcle.com<br /><br /><a href="http://www.sporcle.com/games/lobsterman56/math_quiz">Here</a> is a maths related quiz, which will either lower your opinion of humanity or make me wonder how low said opinion started off.<br /><br />Enjoyjonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com1tag:blogger.com,1999:blog-805662863526468887.post-59645455174918143242014-01-30T13:06:00.000-08:002014-01-30T13:06:19.933-08:00Education the world overSo this isn't really a maths post. Anyway while internet/wiki browsing I came across the UN based "education index". I have no idea of the methodology and for some strange reason the wiki article lists the 2007 rankings.<br /><br />Anyway here <a href="http://en.wikipedia.org/wiki/Education_Index">they are</a> , Cuba and to a lesser extent Kazakstan seem to be better than I'd have personally guessed.<br /><br />Does anyone know either the methodology here or have access to more recent data?<br /><br /><br />jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com1tag:blogger.com,1999:blog-805662863526468887.post-78811802879094587832014-01-21T00:14:00.000-08:002014-01-21T00:14:12.199-08:00Rubik's Cube 1-Guest Post by Matt TaiMy friend <a href="http://www.math.upenn.edu/~mtai/">Matt Tai</a> taught me to solve the Rubik's cube. So I asked him to give a series of guest posts on the subject. He threatened to send me a copy of <a href="http://shakespeare.mit.edu/henryviii/full.html" style="background-color: white; font-family: arial, sans-serif; font-size: 13px;">Henry VIII</a> instead of that post. As the version of Henry VIII he sent me was the play by <a href="http://en.wikipedia.org/wiki/William_Shakespeare">William Shakespeare</a> and not the genome sequence of the <a href="http://en.wikipedia.org/wiki/Henry_VIII">British King</a>. I managed to convvince him to give us a post on the Rubik's cube today. Hopefully (though it's unlikely) he'll give us the genome sequence next time.<br /><br /><u><b>Stuff Matt actually wrote below</b></u><br /><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">The Rubik's cube, invented by Erno Rubik, is a puzzle that has become a cultural icon, a puzzle whose difficulty is widely acknowledged.</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">The idea of the puzzle is not terribly complex. The cube is subdivided into 27 smaller "cubies", arranged 3 by 3 by 3. The basic action is to grab a 3 x 3 square of these cubies that make up a face of the larger cube, and twist the square around the center cubie; you can twist it a quarter of the way around, halfway around, or three-quarters of the way around. Twisting it four quarters is the same as not turning the face at all.</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">The cubies have stickers on them, generally in one of six colors; the puzzle is solved when the cubies are arranged such that the stickers form six 3 x 3 squares of the same color, i.e. when the big cube looks like it is solidly colored on each side. The puzzle is then to take a Rubik's cube where the cubies have been scrambled and, via twisting the faces, return the cube to the solved position.</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">Since the invention of the cube, a myriad of methods for getting from a scrambled position to the solved position have been created. Some are hard to learn, some are easy to learn; some are slow, some are fast. Most methods are hard to simply stumble upon by accident; usually to come up with a new method requires lots of experimentation, during which the cube gets scrambled, although hopefully not beyond the experimenter's ability to solve.</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">Most people who pick up a Rubik's cube have some success the first few times, perhaps getting a few stickers of the same color onto a single face, perhaps even getting an entire face just by exploration. But that's usually the stopping point. After all, once you've gone through all that effort to get a face together, you don't want to destroy that. But turning any of the faces next to the solved face will move some pieces into the wrong position, undoing your hard work; so you're stuck with only being able to turn the face you've solved and the opposite face. What can you do now?</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">The secret is that to get the freedom to fix the rest of the cube, you have to temporarily undo your solved parts in such a manner that you can fix them after you've used that temporary freedom, without undoing the new fixes that you've achieved. As you solve more and more of the cube, this gets trickier and trickier.</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">Thus we get to the second part of solving the cube: planning. This doesn't mean you have to know every single step to take before even turning a face (although there are people who can do this) but you need to have an idea of "I want to solve these pieces first, and then those piece next, and then the rest of the pieces afterward". While less essential than the first part, the temporary-controlled-<wbr></wbr>scrambling for freedom trade-off, this allows you to keep track of what kind of scrambling you're allowing at each step, how much control you need over that scrambling. You could be purely opportunistic and just solve whatever piece is easiest to slot into place, but if your solved pieces are scattered randomly around the cube then they're blocking all sorts of possible moves and are hard to move out of the way.</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">So most methods can be broken up into these two pieces, which I'll call "algorithms" and "plans". An algorithm in this case is a specific set of twists (e.g. twist the top face a quarter turn, then the right face a half turn, etc) that moves some number of cubes around, while also having some other cubes end up in the same positions that they started in. The first bunch of cubes are the ones you're trying to put into place, the second bunch of cubes are the ones that are already solved and that you're trying not to screw up. A plan is a sequence of bunches of cubes, in order of which ones you'll solve first. For instance, one plan might say "pick a face, put the edge pieces for that face in place, then the corner pieces in place, and then the edges next to those corners, etc". At each step of the plan, the algorithms will tell you the exact set of twists needed to execute that step of the plan; which algoirthm to use will depend on which step of the plan you're on and the actual position of the cubes involved.</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">While plans are often malleable and often involve some on-the-spot thinking, algorithms are usually just memorized, since they are much less flexible. Substituting a half-turn for a quarter turn can lead you quite far from where you wanted to go, but solving one particular corner before another often isn't too much of a stretch. Algorithms are also less flexible in terms of what they can do; a given algorithm moves a specific set of cubes around in a specific way and keeps a specific other set of cubes in the same place, so if that isn't quite what you want, you'll need a new algorithm. Some methods require memorizing hundreds or thousands of algorithms for particular situations; in return, they get speed, in that the more specific algorithms are also often faster than more general ones. So if you want speed, then you need to have a good memory. You also need to be able to recognize what needs to be done quickly, not wasting time choosing which cubes to get into position next. Hence the need for good plans.</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">But methods aren't the only things that go into speed. You need dexterity as well. Speed cubers often use all of their fingers individually when solving, and their wrists, so that once a face has been twisted they can go to the next move without having to reposition their fingers or the cube in preparation. Perhaps surprisingly, a lot of effort is put into the physical cube as well. A cube that requires a lot of strength to turn is not going to be good for speed cubning, nor is a cube whose faces won't stop spinning if you tap it accidentally. A good speedcube will be easy to turn, but the faces will stay put until deliberately twisted, and will twist exactly (or almost) a quarter, half, or three-quarter turn, as if you turn a face somewhere in between the other faces will usually refuse to budge. Of course, some speedcubers have learned to take advantage even of this constraint.</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">Interestingly, the fastest speedcubing methods are not the shortest, in that although someone using these methods can solve the cube in a very short time, there are other methods which involve fewer overall twists. Using fewer twists does make for a shorter solving time, all other things being equal, but these methods with few twists require the solver to spend a lot of time analyzing the cube at each step to determine which twist to do next, while someone focusing on speed will simply keep turning without regard for whether they're taking the absolute shortest (measured in twists) path or not. By the way, the absolute shortest path, if we measure a quarter twist, a half twist, and a three-quarter twist each as a single move, is known to be at most 20 moves long. This was proved definitively in 2010 using a computer running a lot of calculations. Unfortunately, nobody knows how to figure out those 20 moves for a given scrambled position. The shortest known methods take about 50 moves, and involve tons of memorization without much pattern.</div><div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 13px;">Next time I'll get a bit into the math of the Rubik's cube, but for now I'll just note that there are over 40,000,000,000,000,000,000 possible positions for a standard, solid-colors Rubik's cube to be in. That's 40 followed by 18 0s. So someone who knows a general method for solving a Rubik's cube knows how to get from any of those 40 million million million positions to the solved position reliably, and it is possible to do so in only 20 moves.</div>jonathan karivhttps://plus.google.com/101327060857263638427noreply@blogger.com0