Tag counting

Studying shuffling and Shannon entropy part 2


We did a fun project about Shannon Entropy and Shuffling yesterday:

Chard Shuffling and Shannon Entropy

That project was based largely on an old Stackexchange post (well, comment) here:

See the first comment on this Stackexchange post

Today I wanted to extend that project a little bit and thought it would be fun to look at a different kind of shuffle to see if there was a difference in entropy.

Here’s the shuffle for today as well as what the boys think will happen with this shuffle:

Next we took some time off camera to enter the card numbers in our spreadsheet. Here’s what we found for the new entropy after one of these new shuffles:

Finally, we took even more time off camera to do 4 more shuffles and write down the order of all the cards. After that we did 5 successive shuffles and wrote down the numbers after the 10th shuffle.

The kids didn’t think the cards were as mixed as they were in yesterday’s project, and here’s what the entropy calculation said:

I really enjoyed these two projects. It was especially fun to see how kids could get their arms around the idea of entropy even though the math itself is pretty advanced.

A neat expected value problem from Expii

[sorry for the quick write up – I got asked to help out with my son’s archery class today, so I just decided to publish this one as it was when I get asked to help . . . ]

I saw a neat expected value problem from Expii yesterday. In case you’ve not see their site, here’s the link to their main site:

Expii’s front page

and here’s a direct link to the problem:

A neat expected value problem from Expii

The problem goes like this:

“You are planting some trees as environmental action for Earth Day. At each of 200 spots around a circle, you place a seed. Each seed will sprout into a small tree with probability 1/2. Sadly, some of these small trees will die. In particular, a small tree dies if it has another small tree as its neighbor, because they will be fighting for sunlight.

What is the expected value of the number of trees that are still alive at the end of the year?”

I thought this would be a great problem to discuss with the boys. We just got back from a vacation in San Diego and my younger son was still on west coast time, though, so I just talked through this one with my older son.

First I introduced the problem and we double checked that he understood it:

Next we discussed some simple cases to see if we could get our arms around the problem:

Now we moved on to the general case. My son understood some of the main ideas about the problem, but made a small mistake at the end that led to a very small expected value.

Finally, we wrapped up by looking at the error at the end of the last video and trying to calculate the expected value slightly more carefully:

A fun math question about Snapchat from a friend

Last night a friend asked me a fun question about Snapchat:

“Say [our group]] has 26 people in it, but Snapchat has a limit of 16 in a group. How many groups would need to be created so that everyone is in a group with all of the [people in the original group]?”

It was fun to think this one through.

My thought process solving the problem went like this:

First I drew a picture of the people sitting around in a circle and thought about how you might chop them up into groups of 16. The picture below shows two groups of 16 -> one group has the people numbered 1 through 16 and the other has the people numbered from 11 to 26.

At this point I thought that since two groups of 16 had an overlap of 6 people you would need 5 sets of two groups to be sure that all everyone matched with everyone else. The reason, I thought, that you couldn’t do it with fewer was that 4 groups x 6 people = 24 and you needed to get to 26.

But then I realized you could do better than my initial idea of having 5 sets of two groups. My new idea was to make a third group containing the people numbered 1 through 8 and the people numbered 19 through 26. The new cut is shown in the picture below.

After making that group, all I need to do is pair people 9 and 10 with people 17 through 26 and then pair people 17 and 18 with people 1 through 10. That solves the problem with 5 groups.

Yay – with a little thought I’ve cut the number of groups from 10 to 5.

But can you go lower than 5?

My next try looked like this picture:

So, the same two starting groups as before, but now my 3rd group paired people 1 through 6 with people 17 through 26. Now only people 7 through 10 were not paired with everyone and it only required a final group of 14 to pair them with people 17 – 26. Those 4 groups paired all 26 people in the big group with everyone else.

So, great, I’m was now down to 4 groups, but could I get to 3? A little math says no (I think!).

With 26 people you are going to have to make a total of 26*25 / 2 = 325 connections if you want to pair everyone with everyone else. That’s because each person needs 25 connections, but each connection pairs two people (so, I don’t need to connect A to B and then later also connect B to A – that’s why you can divide by 2 in the formula above).

Similarly, each group of 16 will produce 16*15 / 2 = 120 connections. Since 120*3 = 360, maybe there is a way that you can produce the 325 necessary connections with just 3 groups.

However, the overlapping people in the groups are a problem. Two groups of 16 will always contain at least 6 of the same people. Since the connections involving those 6 people are getting double counted (and there are 6*5 / 2 = 15 of them), adding a second group of 16 can’t produce 120*2 = 240 total connections, but rather at most 120 + 120 – 15 = 225 connections. Now, since the 3rd group will have at least 6 overlaps with each of the previous two groups, with 3 groups you can have at most 225 + 120 – 2*15 = 315 connections.

