Sort of live blogging a solution to a problem posed by Nassim Taleb

This morning Nassim Taleb posed this problem on Twitter:

A later tweet clarified that the problem was asking for “at least 3.”

I wanted to write up my solution because I think that it is important to share the thought process rather than just the answer to a question. I’ve written up solutions to similar problems before and was originally inspired to write posts like this one after seeing Tim Gowers “live blog” a solution to an IMO problem.

A couple of notes to be clear:

(Edit) (0) Make sure to read all the way to the bottom as I now have corrected a counting mistake

(1) I’m not sure this solution is correct (EDIT – with the final correction at the bottom I am now much more confident),

(2) Incredibly, two keyboards broke while typing up this post, so sorry if there are typos. It is a miracle that the latex formulas work.

Anyway . . .

I understood the problem to be the same question as this one:

You have 8 balls and 16 boxes numbered 1 through 16. For each ball you select a box uniformly at random and place the ball in the selected box. After placing the 8th ball in one of the boxes, what is the probability that at least one box contains at least 3 balls.

My first inclination was to do a quick back of the envelope calculation using the Poisson and Binomial distributions:

FirstTry

So, assuming a Poisson distribution for the number of balls in each box (with expected value 1/2), the probability of 3 or more balls in a box is about 1.44%. The probability that no boxes have 3 is (1 – 0.0143877)^16 which is about 80%. So the probability of at least one box having 3 or more balls would be around 20%.

The same calculation assuming a binomial distribution with 8 balls having a 1/16 chance of going in a box leads to a guess of around 16% for the probability of a box having at least 3 balls.

I knew that neither of these approaches was correct, but I thought that starting this way would give me a sense of what the right answer would be.

Next I asked how many different ways there were to put 8 balls into 16 boxes. This question is a classic “stars and bars” question from combinatorics. The answer is 23 \choose 8 which is 490,314.

So, how can I makes sense of these 490,314 different ways to put the balls in the boxes?

My first thought here was to look at the partitions of 8, since no matter how the balls are distributed, the sum of the number of balls in each box has to be 8. Turns out there are 22 ways to partition 8:

Mathematica2

Since there are only 5 partitions with only 2’s and 1’s, I figured I’d just count the different ways that those partitions could occur in the 16 boxes.

So, for example:

(1) [1,1,1,1,1,1,1,1] can occur in 16 \choose 8 = 12,870 ways

(2) [2,1,1,1,1,1,1] can occur in 16 \choose 1 * 15 \choose 6 = 80,080 ways

The full calculations for the partitions with only 2’s and 1’s and the ones that include numbers 3 or greater are here:

Mathematica3

So, I had to check these calculations a bunch of times since the ones we want to exclude add up to only 258,570 out of 490,314 -> not even close to 80%. But, checking and checking and checking kept getting me to the same answer.

The total ways to distribute the balls in ways that at least one box gets 3 or more balls is 231,744, and thus the probability of a box getting at least 3 balls is 231,744 / 490,314 which is roughly 47.3%. This probability is much higher than I would have guessed.

Later I saw this follow up tweet from Taleb:

Taleb2

I spent the rest of the day trying to come up with a better formulation, but really was not that successful. The best I could come up with was a formulation using generating functions.

The total number of ways to distribute the 8 balls into 16 boxes is given by the coefficient of x^8 in the polynomial:

(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8)^{16}

Luckily that number is 490,314.

Similarly, the total number of ways to distribute the 8 balls into 16 boxes with at most 2 balls per box is given by the coefficient of x^8 in the polynomial:

(1 + x + x^2)^{16}

and that number is also what we found above -> 258,570.

Math4.jpg

So, we get the same answer as above.

The generating function approach also gives a way to solve the general problem in the second part of Taleb’s tweet. We’d just look at the coefficients of x^n in these two polynomials:

(1 + x + x^2 + x^3 +\ldots + x^{n-1} + x^n)^{d}, and

(1 + x + x^2 + x^3 +\ldots + x^{m-2} + x^{m-1})^{d}.

Then do the same calculation as above.

However, although this approach with generating functions is easy to describe, it really isn’t much easier to calculate, so I doubt it was the reformulation that Taleb had in mind.

(EDIT that goes from here to the end)

[I’ve had to steal a keyboard from my son since one broken keyboard doesn’t type symbols like $, [], and {} making latex formulas impossible and the other doesn’t type the letter t. 4:00 am problems!]

At 4:00 am I woke up and realized an error in the approach. By that time there were a few comments on twitter also pointing out the under counting.

