Tag counting

Revisiting Joel David Hamkins’s “Graph Theory for Kids”

A few years ago we did a fun project with Joel David Hamkins’s “Graph Theory for Kids”:

Going through Joel David Hamkins’s “Graph Theory for Kids”

Here’s the link to Hamkins’s notes for the project:

Graph Theory for Kids

This project was also inspired by the project we did yesterday on the graph isomorphism theorem:

Sharing Lazlo Babi’s graph isomorphis talk with kids

For today’s project I printed two copies of Hamkins’s booklet and had the boys work through it on their own. After they were finished, we talked through the project after they were finished. Here’s the conversation broken into 4 parts – as you’ll see, Hamkins has made an absolutely fantastic project for kids:

Part 1: An introduction to graphs and one surprising property

Part 2: Looking at some more complicated or “extreme” examples and also illustrating how some of the more complicated graphs make for nice counting exercises for kids

Part 3: Now a few examples that the kids made on their own – this part led to a nice discussion about crossings

Part 4: Some 3d shapes and a really fun observation from my older son about the sphere

Advertisements

Talking through two problems from the 2005 AMC 10

I really enjoy using old AMC problems to talk about math with the boys.

These two problems gave my older son some trouble today:

Tonight I had a chance to talk through these problems with them.

Here’s the probability problem:

Here’s the GCD problem:

Talking though Richard Evan Schwartz’s Gallery of the Infinite with kids

We received Richard Evan Schwartz’s Gallery of the Infinite in the mail this week:

I thought that the boys would love reading the book and asked them to each read it twice prior to today’s project. Here are some of the things that they thought were interesting (ugh, sorry for the focus problems . . . .) :

The first thing the boys wanted to talk about was the “smallest” infinity -> \aleph_0. Here we talked about that infinity and other sets of integers that were the same size.

Next we moved on to talk about the rational numbers – we had a good time talking through the argument that the “size” of the rational numbers was the same as the positive integers.

This argument is represented in the book by a painting of a shark!

Now my older son wanted to talk about Cantor’s diagonal argument. He was a little confused about the arguments presented in the book, but we (hopefully) got things straightened out. I think this shows kids can find ideas about infinity to be really interesting.

Finally, we wrapped up by talking about the implications of the infinity of binary strings being larger than the infinity of counting numbers.

Definitely a fun project. I love the content of the book and so do the kids. The only problem is that the quality of the binding is awful and although we’ve only had the book for a few days, it is falling to pieces. Boo 😦

Working through a challenging AMC 10 problem

My son was working on a few old AMC 10 problems yesterday and problem 17 from the 2016 AMC 10a gave him some trouble:

Screen Shot 2018-01-07 at 5.14.40 PM

I thought this would be a nice problem to go through with him. We started by talking through the problem to make sure that he understood it:

In the last video he had the idea to check the cases with 10 and 15 balls in the bucket, so we went through those cases:

Now we tried to figure out what was happening. He was having some difficulty seeing the pattern, so I spent this video trying to help him see the pattern. The trouble for me was that the pattern was 0, 1, 2, . . ., so it was hard to find a good hint.

Finally he worked through the algebraic expression he found in the last video:

This isn’t one of the “wow, this is a great problem” AMC problems, but I still like it. To solve it you have to bring in a few different ideas, and combining those different ideas is what seemed to give my son some trouble. Hopefully going through this problem was valuable for him.

Sharing the ABRACADABRA problem with kids

Yesterday we did a fun project on Markov chains and sharing the “COVFEFE” problem with kids:

Sharing Markov chains and the “covfefe” problem with kids

For me math behind this problem was the most interesting math I learned in 2017:

The most interesting piece of math I learned in 2017 -> the “covfefe” problem

Today we moved on to a really neat surprise, and what makes the math behind this problem incredibly fun -> the “ABRACADABRA” problem.

First, we reviewed the ideas from yesterday:

After that review, we though through a few of the states and the transition probabilities in the new word. The transition probabilities are subtly different than in the “COVFEFE” problem:

Now we went to Mathematica to code in the ideas we discussed in part 2. We did about half of the coding on camera and did the other half off camera:

Finally, having finished the code we discussed what results we expected. I don’t see how anyone could get the right intuition here seeing the problem for the first time, so what do you expect here is almost an unfair question. Still, the boys had some nice ideas and then we checked out the results:

There are other approaches to these problems – the approach via Martingales, for example:

What that approach is also interesting (and incredible – you can solve the stopping time in your head!) I think the Markov chain approach is a bit more accessible to kidsd. Well . . . maybe because the math is buried in the background.

Anyway – super fun project, and an great piece of math to share with kids.

Sharing Markov chains and the “COVFEFE” problem with kids

In 2017, the most interesting piece of math I learned can via Christopher Long and Nassim Taleb and related to the “COVFEFE” problem:

Screen Shot 2017-12-11 at 5.05.10 AM

I wrote about the problem here:

The most interesting piece of math I learned in 2017 -> the “covfefe” problem

It turned out that we’ve looked at Markov chains before thanks to this great video from Kelsey Houston-Edwards:

Sharing Kelsey Houston-Edward’s Markov chain video with kids

I’d forgotten about that project, but when I mentioned to my younger son that we’d be looking at Markov chains today he told me he already knew about them!

So, I started today by having the boys watch the PBS Infinite Series video again. Here’s what they thought:

Next I introduced the “COVFEFE” problem. I was really happy how quickly the boys were able to pick up on how Markov chains could be used to solve this problem.

Next we looked at Nassim Taleb’s Mathematica code – that code is so clear that the problem becomes instantly accessible to kids, which is pretty amazing.

Finally, since things were going so well this morning, I introduced the word that we’ll study tomorrow -> ABRACADABRA. The kids were able to see why the transitions in this word were different. I’m excited to see how they think through the “ABRACADABRA” problem tomorrow!

The math behind this problem really was the most interesting math that I learned in 2017. It is really important math, too, and I’m excited that the Mathematica code makes some of the ideas accessible to kids. This was a fun one!

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.

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.