But you need 325 to have everyone connected with everyone, you can’t get there with three groups. So, 4 is the minimum and the method shown starting with the 3rd picture above shows one way to do it with 4. There are probably many others.

Fun little problem 🙂

Returning to inclusion / exclusion

We’d taking a break from our inclusion / exclusion project but I wanted to return to it tonight. I picked a fairly challenging problem from one of my old math books:

How man 5 card poker hands have at least one card from each suit?

I didn’t have any idea how it would go . . .

We started by reviewing the ideas in inclusion / exclusion and the moved on to try to get our bearings in the problem:

Having formed a pretty good plan in the first video, we moved on to tackling the rest of the problem.

I’m really happy with how this went. It is fun to see the boys learning to break complicated problems down into problems that are slightly easier to deal with.

Revisiting a counting project for kids that I learned from Jim Propp

For our math project today we returned a tiling idea that is a really fun idea for kids to explore. Here are a few of our prior projects on the subject:

A fun counting exercise for kids suggested by Jim Propp

Counting 2xN domino tilings

Screen Shot 2016-08-13 at 9.25.29 AM

Today the plan was to look at 2xN tilings first and then move on to tilings of 3xN rectangles with 3×1 dominoes.

We stared by exploring some simple 2xN cases and looked for patterns:

In the first video we counted the number ways that we could tile 2×1, 2×2, 2×3, and 2×4 rectangles with dominoes. Now the boys noticed the connection with the Fibonacci numbers and we tried to find and explanation for why the Fibonacci numbers seemed to be showing up here. The nice thing is that the boys pretty much got the complete explanation all on their own.

Now we moved on to counting the tilings of a 3xN rectangle using 3×1 “dominoes” – what would be different? What would be the same?

One really interesting thing here is that my older son and younger son came up with different ideas for how to count the general arrangement.

So, in the last video my older son had a counting hypothesis that I couldn’t quite understand. In the beginning of this video I have him explain his process more carefully. The surprise was that for the 3×6 case we were looking at next both of their counting procedures predicted the same number of domino tilings.

In this part of the project we tried to follow both procedures to see how they worked.

Having sorted out the counting procedure in the last video, we now looked carefully at the 2xN and 3xN tiling procedures and saw that we could compute the number of tilings for the 2×100 and 3×100 cases if we wanted to.

I’d love to come up with more counting projects for kids. These projects are accessible to young kids and I think shows of some really fun ideas from advanced math that kids probably don’t usually see in school.

A neat counting problem I saw on Twitter today

Saw a fun problem in this sequence of tweets today:

Seemed like a great problem to cover with the boys tonight. They had some pretty good ideas right from the start:

Once they had the idea for the first 100 numbers down we moved on to trying to find the 1000th number with no 5’s or 7’s. Their approach was a little different from how I would have proceeded, but it was nice to see their idea. They also noticed and avoided a little trap right at the end 🙂

Really happy I saw this problem today. Excited to get the book when it comes out.

A challenging but super instructive inclusion / exclusion example

My son had a really interesting problem as part of the homework for an enrichment math program he’s in. I’m writing this post from the road so I don’t have the exact statement of the problem in front of me, but it went something like this:

You are going to make 7 digit numbers using the digits 1, 2, 3, . . . , 7 exactly once. How many of these numbers have no consecutive digits with common divisors?

So, for example 1,234,567 is a perfectly fine number, but 2,413,567 doesn’t work.

My son’s solution was nice, but complicated. He found the number of ways to separate the even numbers (there are 10) and then found the ways to fill in the odd numbers in each of those cases.

I couldn’t find an easier solution and wondered on Twitter if there was one. One response I got pointed me to a similar problem that was discussed on the Art of Problem Solving problem forum:

Looking through the thread I stumbled on a really clever inclusion / exclusion solution. Since we’ve been taking a closer look at inclusion / exclusion ideas I thought it would be fun to step through this solution with the boys. I think this a really instructive inclusion / exclusion example. One thing that was a little tough for the boys to understand was that the elements we were “excluding” were pairs of integers.

Also, just to be clear, I’m not expecting the boys to have a complete understanding of this solution. Rather, I just wanted to show them an inclusion / exclusion example that had some interesting twists.

So, we started by introducing the problem because my younger son hadn’t seen it before:

Next we dove in to the inclusion / exclusion solution. The “no restrictions” case is easy! Seeing the way to express the restrictions is pretty challenging. Once we understood that case we looked at subtracting away the cases with 1 restriction.

Next we looked at the 2 restriction case. Now things get really tricky – the fact that we have now have pairs of pairs of numbers is one bit of confusion. Another bit of confusion comes because one pair of pairs is not like the others.

Finally we looked at the case with 3 restrictions. This part, I think anyway, is really cool. The surprise is that several of the cases are impossible!