the error in counting comes in assuming the each distribution of balls coming from a partition of 8 is equally likely. That’s not the case. The distribution [1,1,1,1,1,1,1,1] can indeed occur in 16 \choose 8 ways, but there are also 8! (8 factorial, I mean, in case it displays incorrectly) arrangements for each of those ways.

However, the distribution [2,1,1,1,1,1,1] which occurs in 16 \choose 1 * 15 \choose 6 has 8! / 2! different arrangements.

So, factoring in that under counting leads to the following correct count for the cases with only 1’s and 2’s:

Mathematica5.jpg

The 3,567,874,400 cases are out of a total of 16^8 cases and thus the probability of having a 3 in more than one box is given by:

Math6

So, the result is (happily) closer to the back of the envelope result that’d get and I don’t have to worry that the Poisson / Binomial approximations are way off!

Now, back to bed 🙂

Advertisements

Working through some introductory trig ideas with my son

My older son is working through Art of Problem Solving’s Precalculus book this year. I love this book and am happy to help him work through it. For now the topic is trig functions. Here are three nice conversations we’ve had in the last week:

(1) Exploring some parametric plots:

We had been looking at graphs of sin(x) and cos(x), but what if I made the x-coordinate a function cos(t) and the y-coordinate function of sin(t)? What would that look like?

(2) A clever homework problem that gave him some trouble

The question to asked him to find the product:

\tan(\pi/12)*\tan(2\pi/12)*\tan(3\pi/12)*\tan(4\pi/12)*\tan(5\pi/12)

(3) Talking about the sum and difference formulas

This morning he was working through the geometric proofs in the book that give you the sum and difference formulas for cos(a + b) and sin(a + b). After that I showed him how the formulas come from the formula:

e^{i \theta} = \cos{\theta} + i\sin{\theta}

I’ve never taught a precalculus class before, so I’m explaining most of these ideas for the first time.  Hopefully the book will give him a good foundation and my fumbling around will show him one or two fun ideas.   I think this will be a fun year.

Talking about the orbit of Mars with kids

At dinner last night the topic of sending humans to Mars came up. I don’t remember how or why – we just started talking about it and my younger son was really interested. When I asked the boys if there was anything they wanted to talk about for our project this morning the topic was Mars.

The tiny little problem with this topic is that I know absolutely nothing about it! But with a little prep work this morning I was able to throw together what was hopefully a fun 30 min.

We started by watching this short video:

After the video we talked about a few of the ideas. I almost went down the rabbit hole of explaining a bit of mechanics, but probably luckily changed my mind right before jumping in to that topic.

The next topic was Kepler’s 3rd Law. This Law says (oversimplifying) that for planets orbiting the Sun, the time of the orbit squared divided by the radius cubed is constant.

I introduced the law and did the computations for Earth and Mars.

Finally, since my older son is just starting to study trig, I wanted to show a really neat curve. I forget where I saw this idea previously, but it is a fun picture and also a neat trig example.

The question is, if we plot the midpoint of the line connecting the Earth and Mars as they orbit the sun, what does the curve look like?

This was a fun project and is also definitely a neat trig example. For a great history lesson of how humans learned more about Mars check out Terry Tao’s incredible public lecture – “The Cosmic Distance Ladder” (he’s talking about Mars around 58:00 – though maybe earlier, too):

Using Numberphile’s “Pancake Number” video with kids

Numberphile put out a great video on the so-called “pancake number” – see the 3rd video below. I watched it when it came out and thought it would be a fun project for the kids to explore.

Unfortunately I got mixed up on the procedure when we were doing the first two parts of the project this morning. So, at the beginning of the project we weren’t actually studying the “pancake numbers” but rather a variant. Not a big deal, though it required an explanation after we watched the video!

We started with an introduction to the sorting problem and studying the case of trying to put 5 elements in order using (what I thought were) the pancake sorting rules.

Next I asked the kids to explore the problem in general and they looked carefully at a few simple cases. One neat thing here is that one relationship between sorting N and N+1 blocks that they thought would be true turned out not to be true.
 

Now we move on to view the Numberphile video. Katie Steckles does such a great job here (and I love that the sheet of paper from the Graham’s number video is up on the wall behind her!).

 To wrap up we returned to the white board and played around with the correct rules. It was nice that they were able to find an example with 3 blocks that had a different result when we applied the right rules.

Definitely a great video by Numberphile and a fun project for kids. It is always really fun to play with an unsolved problem that is accessible to kids.

Using 3d printing to help explore a few ideas from introductory algebra

Last spring I was playing around with some different 3d printing ideas and found a fun way to explore a common algebra mistake:

Does (x + y)^2 = x^2 + y^2

comparing x^2 + y^2 and (x + y)^2 with 3d printing

