I moved recently, and my new place is a bit farther from choir practice than the old one was. My walk there has gotten longer, giving me more time to lose myself in thought as I meander over. What better subject to ponder than the walk itself? Specifically, as a mathematician, I would like to find the optimal route between my home and choir practice.
My old place was almost due north of choir practice, so there weren’t a lot of options for how to walk there. The new place, though, is eight blocks north and six blocks west. The streets are on a grid, so any route that goes south for a total of eight blocks and east for a total of six will get me to choir practice.
The routes are all basically the same length, so I’m not looking to minimize distance. Instead, I just want to find the most pleasant commute: the one with the fewest growling dogs, the best places to cross busy streets, and the prettiest landscaping to admire as I pass. I don't know a shortcut for figuring out my optimal commute, so I just need to try all the possibilities. I don’t want to backtrack on my route, so I want to figure out how many ways I can walk 8 blocks south and 6 blocks east going only south and east.
I know a little bit about combinatorics, the branch of math that deals with counting combinations and permutations of decks of cards, students in chairs, or in my case paths to choir practice, but I'm not an expert. Yet as I pondered this question on a recent walk, I realized it was hauntingly familiar. In fact, I had just solved it on Project Euler a few months ago. Project Euler is a fantastic database of math problems that require some programming to solve. I’m pretty new to programming, and Project Euler is a great place for me to get fun questions to work on and practice my Sage skills.
Question 15, “Lattice paths,” asks us to find the number of different routes from the top left to the bottom right of a 20x20 grid moving only down and right.
With slightly different numbers, this is exactly the question I wanted to solve to figure out how many possible routes there are to choir practice.
So what's the answer? Well, the first rule of Project Euler is that you do not talk about Project Euler. Or at least about how you solved a Project Euler problem. As the homepage states, “Real learning is an active process and seeing how it is done is a long way from experiencing that epiphany of discovery. Please to not deny others what you have so richly valued yourself.”
For that reason, I won’t tell you how many paths there are or how I figured it out. (And if you figure it out, please don’t spoil the fun for anyone else.) I will say, however, that my mathematician spouse and I came up with an elaborate solution that ended up being far from the fastest way to solve the problem. While I felt a bit silly when I saw a more streamlined answer and realized how obvious it was in hindsight, our method revealed a new (to me) identity in combinatorics. I can’t really be mad about that.
The method I used to solve the Project Euler problem applies perfectly to the case of the walk downtown, so I now know how many routes I need to try before I can pass judgment on which one is the best. Let’s just say I have plenty of
work walks cut out for me.