Despite being a very challenging problem, I love this problem as an inclusion / exclusion example for kids. No individual piece is beyond their reach and if you walk through the problem slowly everything is accessible to them.

A fun shape for kids to explore: the Permutohedron

I learned about permutohedrons from a comment by Allen Knutson on a prior blog post. See the first comment here:

A morning with the icosidodecahedron thanks to F3

I prnted the shape from Thingiverse and it was amazing!

“Permutahedron” by PFF000 on Thingiverse

We started the project today by examining the shape and comparing it to a few other shapes we printed. The comparison wasn’t planned – the other shapes just happened to still be on the table from prior projects . . . only at our house 🙂

Next we talked about permutations and the basic idea we were going to use to make the permutohedrons. We drew the 1 dimensional version on the whiteboard and talked about what we thought the 2 dimensional version would look like.

We used our zometool set to make a grid to make the 2 dimensional permutohedron. Lots of different mathematical ideas for kids in this part of the project -> coordinate geometry, permutations, and regular old 2d geometry!

Next we went back to talk about how PFF000’s shape was made. Here’s the description on Thingiverse in case I messed up the description in the video:

“The boundary and internal edges of a 3D permutahedron.

The 4! vertices are given by the permutations of [1, 3, 4.2, 7], with an edge connecting two vertices if they agree in two of the four coordinates. The 4D vertices live in a 3D hyperplane, namely the sum of the coordinates is 15.2.
Designed with OpenSCAD.”

This part of the project was a little longer, but worth the time as both the simple counting ideas on the shape and the combinatorial ideas in the connection rules are important ideas:

Finally we wrapped up by taking a 2nd look at the shape and also comparing it to Bathsheba Grossman’s “Hypercube B” which was also still laying around on our project table!

This was a really fun project that brought in many ideas from different areas of math. I’m grateful to Allen Knutson for the tip on this one!

The airplane seat problem

For today’s Family Math project we talked through a classic probability puzzle:

An airplane has 100 seats.  100 passengers are going to board and each one has an assigned seat.  The first person to board ignores the assigned seat requirement, though, and chooses a seat at random (including the 1/100 possibility of actually choosing the correct seat).  After that, everyone else boards taking their assigned seat if it is open, or choosing a seat at random if their seat is taken.  What is the probability that person #100 sits in their correct seat?

Here’s how I introduced the problem to the boys:

At the end of the last video my younger son suggested studying a smaller problem first. He picked though the case with 4 people would be easier – and it would! I suggested starting even lower than that, though, so we started with just one person:

After seeing a pattern in the smaller cases we went back to try to tackle the larger case. We had a little bit of confusion, though – and that confusion may have been only on me misunderstanding what my son was saying! – so we cut this movie a bit short to return to the 4 person case:

Returning to the smaller case with 4 people, my son clarified his argument. That argument was, essentially, an induction argument which was really cool! The boys were able to explain how you extend the same argument to the case with 100 people. Nice solution!

At the end we talked about another fun feature of this problem – what are the possible seats that the last person might sit in?

It is always fun to go over a famous problem. This time was an especially nice discussion surprise since the induction argument was an out of the blue surprise! I think this is a fun problem to talk through with kids.

Sharing John Cook’s Fibonacci / Prime post with kids

Saw a neat post from John Cook about using a fun fact about the Fibonacci numbers to prove there are an infinite number of primes:

Infinite Primes via Fibonacci numbers by John Cook

Funny enough, we’ve played with the Fibonacci idea before thanks to Dave Radcliffe:

Dave Radcliffe’s Amazing Fibonacci GCD post

That project was way too long ago for the kids to remember, so today we started by just trying to understand what the Fibonacci identity means via a few examples:

Next we looked at the idea from Cook’s post that we need to understand to use the Fibonacci identity to prove that there are an infinite number of primes. The ideas are a little subtle, but I think the are accessible to kids with some short explanation:

We got hung up on one of the subtle points in the proof (that is pointed out in the first comment on Cook’s post). The idea is that we need to find a few extra prime numbers from the Fibonacci sequence since the 2nd Fibonacci number is 1. Again, this is a fairly subtle point, but I thought it was worth trying to work through it so that the boys understood the point.

Finally, we went upstairs to the computer to explore some of the results a bit more using Mathematica. Luckily Mathematica has both a Fibonacci[] function and a Prime[] function, so the computer exploration was fairly easy.

One thing that was nice here was that my older son was pretty focused on the idea that we might see different prime numbers in the Fibonacci list than we saw in the list of the first n primes. We saw quickly that his idea was, indeed, correct.

This project made me really happy 🙂 If you are willing to take the Fibonacci GCD property for granted, Cook’s blog post is a great way to introduce kids to some of the basic ideas you need in mathematical proofs.