Tag counting

The most interesting piece of math I learned in 2017 -> the COVFEFE problem

This question from a math exam in India was flying around math twitter last week:

Screen Shot 2017-12-11 at 5.05.10 AM.png

I mistakenly thought the question was just sort of a fun joke and not all that interesting, but then I saw a series of tweets beginning with:

and ending with:

That last tweet was definitely a “wait . . . what??” moment for me.

Thinking about ABRACADABRA right off the bat was too hard, so I simplified the problem drastically too see what was going on. Suppose you are flipping a fair coin, what is the expected number of flips until you see the sequence H H? What about H T? These two problems are also, I think, great ways to introduce ideas about stopping time problems to kids. (the answers are 5 flips and 4 flips respectively).

Playing around with the easier problems showed me why the ABRACADABRA problem could have a longer stopping time than I would have guessed, but I couldn’t solve the problem exactly. Then I found this paper (written as part of an undergraduate research program at the University of Chicago!) which gave a wonderful explanation of the ABRACADABRA problem and (almost incredibly) a way to think about the problem that allows you to solve it in your head!

Screen Shot 2017-12-11 at 5.18.38 AM

Martingale’s and the ABRACADABRA problem by Di Ai

After going through that paper I was happy to have learned some new ideas about stopping time problems and more or less moved on. But then one more nice surprise came from the COVFEFE problem when Nassim Taleb shared his Markov chain solution:

I’d never played with Markov chains in Mathematica (or, basically anywhere really) so I thought it would be fun to use what I learned from Taleb’s code to explore the ABRACADABRA problem. Working through that code gave me a much better understanding of Long’s “which states lead to which states” comment above. It took me a bit of time to realize, for example, that the state ABRA can move to the state AB, for example.

Again, copying Taleb’s code, here’s the transition matrix:

Transition States

and the graph of the states plus the stopping time which matches 26^11 + 26^4 + 26:

Time to Stop.jpg

It was fun to learn that the original COVFEFE problem was part of a class of problems that are much more subtle than they might seem at first glance. Learning about the connections to martingales and learning how to implement Markov chains in Mathematica was a really nice surprise, too.

Advertisements

Revisiting card shuffling after seeing a talk by Persi Diaconis

Last week I took the boys to a talk given by Persi Diaconis at MIT:

Despite most of the talk going over their heads, the boys were really excited after the talk and had lots of different “shuffling” ideas that they wanted to explore.

Since this was going to be a long project, I divided it into two pieces – studying “pick up 52” with my younger son last night and studying shaking the cards in a box with both kids this morning.

The idea of using Shannon Entropy to study how random the shuffles are is something that we explored in these two prior projects:

Chard Shuffling and Shannon Entropy

Chard Shuffling and Shannon Entropy part 2

The original idea for those projects came from on an old Stackexchange post (well, the first comment) here:

See the first comment on this Stackexchange post

So, I kicked off the project last night with my younger son. Here are his thoughts about the Diaconis talk and about his “pick up 52” idea

We did 4 trials without re-sorting the cards in between. Here are some quick thoughts about how the deck was getting mixed up between the 2nd and 3rd throws:

After we finished I had my son do a few minutes of riffle shuffling to completely mix up the deck (starting from where the deck was after the 4th pick up 52). While he was doing that I entered the numbers from our throws into a spreadsheet.

The surprise was that even after the first throw the cards were really mixed up. I was even more surprised by this because he basically threw the deck in the air rather than what (to me anyway) is the normal way of throwing cards for pick up 52.

This morning we continued the project with my older son’s idea of putting the cards in a box and shaking the box. Here the introduction to that idea:

Here are some thoughts from my older son after the first mixing. He didn’t think they were all that mixed up. We did a total of 3 more mixings – the 3rd and 4th were off camera.

Finally, we wrapped up by reviewing the numbers for mixing the cards up in the box. The first mixing had more entropy than we thought, and after the 2nd mixing the cards appear to be pretty close to as mixed up as you can get (equivalent to about 10 riffle shuffles, I think).

This was a really fun project. The math you need to describe what’s going on here is much to advanced for kids (and worthy of a math lecture at MIT!), but kids can still have a lot of fun exploring some of the ideas. The seemingly simple idea of how can you measure how mixed up a shuffle is is a pretty interest idea all by itself.

An instructive counting / probability question from Alexander Bogomolny

I saw this question from Alexander Bogomolny today through a tweet from Nassim Taleb:

It reminded me a bit of a fun question I saw from Christopher Long a few years ago:

A great introductory probability and stats problem I saw from Christopher Long

The first solution that came to mind for the dice question involved generating functions. Here’s the code I wrote in Mathematica:

Mathematica Code

The general idea was to look at powers of the polynomial x + x^2 + x^3 + x^4 + x^5 + x^6 and keep track of the coefficients for powers greater than x^{12}. The one tiny bit of difficulty is that you also have to strip off the powers of x greater than x^{12} after each stage (since you only want to count the first roll giving you a sum greater than 12). Here’s that polynomial cubed, for example:

Coefficient Example

The coefficients for x^{13} through x^{18} tell us the number of different ways to get a 13 through an 18 with three rolls.

The results of counting the polynomial coefficients are given below (columns give the number of ways to roll 13 through 18, and the rows are the dice rolls 3 through 13):

