Grid with 100 Paths

Due to current circumstances, the National Council of Teachers of Mathematics (NCTM) had to cancel their Centennial Annual Meeting and Exposition, which was to be held April 1-4 in Chicago. As a replacement, though, they presented an amazing gift to the math education community — 100 free webinars led by selected speakers from the Chicago program. Dubbed 100 Days of Professional Learning, these webinars are to be held on select days from April through October.

As part of the 100 Days, I presented “100 Problems Involving the Number 100” on May 14. To celebrate NCTM’s 100th Anniversary, I collected or created 100 problems, each of which included the number 100. One of my favorites, Dog Days, looked like this:

From this information alone, what could you determine?

At the end of the webinar, the conversation continued “backstage” with several members of NCTM staff, NCTM President Trena Wilkerson, and me. During that conversation, Trena made the outlandish suggestion,

Now we need a collection of 100 problems for which the answer is always 100.

I had just finished preparing a webinar with 100 problems, and now she was asking for another 100 problems. But never one to shy away from a challenge, I began to think about what kinds of problems might be included in such a collection. One type that came to mind was path-counting problems, like this one:

Moving only north or east on the segments in the diagram, how many distinct paths are possible from A to B?

That particular grid, measuring just 3 × 4, has fewer than 100 distinct paths from A to B. (How many paths, exactly? That’s left as an exercise for the reader.) What got me excited, though, was wondering if there were any grids that have exactly 100 paths — and hence providing 1% of the content for the collection that Trena requested.

As it turns out, there are no unmodified m × n grids that have 100 distinct paths. But what if some segments were removed? For instance, what if one of the middle vertical segments were discarded from a 4 × 6 grid, as shown below? How many distinct paths from A to B would there be?

As it turns out, a lot more than 100. (Again, finding the exact number is an exercise I’ll leave for you. If you need help, Richard Rusczyk from Art of Problem Solving has a video showing how to count paths on a grid.)

So, this is where I leave you:

Can you create a grid with some segments removed that will have exactly 100 distinct paths?

Have fun! Good luck!

As for the webinar, which lasted only 60 minutes, there wasn’t nearly enough time to cover 100 problems, but we had fun with 5 of them.

If you missed the webinar, you can hear the discussion about the Dog Days problem and 4 others, as well as get a PDF of all 100 problems, via the links below.

• Webinar Recording
• Webinar Chat
• Webinar Slides
• Webinar Handout

Enjoy!