tag:blogger.com,1999:blog-8231784566931768362.post1214382754311790726..comments2018-01-13T06:51:48.298-05:00Comments on MathNotations: 1,2,2,3,3,3,4,4,4,4,... What is the 2008th term? SAT-type Questions vs. Math Contest ProblemsDave Marainhttp://www.blogger.com/profile/13321770881353644307noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-8231784566931768362.post-78656375123154805932008-04-23T13:00:00.000-04:002008-04-23T13:00:00.000-04:00Solution to the sequence problem:Let Fn be the num...Solution to the sequence problem:<BR/><BR/>Let Fn be the number such that the first occurance of n is in the Fn'th position.<BR/><BR/>Using the formula for summation of an arithmetic series:<BR/><BR/>Fn= (n^2-n)/2 + 1<BR/><BR/>Let a_n represent the a_n'th position in the sequence.<BR/><BR/>We are trying to find an n such that Fn<=a_n<BR/>or Fn-a_n<=0<BR/><BR/>using the quadratic formula, we see the formula to solve this problem for any a_n is:<BR/><BR/>n=floor(0.5+sqrt(0.25-2(1-a_n)))<BR/><BR/>where floor is the function that rounds down to the nearest integer.<BR/><BR/>so for a_n=56, n=11<BR/>and for a_n=2008, n=63<BR/><BR/>This was verified using a simple brutce force python script.<BR/><BR/>Cheers.JTBnoreply@blogger.comtag:blogger.com,1999:blog-8231784566931768362.post-73251836535675910662008-04-16T07:32:00.000-04:002008-04-16T07:32:00.000-04:00Dave,The digit problem has Alice's coin come up he...Dave,<BR/><BR/>The digit problem has Alice's coin come up heads 5/9 of the time and tails 4/9 of the time. However, that procedure works for any distribution from Alice, even the one you gave.<BR/><BR/>Do you know the term 'convolution'? Let X and Y be random variables with discrete probability distributions p and q. Then, X+Y has probability distribution<BR/><BR/>p*q(t) = ∑p(s) q(t−s), summing over s.<BR/><BR/>To work with our problem, have our random variables take values in Z₂. Heads correspond to odd numbers and tails to even numbers. Then, a fair coin has the probability distribution<BR/><BR/>f(0) = f(1) = ½.<BR/><BR/>It turns out that f*p = f for any probability distribution p; f is the 'zero' for convolutions with this domain.Eric Jablownoreply@blogger.comtag:blogger.com,1999:blog-8231784566931768362.post-32213878863243492212008-04-15T17:37:00.000-04:002008-04-15T17:37:00.000-04:00Eric --What a nice connection - relating the parit...Eric --<BR/>What a nice connection - relating the parity of the sum of 2 digits with outcomes of 2 coins! To make sense of your idea I needed to consider extreme cases. Assume Alice's coin lands Heads 100% of the time (not much entropy, i.e., uncertainty, there!). Then the probabilities of the 4 possible outcomes of flipping the two coins would be (Alice listed first):<BR/>HH: (1)(.5) = 0.5<BR/>HT: (1)(.5) = 0.5<BR/>TH: (0)(0.5) = 0<BR/>TT: (0)(0.5) = 0<BR/>Similarly, if Alice's coin lands Tails 100% of the time.<BR/>Your re-definition of H and T compensates for these extremes. I need to become more knowledgeable in this area before displaying further ignorance!Dave Marainhttps://www.blogger.com/profile/13321770881353644307noreply@blogger.comtag:blogger.com,1999:blog-8231784566931768362.post-49821972680821767342008-04-14T01:20:00.000-04:002008-04-14T01:20:00.000-04:00We can create a new problem out of the digit probl...We can create a new problem out of the digit problem:<BR/><BR/>Suppose Alice and Bob are playing a game requiring a coin flip. Alice has a coin, but Bob is worried that it might be weighted. How can Bob ensure that they can make fair choices even if Alice's coin is weighted.<BR/><BR/>1. If Bob has a fair coin, they can agree that they flip the two coins together and bet on whether they come up the same or different. In fact, this is your digit problem, with Alice's coin being the 100s digit and Bob's the 1s digit.<BR/><BR/>2. If all they have is Alice's coin, what can they do to get a guarantee of fairness from it? Let the students think for a while.<BR/><BR/>Answer: Always flip the coin twice. If they come up HH or TT, ignore the pair of flips and flip it again twice, and so on.<BR/><BR/>If the flips come up HT, call it heads.<BR/><BR/>If the flips come up TH, call it tails.<BR/><BR/>You can go on from there to talk about how many pairs of flips it would take to get a result, and then talk about entropy in probability, but that's a more specialized discussion.Eric Jablownoreply@blogger.comtag:blogger.com,1999:blog-8231784566931768362.post-23287472550635982952008-04-13T16:15:00.000-04:002008-04-13T16:15:00.000-04:00I like that clever mapping approach, Joshua. This ...I like that clever mapping approach, Joshua. This type of method is mot often discussed and it should be. I also like your last statement - Naming is part of a classification system of methods for students. What they also need is additional practice with this type of thinking. Too often, I've seen the occasional challenge problem presented as an isolated question. Students do not make connections without a conscious effort on our part.<BR/><BR/>I post many counting problems on this blog specifically so that teachers can click on the 'Counting Problems' (3 posts) or 'Combinatorial Math' (12 posts) labels in the sidebar and have an immediate problem bank to choose from for class problems and assessments or as ideas for their own questions.Dave Marainhttps://www.blogger.com/profile/13321770881353644307noreply@blogger.comtag:blogger.com,1999:blog-8231784566931768362.post-57060752492640969272008-04-13T16:07:00.000-04:002008-04-13T16:07:00.000-04:00The first problem can be solved with the summation...The first problem can be solved with the summation formula:<BR/><BR/>S(n) = 1+2+...+n = n(n+1)/2<BR/><BR/>One simply needs to find n such that <BR/>S(n) =< 56 < S(n+1) is satisfied:<BR/><BR/>S(n) =< 56 < S(n+1)<BR/><=><BR/>n(n+1) =< 112 < (n+1)(n+2)<BR/><BR/>Now approximate 112:<BR/><BR/>10*11 = 110 =< 112 < 11*12 = 132<BR/><BR/>Therefore the 56th term of the sequence is n = 10.<BR/><BR/>I'm not shure if there is an effective<BR/>way to solve this without the summation<BR/>formula. Is there one?Floriannoreply@blogger.comtag:blogger.com,1999:blog-8231784566931768362.post-55661717714963094892008-04-13T15:35:00.000-04:002008-04-13T15:35:00.000-04:00"Let S be the set of all 3-digit positive integers..."Let S be the set of all 3-digit positive integers whose middle digit is zero. If a number is chosen at random from S, what is the probability that the sum of its digits is even?"<BR/><BR/>Well, for this one, it's obvious.<BR/>Consider the mapping from S to itself which adds one to the last digit if it's even, and subtracts one if it's odd.<BR/><BR/>This mapping is one-to-one and onto and maps all numbers whose digit sum is even onto numbers whose digit sum is odd and vice-versa. So clearly the desired set is exactly half of S.<BR/><BR/>Of course I said that more formally than I would with students, but the idea is a very simple one -- symmetry and parity -- yet very deep and powerful. It's always good to keep coming back to these fundamental strategies and using them again and again. Above all, it's important to identify and NAME them when you use them, so students can start to see the kinds of situations where they come up!Joshua Zuckerhttps://www.blogger.com/profile/04689961247338617418noreply@blogger.com