Tag counting

A good (though tricky) introductory counting problem

My older son is re-working his way through Art of Problem Solving’s Introduction to Counting and Probability. He came across a problem in the review section for chapter 5 that gave him some trouble. I decided to talk through part of it tonight and included my younger son.

My younger son hasn’t been studying any counting lately, so I was expecting the problem to be pretty challenging for him. His work through the first part of the problem is, I think, a nice example of a kid working through a challenging math problem.

The problem is this: How many different ways are there to put 4 distinguishable balls into 3 distinguishable boxes?

The next problem is what was giving my son some trouble: How many different ways are there to put 4 distinguishable balls into 3 indistinguishable boxes?

My younger son struggles with the problem for a bit on this one and then my older son offers his thoughts. What gives my older son a little trouble is the case in which you put 2 balls into one box and 2 into another.

So, after struggling with 2-2-0 case in the last video, we talk about it in a little more depth here. The tricky part is seeing that two cases that don’t look the same are actually the same. It was harder for the boys to see the over counting than I thought it would be. But, we made it!

So, the indistinguishable counting part was pretty confusing to the boys. I think we need to do a few more problems like this to let this particular counting concept sink in.

James Tanton’s counting problem part 2

Yesterday we looked at a really neat problem James Tanton posted last week:

That project is here:

Working through a challenging counting problem from James Tanton

Our first look at the question involved some dice rolling and a computer simulation. Today we are going to look at an exact solution to the problem. That solution involves studying all of the different things that can happen when you roll 5 dice. It turns out that there are 7 different patterns that can happen, and these patterns related to the ways you can write 5 as the sum of positive integers.

(1) 5 different numbers, which I’ll represent as 1 + 1 + 1 + 1 + 1

(2) 3 different and 2 the same -> 1 + 1 + 1 + 2

(3) 2 different and 3 the same -> 1 + 1 + 3

(4) 1 different and 4 the same -> 1 + 4

(5) 1 different and 2 pairs -> 1 + 2 + 2

(6) 1 pair and 1 triple -> 2 + 3

(7) All numbers the same -> 5

For today’s project we’ll count the number of ways that each of these 7 patterns can occur. We know that the total number of arrangements is 7,776, so that’s going to help us make sure we have counted correctly.

Here’s the introduction to the problem and to the approach we are going to take today:

Now we began to count some of the arrangements. In this video we count the number of dice rolls in (1), (4), and (7) above:

Now we moved on to some of the more challenging arrangements. Here we looked at (6) and (2) above:

Now we looked at case (5). This case proved challenging because dealing with the 2 pairs caused a little confusion between over counting and under counting. But, after looking at the cases carefully we did manage to get to the answer.

At this point we had only one case left -> (3) from above. But, the counting practice that we’d had up to this point helped this case go pretty quickly.

Finally, we added up our numbers and checked that we’d found all 7,776 cases. We did!

The one thing left to do was to count the different numbers that we saw in each case and find the average. I’d done that ahead of time just to save a bit of time in the movie. Our final answer was (27,906) / (7,776) or about 3.588. The exact answer was (happily!) very close to the two estimates that we had found in our simulations yesterday.

I love Tanton’s problem. It is a great estimation problem as well as a great counting problem. We might do one more project tonight on yet a different way to solve the problem using Markov chains:

Looks like a fun idea – I’ll be thinking about how to talk through this approach with the kids during the day today.

Working through a challenging counting problem from James Tanton

I saw a neat problem from James Tanton during the week:

A follow up post from Amy Hogan made me realize that I should use the problem for a project:

So, I decided to make looking at this problem our weekend project. Today I wanted to try a few simulations. Tomorrow we’ll count the cases. That case work is pretty challenging, but I think we’ll be able to get through it.

Here’s the introduction to the problem:

Next I had the boys roll 5 dice 50 times and record the numbers they saw each time. Here are those results as well as our first estimate of the answer to Tanton’s question:

Finally we moved on to do a simulation. Normally I would have used Mathematica, but I’ve got a program related to one of our old Goldbach Conjecture videos running right now. This problem was easy enough to deal with on Excel, though, so I looked at a simulation there.

Here’s what they saw in the numbers:

Definitely a nice start to this project. Counting the different cases tomorrow will be a bit more difficult, but we’ll also get to talk about some pretty interesting mathematical ideas like partitions and choosing numbers. I’m excited to see if we are able to get all the way to the end.

A challenging counting problem for kids learning algebra

My son is in a weekend enrichment math program and that program has been great for him. It comes to an end this week. The last problem on this week’s homework assignment gave him some trouble, so I thought it would be fun to see if we could work through it together.

I was a little worried because I’d not seen the problem until just before the project, but luckily things went ok.

Here’s the problem:

a, b, c, and d are positive integers less than 10. How many solutions are there to the equation a + bcd = ab + cd?

[post publication note: Originally the text presented the problem incorrectly. It is correct in the videos. Karen Carlson pointed out the typo to me. Sorry about that.]

Here’s how we got started – my son had found several cases, but not quite all of them:

After the introduction to the problem and my son’s work so far, we moved on to try to find more solutions. The main idea I gave my son involved writing the equation in a slightly different form:

Now that we had a plan, we moved on to counting the rest of the cases that we found in the last video:

Finally, we went to Mathematica to write a little program to count the solutions for us. This part of our project turned out to be more interesting than I was expecting. It was interesting to compare the brute force solution of the computer to the case by case counting technique that we’d just gone through.

So, a fun problem that definitely made my son think this week. It is

Studying shuffling and Shannon entropy part 2

img_1908

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.