We've already seen in a lot of counting problems that there's often more than one way to get the answer. That is, there's more than one way to get from point A to point B. And in this problem, that's going to be the whole point, is to count the number of ways to get from point A to point B. Now we could start off just by finding paths and just counting them off.
Here and then here is one, here and then here is two, here and then here is three, here and then here is four, here and then here... Did I count that one? Um, I'm not...
I'm not... Well, I don't think I did. And then there's here and... did I count that?
Hmm. Uh oh. If I just kind of just list them off, well, first of all, I might forget which ones I've already counted and count things twice. And then, second of all, how will I know when I'm finished? How will I know I've found them all?
I'm going to have to get more organized, find another way to do this. Well, first what I'm going to do is I'm going to make it a simpler problem. Look at it and see if we can make a simpler problem, because we like simpler problems.
And one way to make it simpler is let's just forget about y and z for a minute, and focus just on x. And we see that to go through x to get to b, well, we have three ways to go from a to x. Amen.
two ways to continue on to B. So that means to get from A to B through X, we have three ways to go from A to X, and for each of those we have two ways to go on to B, so there are 3 times 2, 6 ways to go from A to B. In the same way, we can count the paths through Y.
One way to go from A to Y, four ways to continue on to B. The total of 1 times 4 is 4 ways to go from A to B through Y, and we just do the same thing. down here at z.
Two ways to get to z. For each of those we have five ways to continue on to b. And now we have the number of ways to get from a to b through x, through y, and through z. And these are the only possibilities, so all we have to do is add these up.
And we can be sure, we can be sure that we've counted all the paths here because we have to check two things. Two things, First of all, Is every single possible path counted here? Every single path must go through x, y, or z. So every single path is in one of these three cases. Second, we have to make sure we haven't counted any path twice.
And every path goes through either x, y, or z. It can't go through two of them. So each path is counted exactly once.
Once and only once. So what we've done here is what I'll call casework counting. We've listed out our cases. We made sure they didn't overlap, and we made sure that every single possible path fits into one of these cases. Now, every single casework counting problem you do is going to look exactly like this.
You're going to list out the cases. You're going to make sure everything you want to count falls into exactly one of these cases. So, everything you count will fall into one of the cases, and no two of the cases will overlap. So, everything gets counted once and only once.
And in theory, this is the way. This is the way it works. Now, as Yogi Berra said, in theory there's no difference between theory and practice. But in practice there is. So we're going to get a little more practice.
And we're going to do that with a problem that I thought of when I heard a very, very famous, famous story about two outstanding mathematicians. It was a great moment in geek history. The two mathematicians were G.H. Hardy and Ramanujan.
And Ramanujan was a... was a prodigy in India, late 1800s, early 1900s. And he produced a lot of wonderful, wonderful mathematics. And he started sending some of his math, some of the theorems he came up with, to a lot of very prominent English mathematicians. And at that time, Hardy was one of the most famous.
And when Hardy saw his work, he was amazed by it. Some of the theorems that Ramanujan came up with, Hardy not only had never seen before, but couldn't even prove them himself. And he figured, well, you know...
These theorems must be true because if they weren't true, no one would ever have the imagination to invent them. So he invited Ramanujan to come to England, and the two of them worked together for quite a while and produced a lot of wonderful mathematics. Now, while Ramanujan was in England, he got sick once, and he was in the hospital, and Hardy went to visit him, and Hardy was pretty upset when he got there because he figured the number on the cab, it was an ill omen. It was an ill omen because the number on his cab... What's boring?
Nothing interesting about this number. And Ramanujan looked at it and said, What do you mean? That's a wonderful number. It's the smallest number that can be written as the sum of two positive cubes in two different ways. Great moment in geek history.
You'll have to figure out what those two different ways are yourself. But this inspired me to think about a math problem. I figured, you know, Ramanujan's definitely smarter than you and me put together.
I don't doubt that. But I wasn't so sure that this was a case of of Ramanujan being smart. Maybe it was just a case of him, you know, knowing that there are just a few numbers that can be written as the sum of two cubes. So I decided to count them. How many numbers, and I just went up to a thousand, I didn't want to go crazy here.
How many numbers less than a thousand can be written as the sum of two positive cubes, and we don't care if they can be written in two ways. I'm happy with just one. You know, maybe there aren't many of these. So of course I just started from one.
1 can't be written as the sum of 2 positive cubes. 2 can. 2 is 1 cubed plus 1 cubed. That's pretty easy.
3, no. 4, no. 5, no. 6, no. 7, no. 8, no. 8 is 2 cubed. 9 can. 9 is 2 cubed plus 1 cubed. 10, no. 11, no. 12, no. 13, no. 14, no. 15, no.
This is ridiculous. I mean, it's going to take me forever to get all the way up to 1000. Once it gets higher, I won't really know for sure if... a number can be written as the sum of two positive cubes. Maybe instead I'll just start with cubes and just start adding them together and see what I get.
I already saw that 1 cubed plus 1 cubed works and 1 cubed plus 2 cubed. I can do 3 cubed plus 4 cubed. I think that's 27 and 64. Yeah, that's way less than 1,000.
5 cubed plus 7 cubed. Does that work? 1,25.
3,43. Yeah, that's less than 1,000. Let's try 9 cubed.
plus 11 cubed. Oh, that's definitely not going to work. 11 cubed is more than 10 cubed, and 10 cubed is 1,000, so this one doesn't work. 8 cubed plus 9 cubed, 512, 729. No, that's not going to work either.
This is going to take forever, too. Not only that, how will I know when to stop? How will I know I have them all? This isn't going to work.
I'm going to have to get more organized. And the first observation I can make in getting more organized is, well, a thousand. Ten cubed is a thousand, so I can't use ten or any number higher than ten as one of my cubes.
So that already eliminated a bunch of numbers, so I don't have to think about those. So the first number I'm going to have to think about coming down is nine. So I'm going to have to think about nine cubed. And nine cubed is 729. And I can subtract that from 1000 to see how much I have left over. I have 271. So I can add 9 cubed to any cube that's less than 271. And I'll get a number that's less than 1000. So now I just have to find the cubes that are less than 271. And we know how to do that.
We can just check them. 8 cubed is too high. 7 cubed is 343. That's too high. 6 cubed.
216. That works. So I can add 6 cubed. I can add 5 cubed. And so on down to 1 cubed. So there's six ways to do this.
This is promising. So now I can take another step down. I've already taken care of nines.
So all my nines are accounted for here. I can look at the ways to have 8 as one of my cubed. 8 cubed is 512, so I can't add it to itself.
That'll give me a number higher than 1000. But I can add it to 7 cubed, because that's 343. And that means, of course, I can add it to all the smaller ones, down to 1 cubed. Which means there's 7. This is good, this is good. So now I can go into 7 cubed.
And 7 cubed is 343. And we saw that we can add it to 8 cubed. Oh, wait, I made a mistake there. I have to be careful. I'm setting up my cases here. I don't want my cases to overlap.
I've already got 8 cubed plus 7 cubed here. I don't want to count it again. So I'm going to get rid of that.
And I'm going to define my cases by the largest cubed. The largest number we have cubed. cubed, so my 9s.
This is the one where 9 is the largest, these are the ones where 8 is the largest number that I'm cubing, so for 7, I have to start at 7 and go down. And 7 cubed plus 7 cubed, well that works. And so on down to 1. So there's 7 there.
And then for 6 cubed, I have the same thing. I know that I'm not going to use 9, 8, or 7 because I've already counted those. So I'll start from 6 cubed plus 6 cubed and go on down to 1. Give me 6. And similarly, for 5, 5 cubed down to 1. There's 5 there. They're 4 with 4 cubed, 3 with 3 cubed, 2 with 2 cubed, and only 1 left with 1 cubed. And now I have all my cases.
First of all, I can be sure that I've counted every single possible sum of 2 cubes that's less than 1000. All of them are in this list, because I know there are none with 10 or higher. I've got all the ones with 9 as the largest cube, all the ones with 8 as the largest, 7, 6, 5, and all the way down to 1. This is nice and organized. I know that every possible sum of cubes that's less than a thousand is in this list somewhere. Second, I know that there's no overlap.
I know that there's no sum that pops up twice here. First of all, I know that there are no eights anywhere lower than this. There are no sevens anywhere lower than this, and so on.
But second, I know that I don't have seven cubed plus six cubed equals eight cubed plus four cubed. I know that that won't happen. And how do I know that? that because of...
what Ramanujan told us about 1729. Ramanujan told us that 1729 is the smallest number that can be written as the sum of two positive cubes in two different ways. So I know that there's not some number that's going to pop up twice in this list, so I don't even have to add all these up to make sure there's no overlap. So now I can just tally up my cases and I'll get the total number of numbers less than a thousand.
that can be written as the sum of two positive cubes. And there it is. I just add it up. 1 through 4, that's 10, 15, 21, 28, 35, 41. So we have 41 numbers.
Less than a thousand can be written as the sum of two positive cubes. And just imagine there are probably a bunch more going up to 1729, so it's... Probably not the case that Ramanujan sat there and knew all the numbers that could be written as the sum of two positive cubes. That said, he is smarter than you and me put together, so maybe he did.
Now again, look at our strategy here in using casework. Clearly defined cases, every single possibility falls into one case, no two cases overlap. In other words, we're counting everything once and only once.
Bye.