Tag Archives: math

Cereal Boxes Redux

8 Replies

In my last post, my students were wrestling with a question about cereal prizes.  Namely, if there is one of three (uniformly distributed) prizes in every box, what's the probability that buying three boxes will result in my ending up with all three different prizes?  Not so great, turns out.  It's only 2/9.  Of course this raises another natural question: How many stupid freaking boxes do I have to buy in order to get all three prizes?

There's no answer, really.  No number of boxes will mathematically guarantee my success.  Just as I can theoretically flip a coin for as long as I'd like without ever getting tails, it's within the realm of possibility that no number of purchases will garner me all three prizes.  But, just like the coin, students get the sense that it's extremely unlikely that you'd buy lots and lots of boxes without getting at least one of each prize.  And they're right.  So let's tweak the question a little: How many boxes do I have to buy on average in order to get all three prizes?  That's more doable, at least experimentally.

I have three sections of Advanced Algebra with 25 - 30 students apiece.  I gave them all dice to simulate purchases and turned my classroom---for about ten minutes at least---into a mathematical sweatshop churning out Monte Carlo shopping sprees.  The average numbers of purchases needed to acquire all prizes were 5.12, 5.00, and 5.42.  How good are those estimates?

Simulating cereal purchases with dice

Here's my own simulation of 15,000 trials, generated in Python and plotted in R:

I ended up with a mean of 5.498 purchases, which is impressively close to the theoretical expected value of 5.5.  So our little experiment wasn't too bad, especially since I'm positive there was a fair amount of miscounting, and precisely one die that's still MIA from excessively enthusiastic randomization.

And now here's where I'm stuck.  I can show my kids the simulation results.  They have faith---even though we haven't formally talked about it yet---in the Law of Large Numbers, and this will thoroughly convince them the answer is about 5.5.  I can even tell them that the theoretical expected value is exactly 5.5.  I can even have them articulate that it will take them precisely one box to get the first new toy, and three boxes, on average, to get the last new toy (since the probability of getting it is 1/3, they feel in their bones that they should have to buy an average of 3 boxes to get it).  But I feel like we're still nowhere near justifying that the expected number of boxes for the second toy is 3/2.

For starters, a fair number of kids are still struggling with the idea that the expected value of a random variable doesn't have to be a value that the variable can actually attain.  I'm also not sure how to get at this next bit.  The absolute certainty of getting a new prize in the first box is self-evident.  The idea that, with a probability of success of 1/3, it ought "normally" to take 3 tries to succeed is intuitive.  But those just aren't enough data points to lead to the general conjecture (and truth) that, if the probability of success for a Bernoulli trial is p, then the expected number of trials to succeed is 1/p.  And that's exactly the fact we need to prove the theoretical solution.  Really, that's what we need basically to solve the problem completely for any number of prizes.  After that, it's straightforward:

The probability of getting the first new prize is n/n.  The probability of getting the second new prize is (n-1)/n ... all the way down until we get the last new prize with probability 1/n.  The expected numbers of boxes we need to get all those prizes are just the reciprocals of the probabilities, so we can add them all together...

If X is the number of boxes needed to get all n prizes, then

$latex E(X) = frac{n}{n} + frac{n}{n-1} + cdots + frac{n}{1} = n(frac{1}{n} + frac{1}{n-1} + cdots + frac{1}{1}) = n cdot H_n&s=2$

where Hn is the nth harmonic number.  Boom.

Oh, but yeah, I'm stuck.

Pruning Tree Diagrams

2 Replies

A few days ago we opened up with some group work surrounding the following problem.  I gave no guidance other than, "One representative will share your solution with the class."

My favorite cereal has just announced that it's going to start including prizes in the box.  There is one of three different prizes in every package.  My mom, being cheap and largely unwilling to purchase the kind of cereal that has prizes in it, has agreed to buy me exactly three boxes.  What is the probability that, at the end of opening the three boxes, I will have collected all three different prizes?

