Nassim’s problem really isn’t accessible to kids, but a slight variant is -> how many sequences of 250 coin flips are there where no run of heads or tails is longer than 2 flips?

I decided to go through that problem with the boys this morning. It was just at the right level to really challenge them, but still fit inside of a 30 min project.

We started by looking at Xi’s problem and they both had pretty good intuition for which sequence was which:

After the short introduction we started trying to figure out how to tackle the problem about sequences where the longest run was at most 2. After thinking of a few other ideas first, they decided to take a look at some shorter sequences to see if that would help us get some intuition for how many had runs that were no longer than 2:

Now we took a look at the sequences of length 4. Luckily there are only 16 different coin flip sequences of length four, so we could write them all out. The boys found that there were 10 sequences with runs no longer than 2. That led to an idea about how many would work in general:

Now we had a conjecture – there would be 16 sequences of length 5 that had runs no longer than 2 – so we tried to count those sequences directly to see if the conjecture was right:

Finally, we sketched a general proof of the conjecture (I’m intentionally being vague on what it is to not give it away). This part was also a little difficult for the boys, but they eventually saw the right pattern and that pattern led to the general proof:

This problem made for a really fun project this morning and Nassim’s problem led to some great twitter discussions that lasted all week. I was happy to be able to find a piece of Nassim’s problem that the boys could tackle.