Counts at each stage

These counts don’t have the right weights, though, since 21 ways of getting a 13 on the 3rd roll have a much higher chance of happening than the 1 way of getting an 18 on the 13th roll. In fact each row has a weight 6x greater than the row immediately below it. Weighting the rows properly we get the following counts:

Total Counts.jpg

Now we just have to add up the columns and divide by 6^{13} to get the probabilities of ending on 13 through 18 (and do a weighted sum to get the expected final number) -> the probability of ending on a 13 is about 27.9% and the expected value of the final number is roughly 14.69:

Probabilities

This is a nice problem to show how generating functions can help you find exact answers to problems that seem to require simulations. It was fun to think through this one.

Counting paths

This week both kids had a homework problem in their enrichment math program that involved counting different paths on the edges of a cube.

I thought it would be fun to use those problems as a way to visit the ideas of counting paths in a lattice.

I started the project with a pretty standard path counting problem -> counting the number of paths that go from corner to corner in a rectangular lattice:

Nice I changed the shape of the lattice and ask the boys how they thought the number of paths would change:

Now we moved on to a problem that was similar to the problem they had for homework -> count the paths going from one corner to the opposite corner on a cube:

Now for a challenge -> count the paths on a 2x2x2 cube going from one corner to the other (in this case each step will have length 1):

This is a fun introductory counting exercise. I was a little surprised how difficult it was to keep track of the numbers on the final 2x2x2 cube, but it was nice to see that they boys could see how to count those paths directly with choosing numbers.

Sharing Nassim Taleb’s dart probability problem with kids

Last week Nassim Taleb posted a fun probability problem on Twitter:

I “live blogged” my work on this problem at the link below and eventually found the solution (though after a long detour):

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

One of the boys had to leave early this morning for a school event, so I was looking for a quick project. With some of the work I did in Mathematica on Taleb’s problem still up on my computer screen, I decided to run through the problem with the boys. The point here wasn’t for them to figure out the solution, but rather to see a neat example of counting techniques used to solve a challenging problem.

I started by explaining the problem and asking them to take a guess at the answer. The boys also had some interesting thoughts about the probability of the balls all ending up in different boxes.

Next we went to Mathematica to walk through my approach to solving the problem. In talking through my approach these ideas from number theory and combinatorics come up:

(1) Partitions of an integer,
(2) Binomial coefficients,
(3) Complimentary counting,
(4) Permutations and combinations, and
(5) Correcting for over counting.

Here’s our quick talk through one solution to Taleb’s problem (and, again, this isn’t intended as a “discovery” exercise, rather we are just walking through my solution) :

To wrap up we returned to the idea of the balls spreading out completely -> a maximum of 1 ball per box. Both boys thought this case was pretty likely and were pretty surprised to find it was less likely than ending up with 3 or more balls in a box!

This problem is little bit on the advanced side for 8th and 6th graders to solve on their own, but they can still understand the ideas in the solution. Also, there are some fun surprises in this problem – the chance of the balls spreading out completely was much lower than they thought, for example – so I think despite being a bit advanced, it is a fun problem to share with kids.

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.

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.

 

An introductory stars and bars problem

Yesterday a counting problem from my son’s math team homework gave him a little trouble. The problem went something like this:

There are 5 different types of fasteners and you need to buy 10 total. If you need to buy at least one of each, how many different ways can you do it?

First we talked about the problem and got their initial thoughts. Then I introduced the stars and bars counting idea:

Next I tried to go through a few more examples by changing the numbers a little. The main ideas seemed a little confusing to the boys and I’d hoped a few extra examples would help. Unfortunately things weren’t going so well.

The last example in the prior video confused my younger son, so I moved on to the next video to talk about that example in more detail. By the end of this example I hoped that the general idea had sunk in, but there was still a little confusion.

So, we talked through the problem a few more times. Now the ideas seemed to be sinking in. IF you have N groups of objects (in the original problem 5 fasteners) and you have to pick M total objects (in the original problem we were trying to pick 5 fasteners) you can represent the problem with M stars and N – 1 bars. So the total number of different ways to make the selections are (M + N – 1) “choose” M or, alternately, (M + N – 1) choose (N – 1).

Not all of our projects go super well. Here my mistake was thinking that I could introduce an advanced concept and the boys would immediately understand it. I feel like the ideas here are definitely within their grasp and will probably spend a bit more time this weekend covering the concept. Hopefully a few more examples will do the trick. Stars and Bars.jpg

Working through two old contest problems

I’ve been sort of on pause doing new math with the boys for the last couple of weeks. I want them to find their stride with the new school year before seeing what additional enrichment math we can do at home.

So, while on pause they’ve just been working through problems from old AMC tests in the morning. When they finish we talk through some of the problems that gave them trouble. Both problems were pretty interesting lessons (for them and me, I mean) today.

Here’s what my older son had to say about problem 18 from the 2013 AMC 10b. It was fascinating to me how he counted the numbers in this problem.

and here’s what my younger son had to say about problem #17 from the 1985 AMC 8 (which then was the American Junior High School Math Exam). It was fascinating to me to see both how he played with the averages and how he found his arithmetic mistake.

I love using these old AMC problems to keep the kids engaged with math. It is always fun to see what sorts of ideas give them problems and just as fun to see their problem solving strategies.