A great counting problem for kids involving binary

This summer I’m slowly working through Art of Problem Solving’s Introduction to Counting and Probability with the boys. I though it would be fun to see them working together and since I haven’t covered this subject with either of them previously I was hoping the age difference wouldn’t be that big of a deal. So far so good.

Flipping through the challenge problem section in Chapter 2 earlier this week I ran across this wonderful problem from an old ARML:

If you write the integers from 1 to 256 in binary, how many zeroes do you write?

Definitely too difficult for a homework problem for either of them right now, but it struck me as a great problem to use for one of our weekend Family Math projects. Some parts were more difficult than I expected, but the kids remained engaged all the way through. It was really fun to see them talking through some of the more challenging details as well as listing out binary numbers with the snap cubes. Although this one is a little more challenging and a little longer than a normal Family Math project, I’m really happy with how this project turned out. I think it would be incredibly fun to work through this problem with a large group of kids.

We began by simply discussing the problem which, not surprisingly, meant a short review of writing numbers in binary. My younger son understood that 256 was a power of two and would be written as 1 followed by a bunch of zeroes. How many zeroes exactly was the starting point to today’s discussion:


Next was a neat idea from my older son – to solve the problem we want to break it down into easier cases. His first guess at a way to break the problem down was to organize the numbers by the number of 1’s they have. An interesting idea for sure, and one that works well for numbers that only have one 1. Unfortunately breaking the problem into these cases gets complicated fast. After we do a bit more work with permutations and combinations it might be pretty fun to return to this idea, but for today we walked down this road a little bit and discovered it is a pretty tough way to go.

Since this video is a little long and has nothing to do with how we eventually solve the problem, it is ok to skip it. However, I think it is really important to try out ideas like my son had here. Learning how to identify when an idea is working out and when it isn’t is a really important lesson:

Next we moved to our kitchen to look a little more closely at what binary numbers look like. We used snap cubes to “write” a few numbers in binary. Looking at the list we decided to group the numbers by number of digits and see if that helped us count the zeroes.

At the end of the last video we formed a conjecture that the number of zeroes in our 4 digit binary numbers would be 9. In this next video we write out the numbers using our blocks and discover that we have 12 zeroes in the 4 digit binary numbers rather than 9. We then talked through how we could see the 12 zeroes as 3 groups of 4. The boys struggled a little to see the three groups of 4 that made these 12 zeroes, but eventually saw it and understood it. That led to another conjecture:

After the last video they were really engaged with this problem. We were guessing that we’d find 32 zeroes when we wrote out the 5 digit binary numbers. The boys spent about 10 minutes off camera building these numbers out of snap cubes, and we did indeed find 32 zeroes. We then talked for a bit about why the pattern we found makes sense. After the video was over I mentioned one extra reason that we could see why half of the digits (not counting the left most digit) were zero – the last 4 digits are the same forwards and backwards if you reverse the colors. That helps us see that for every yellow block we have a black block that can be paired with it.

Finally we went back to our big whiteboard to add up the results. Nothing super special going on here – we write down all of the cases and add up the numbers. The kids thought we’d need a calculator, but we somehow managed to add up the numbers without one!

As I said at the beginning, I thought this problem would make a great project to work through with the kids. Although it was a little long, I’m really happy that we worked through this one. Certainly this was one of the most challenging problems that we’ve gone through together, but since the kid remained engaged all the way through, I’m super happy that we gave this one a shot. Again, I’d love to go through this with a large group of kids.

What a fun start to the day today!