Today I decided to revisit that project. We started by looking at the same idea from algebra:

Does x^2 + y^2 = (x + y)^2 ?

At first we talked about the two equations using ideas from algebra and arithmetic.

/

Now I asked the boys for their geometric intuition and then showed them the 3d printed graphs of the two functions.

This part ran a little long while my younger son was stuck on a small but important point about the graph z = (x + y)^2 – I didn’t want to tell him the answer and it took a couple of minutes for him to work through the idea in his mind.

/

Next I showed them 3d prints of x^3 + y^3 and (x + y)^3 and asked them to tell me which one was which. It is really neat to hear the reasoning that kids use to go from shapes to equations.

/

For the last part of the project I asked the boys to come up with their own algebra “mistakes” for us to explore. My older son chose to compare the graphs of \sqrt{x^2 + y^2} and x + y.

/

My younger son chose the two equations x^2 - y^2 and (x - y)^2. Changing the + to a – in our first set of equations turns out to have some pretty interesting geometric consequences – “it looks sort of like a saddle” was a fun comment.

One especially interesting idea here was exploring where x^2 - y^2 = 0. We used Mathematica’s ContourPlot[] function to explore those two lines because those lines weren’t immediately obvious on the saddle.

/

I’m happy to have had the opportunity to revisit this old project. I think exploring simple algebraic expressions is a fun and sort of unexpected application of 3d printing.

Using Grant Sanderson’s Pythagorean Triple video for an introductory trig lesson

My older son is starting to learn trig and I wanted to show him the surprising connection between the exponential function and trig functions. Grant Sanderson’s video on Pythagorean triples from earlier this year came to mind:

After my son watched the video tonight I asked him to talk about some of the ideas. Here’s what he had to say – I was happy that many of the ideas that Sanderson presented sank in:

Now I showed him the incredible formula e^{ix} = Cos(x) + i*Sin(x). Although I just present the formula, the complex number ideas after that are exactly the same ideas that are in Sanderson’s video:

Now I showed him how this formula makes some of the standard trig identities really easy to both derive and remember. The ideas here were really the inspiration for the video because he asked me this morning if the trig functions were linear.

We specifically looked at formulas for Cos(2x) and Sin(2x) here.

Now we used the formulas in a couple of simple examples. First we looked at 45 degrees, then 30 degrees, and then we looked at the angles in a 3-4-5 triangle:

This project was a fun way to introduce an amazing idea in math and also hopefully a nice way to show my son that ideas in trig go way beyond triangles.

Playing with sin() and cos()

My older son has just started the trigonometry this week. I know the topic can be a little dry at the beginning, so I wanted to show him more than just unit circle exercises.

Today we looked at a few fun curves that you can make just by playing around with trig functions.

I stared by showing some simple graphs and then we moved to some 3d shapes:

Next we took a cue from an old project inspired by Henry Segerman:

Playing with Shadows inspired by Henry Segerman

Hopefully both the shape and the shadows come through in the filming – I haven’t figured out how to shoot shadows very well yet.

Finally I let the kids play around with the Mathematica code for a bit to create their own shapes. They had a couple of pretty fun ideas.

There was one little issue that came up on my younger son’s plot, unfortunately. I didn’t have enough detail in the plot to multiply the range by 10. That’s why his picture fuzzed out quite a bit. I didn’t see the problem on the fly, though, and wasn’t able to fix it in real time.

I’m excited to help my son learn about trig. Hopefully a few projects like this one will help him see that that there’s more to trig than just triangles!

Sharing Tim Gowers’s nontransitive dice talk with kids

During the week I attending a neat talk at Harvard given by Tim Gowers. The talk was about a intransitive dice. Not all of the details in the talk are accessible to kids, but many of the ideas are. After the talk I wrote down some ideas to share and sort of a sketch of a project:

Thinking about how to share Tim Gowers’s talk on intransitive dice with kids

One of the Gowers’s blog posts about intransitive dice is here if you want to see some of the original discussion of the problem:

One of Tim Gowers’s blog posts on intransitive dice

We started the project today by reviewing some basic ideas about intransitive dice. After that I explaine some of the conditions that Gowers imposed on the dice to make the ideas about intransitive dice a little easier to study:

The next thing we talked about was 4-sided dice. There are five 4-sided dice meeting Gowers’s criteria. I thought that a good initial project for kids would be finding these 5 dice.

Now that we had the five 4-sided dice, I had the kids choose some of the dice and see which one would win against the other one. This was an accessible exercise, too. Slightly unluckily they chose dice that tied each other, but it was still good to go through the task.