It's a very JV, training-wheels version of the coupon collector's problem, but it's nice for a couple of reasons:

  1. The actual coupon collector's problem is several years out of reach, but it's a goody, so why not introduce the basics of it?
  2. There is a meaningful conversation to be had about independence.  (Does drawing a prize from Box 1 change the probabilities for Box 2?  Truly?  Appreciably?  Is it okay to assume, for simplicity, that it doesn't?  How many prizes need to be out there in the world for us to feel comfortable treating this thing as if it were a drawing with replacement?  If everybody else is buying up cereal---and prizes---uniformly, does that bring things closer to true independence?  farther away?)
  3. There are enough intuitive wrong answers to require some deeper discussion: e.g, 1/3 (Since all the probabilities along the way are 1/3, shouldn't the final probability of success also be 1/3?), 1/27 (There are three chances of 1/3 each, so I multiplied them together.), and 1/9 (There are three shots at three prizes, so nine outcomes, and I want the one where I get all different toys.)  The correct answer, by the by, is 6/27 or 2/9 (try it out).

Many groups jumped right into working with the raw numbers (see wrong answers above).  A few tried, with varying levels of success, to list all the outcomes individually (interestingly, a lot of these groups correctly counted 27 possibilities, but then woefully miscounted the number of successes...hmmm).  A small but determined handful of groups used tree diagrams to help them reason about outcomes sequentially.

This business of using tree diagrams was pleasantly surprising.  We hadn't yet introduced them in class, and I hadn't made any suggestions whatsoever about how to tackle the problem, so I thought it was nice to see a spark of recollection.  That said, it's not terribly surprising; presumably these kids have used them before.  But I did run across one student, Z, who interpreted his tree diagram in novel way---to me at least.

Most students, when looking at a tree diagram, hunt for paths that meet the criteria for success.  Here's a path where I get Prize 1, then Prize 2, then Prize 3.  Here's another where I get Prize 1, then Prize 3, then Prize 2...  The algorithm goes something like, follow a path event-by-event and, if you ultimately arrive at the compound event of interest, tally up a success.  Repeat until you're out of paths.  That is, most students see each path as an stand-alone entity to be checked, and then either counted or ignored.

What Z did was different in three important ways.  First of all, he found his solutions via subtraction rather than addition.  Second, he attacked the problem in a very visual---almost geometric---way.  And third, he didn't treat each path separately; rather, Z searched for equivalence classes of paths within the overall tree.

Z's (paraphrased) explanation goes as follows:

First I erased all of the straight paths, because they mean I get the same prize in every box.  Then I erased all of the paths that were almost straight, but had one segment that was crooked, which means I get two of the same prize.  And then I was left with the paths that were the most crooked, which means I get a different prize each time.

Looking at his diagram, I noticed that Z hadn't even labeled the segments; he simply drew the three stages, with three possibilities at each node, and then deleted everything that wasn't maximally crooked.  How awesome is that?  In fact, taking this tack made it really easy for him to answer more complicated followup questions.  Since he'd already considered the other cases, he could readily figure out the probability of getting three of the same prize (the 3 branches he pruned first), or getting only two different prizes (the next 18 trimmings).  He could even quickly recognize the probability of getting the same prize twice in a row, followed by a different one (the 6 branches he trimmed that went off in one direction, followed by a straight-crooked pattern).

[youtube=http://www.youtube.com/watch?v=jfJb_afqA0M]

Of course this method isn't particularly efficient.  He had to cut away 21 paths to get down to 6.  For n prizes and boxes, you end up pruning nn --- n! branches.  Since nn grows much, much faster, than n!, Z's algorithm becomes prohibitively tedious in a hurry.  If there are 5 prizes and 5 boxes, that's already 3005 branches that need to be lopped off.  So yes, it's inefficient, but then again so are tree diagrams.  Without more sophisticated tools under his belt, that's not too shabby.  What the algorithm lacks in computational efficiency, it makes up for in conceptual thoughtfulness.  I'll take it that tradeoff any day of the week.

Conditional Response

4 Replies

Aside from being entertaining, these DIRECTV commercials offer at least two important lessons about logic.

[youtube=http://www.youtube.com/watch?v=c-zG5U0v3gU&feature=relmfu]

For starters, let's name the propositions listed in the video:

  • q: your cable is on the fritz
  • r: you get frustrated
  • s: your daughter imitates
  • t: your daughter gets thrown out of school
  • u: your daughter meets undesirables
  • v: your daughter ties the knot with undesirables
  • w:  you get a grandson with a dog collar

So the ad takes us through the following sequence of conditional statements:

$latex begin{array}{lcl} q & longrightarrow & r \ r & longrightarrow & s \ s & longrightarrow & t \ t & longrightarrow & u \ u & longrightarrow & v \ v & longrightarrow & w end{array}&s=2$

Let's be generous and accept that each statement, individually, is true.  Then we're led sequentially along a nice string of propositions, beginning at q and ending with w.  Actually, there's one more tacit proposition, p: you have cable.  So the commercial's (implicit + explicit) logic looks something like this:

$latex p longrightarrow q longrightarrow r longrightarrow s longrightarrow t longrightarrow u longrightarrow v longrightarrow w&s=2$

And therein our first logic lesson: conditional statements respect transitivity.  We can follow an unbroken path of propositions all the way from p to w, which means we can replace that whole string of implications with the statement, "If you have cable, then you'll get a grandson with a dog collar."  Symbolically:

$latex p longrightarrow w&s=2$

We've accepted all the statements along the way, so we accept this one as well, which is both funny and logically sound.  DIRECTV has successfully made fun of the cable companies, and we've had a chuckle.  And if the commercial were to end there, everything would be hunky dory.  But it doesn't end there.  It ends on the line, "Don't have a grandson with a dog collar; get rid of cable..."  Which is to say, "If you don't have cable, you won't have a grandson with a dog collar."  Or...

$latex neg p longrightarrow neg w&s=2$

But that's incorrect!  And that's our second lesson: the technical name for this fallacy is denying the antecedent, or the inverse error.  To give you a more intuitive example, consider the propositions:

  • p: you are a dog
  • q: you are a mammal

$latex p longrightarrow q&s=2$: "If you are a dog, then you are a mammal."  True.

$latex neg p longrightarrow neg q&s=2$: "If you are not a dog, then you are not a mammal."  Obviously false.

It might very well be true that having cable leads to a grandson with a dog collar, but that certainly doesn't mean getting rid of cable is enough to avoid one.

War Games

5 Replies

Back in my previous existence as an artillery officer, I participated in the war for a little while.  Our main job---my Marines and I---was to provide counter-fire support for units in and around the city of Fallujah, Iraq.  Basically, whenever our guys started taking rocket and/or mortar fire, radar would track the source of those rounds and send us their point of origin as a target.  Then we would shoot at it.  Simple.  Kind of.

By the time I got to Fallujah, all the dumb bad guys had been selected out of the gene pool; the ones who were left knew that what they were doing was extremely risky, and they took steps to minimize that risk.  They tried their best to make every opportunity count, and our goal was to make it just as costly as possible for them to shoot at us.  It was a deadly serious game-theoretical problem for both sides.  A game measured in seconds.

Continue reading →

The (square) Root of Love

Leave a reply

All right, fellas, huddle up.  We're going to talk about the best way to find true love.  I mean, you can't just go running around all willy-nilly hoping to bump into somebody great.  The world is a big place.  You need a strategy, man.  A dating plan of attack.

First, some ground rules, some general observations about romantic life, and a few restrictions in the interest of mathematical well-behavedness:

  1. You are only going to meet a finite number of datable women over the course of your lifetime.  It will be a depressingly low number.
  2. You are going to be an upstanding citizen and date only one woman at a time.
  3. You will date a woman for some finite period of time, at which point you'll make a decision either to pull the trigger and propose, or cut her loose.  Or, more likely, she'll dump you first.
  4. Once you propose, no takesies-backsies.  And once you cut a woman loose, you can't ever reconsider her for marriage; she will hate you forever.
  5. You are able to perfectly rank the women you have dated according to a strict, unambiguous order of preference.  Tie goes to the blonde.
  6. You will encounter these women in random order.  That is, you are completely ignorant of where the next potential wife will stand in the overall rankings.
  7. You will date a certain number of women without really considering any of them for a proposal.  In other words, you'll take some time getting a feel for who's out there.  Setting the bar.

In the world of mathematics, this is what's known as an optimal stopping problem.  You're going to date, and date, and date..., and stop.  Hopefully on the woman of your dreams (hence the optimal part).  In fact, this is one of those problems that's so famous it goes by several (mildly sexist) names: the secretary problem, the sultan's dowry problem, the fussy suitor problem.  Because it's Valentine's Day, we'll call it the marriage problem.

Continue reading →

Smashmouth Mathematics

5 Replies

If it were physically possible to fold a piece of paper in half 50 times (it's not), how thick would the resulting origami sculpture be?  Quick!  No fair calculating.  What does your gut say?

If you have absolutely no idea, I'll tell you that a standard piece of printer paper, folded six times by high a school student with very little concern for symmetry or crease definition, has an average thickness somewhere between six and eight millimeters.  How much will that increase over the next 44 folds?  Any ideas?

Continue reading →

Computational Crisis

3 Replies

Let's be clear: American software engineering is in crisis.  Thirty years ago our computer programs were the best in the world; now they routinely lag behind those from South Korea, Finland, China, and even...*gulp*...Canada.  In fact, a 2009 assessment found that U.S. reading software ranked 17th among the 34 OECD countries, math software a dismal 25th.  In the absence of radical reform, our code will cease to be competitive in an increasingly global economy, and we risk losing our preeminent place on the world stage.

In addition to poor test scores, American software has been suffering from increased feelings of alienation and disengagement.  In a survey from last year, 61% of programs said that they "strongly disliked" or "hated" compiling, and more than half said they would rather digitize Wuthering Heights than debug.  There's no doubt the situation is dire.

But there is a solution.

Continue reading →

Greek to Me

1 Reply

I recently had a chance to do one of my favorite (and my students' least favorite) things: talk about words in math class.  Math words.  I also had the opportunity to use one of my favorite math-teacher-type resources: a dictionary.  I don't mean the glossary out of a math book, or a page from Wolfram MathWorld, or any one of the approximately 10.5 million web results (as of this writing) that the Google spits out when prompted with "math" + "dictionary."  I'm talking about a good, old fashioned English dictionary, one of three left in my room by the previous English-teaching occupant: Webster's Ninth New Collegiate, circa 1989.

Continue reading →

Flippin' Wizardry

Leave a reply

Because I'm a math teacher, my services as demystifier of mathematical phenomena are sometimes requested by family and friends who find themselves sufficiently mystified by something mathematical.  Recently I've had a few people send me the link to the YouTube video, "How do japanese multiply??" [sic]

Based on some of the comments (e.g., "What the [flip] is this wizardry?"), there are at least a few people in the world who might like an explanation.  Here's the original video, followed by my narrated solution, plus, for the nerdily inclined, a bonus example in base 6!  Can you imagine anything more fun?

Actually, if you want a much more interesting multiplication algorithm, take a look at Russian Peasant Multiplication.  Now that's some [binary] wizardry.

[youtube=http://www.youtube.com/watch?v=e-P5RGdjICo]

...and the response...

[youtube=http://www.youtube.com/watch?v=85Vd0NpL32k&context=C3a288dcADOEgsToPDskJDE7sA83vY-q75bAdFKWfZ]

Choosy

4 Replies

Something deeply unsettling is afoot in the land of math education when I'm teaching the same backwards thing in the same backwards way it was presented to me as a high school kid.  To wit, combinations.

Here is the current state of the art, according to the big boys of Advanced Algebra publishing:

Fundamental Counting Principle ====> Permutations ====> Combinations ====> Pascal's Triangle ====> Binomial Theorem  ====> Celebration

I submit that, when we do it this way, we're double-charging our students for their attention.  We bog them down in unnecessary algebraic trifling, and we go out of our way to delay the payoff for just as long as possible.  It's bad marketing, and it's bad teaching.  And we don't exactly get away scot-free in all this.  I know I'm in for a rough couple of weeks any time I have to close my opening lesson with, "Trust me."

Continue reading →