Now we moved to the computer. I wrote some simple code to study 4-sided through 9-sided dice. Here we looked at the 4-sided dice. Although it took a moment for the kids to understand the output of the code, once they did they began to notice a few patterns and had some new ideas about what was going on.

Having understood more what was going on with 4-sided dice, we moved on to looking at 6-sided dice. Here we began to see that it is actually pretty hard to guess ahead of time which dice are going to perform well.

Finally we looked at the output of the program for the 9-sided dice. It is pretty neat to see the distribution of outcomes.

There are definitely ideas about nontransitive dice that are accessible to kids. I would love to spend more time thinking through some of the ideas here and find more ways for kids to explore them.

Thinking about how to share Tim Gowers’s talk on intransitive dice with kids

Yesterday Tim Gowers gave a really nice talk at Harvard about intransitive dice. The talk  was both interesting to math faculty and also accessible to undergraduates (and also to math enthusiasts like me).

The subject of the talk – properties of intransitive dice – was based on a problem discussed on Gowers’s blog earlier in 2017.  Here’s one of the blog posts:

One of Tim Gowers’s blog posts on intransitive dice

Part of the reason that I wanted to attend the talk is that we have played with non-transitive dice previously and the kids seemed to have a lot of fun:

Non-Transitive Grime Dice

Here’s the punch line from that project:

The starting example in Gowers’s talk was due to Bradley Efron. Consider the four 6-sided dice with numbers:

A: 0,0,4,4,4,4
B: 3,3,3,3,3,3
C: 2,2,2,2,6,6
D: 1,1,1,5,5,5

If you have little dice rolling competition in which the winner of each turn is the die with the highest number, you’ll run across the following somewhat surprising expected outcome:

A beats B, B beats C, C beats D, and D beats A.

The question that interested Gowers was essentially this -> Is the situation above unusual, or is it reasonably easy to create intransitive dice?

Although the answering this question probably doesn’t create any groundbreaking math, it does involve some fairly heavy lifting, and I think the details in the talk are not accessible (or interesting) to kids.  Still, though, the general topic I think does have questions that could be both fun and interesting for kids to explore.

In discussing a few of the ideas that I think might be interesting to kids, I’ll use a constraints that Gowers imposed on the dice he was studying. Those are:

(i) The numbers on each side of an n-sided can be any integer from 1 to n

(ii) The sum of the numbers must be (n)(n+1)/2

I’ll focus just on 6-sided dice for now. One question that kids might find interesting is simply how many different 6-sided dice are there that meet these two criteria above? Assuming I’ve done my own math right, the answer is that there are 32 of them:

dice1

Next, it might be interesting for kids to play around with these dice and see which ones have lots of wins or lots of losses or lots of draws against the other 31 dice.  Here’s the win / draw / loss totals (in the same order as the dice are listed above):

competition

So, for clarity, the 4th die on the list – the one with numbers 1,1,3,5,5,6  – wins against 16 other dice, draws with 7 (including itself), and loses to 9.  Not bad!

The die three down from that – the one with numbers 1, 2, 2, 4, 6, 6 – has the opposite results.  Such poor form 😦

It certainly wasn’t obvious to me prior to running the competition that one of these two dies would be so much better than the other one.  Perhaps it would be interesting for kids to try to guess ahead of time which dice will be great performers and which will perform poorly.

Also, what about that one that draws against all the others – I bet kids would enjoy figuring out what’s going on there.

Once I had the list, it wasn’t too hard for me to find a set of three intransitive dice.  Choosing

A ->  2, 2, 3, 3, 5, 6

B -> 1, 1, 3, 5, 5, 6, and

C -> 1, 2, 4, 4, 4, 6

You’ll see that A beats B on average, B beats C, and C beats A.

It is always fun to find problems that are interesting to professional mathematicians and that are also accessible to kids.   A few ideas I’ve found from other mathematicians can be found in these blog posts:

Amazing math from mathematicans to share with kids

10 more math ideas from mathematicians to share with kids

I think exploring intransitive dice will allow kids to play with several fun and fascinating mathematical ideas.   I’m going to try a project (a computer assisted project, to be clear) with the kids this weekend to see how it goes.

 

Talking inverse functions with my older son

My older son was stuck on a question about inverse functions from his Precalculus book:

Let f(x) = \frac{cx}{2x + 3}

Assume that f(f(x)) = x for all x \neq -3/2. Solve for c.

We began by talking about what was giving him difficulty and then moved on to solving the problem.

Next we moved on to looking at the function on Mathematica. It was a little unlucky that the scale was different for the x- and y-axes, but I think the pictures still got the point across.

After we finished talking I posted about the problem on twitter and John Golden made a neat Desmos version of the problem: