Welcome to another Mathologer video. Do you still
use coins? Not much right? In fact many experts predict that coins will be abolished altogether
in the not too distant future. Heads or tails will be dead and gone. Very sad. But there's this
really beautiful change making mathematics that I've been meaning to show you since day one of
Mathologer. And pretty soon there'll be no point. So before I lose my chance entirely I'll sneak
in a quick video on coin maths. In particular the goal of today's video is to answer one of
the most burning questions on shoppers minds: how many ways are there to make change for one
googol that is 10 to the power of 100 dollars. The answer to this question is very surprising and the
explanation for the answer even more so, promise. In particular, i'll use infinite series
in a very ingenious way to count that huge but definitely finite number of ways to make
change for a googol. And believe it or not all this change making maths will actually stay
very applicable even in the future without coins. I'll come back to that point
at the end of the video. Ok a little mathematical warm-up to get us going.
Ready no coins up my non-existing sleeves :) have a look at the monster product over there. First
bracket 1 plus x plus x squared all the way to x to the power of 100. Second bracket again
all the way to x to the power 100 but the exponents going up in multiples of 5. There
5, 10, 15, … 100. And so on. Multiples of 10 in the bracket of the next exponent right there
10, 20 all the way to 100. Next one is there 25 all the way to 100. And 50 and finally to a little
bracket 1 plus x to the power of 100. Cool. Now expand this monster product. Go on I’ll wait. Or
maybe not :) but a piece of cake for a computer. There that's the output. So the result is 1
plus x plus x squared plus goes on for a while there all the way to x to the power of 600.
What a monster. Now for the magic let's wave our mathematical wand and zero in on the
number in front of x to the power of 100. There 293 big deal. Just another number right?
Wrong! 293 is exactly the number of ways to make change for a dollar using standard u.s. Coins
those ones over there. 1, 5, 10, 25, 50 and well 100 cents. How does this work? Well those
numbers definitely feature prominently in the product we started with. There the exponent
in the different factors are all the multiples of the six different numbers up to 100. All
clear? No? No problem let's have a closer look. Let's start small. Let's figure out what amounts
of money we can make with three one cent coins and two three cent coins and then how many
different ways we can make those amounts. Okay first just using the one cent
coins what can we do? There, tricky. Yep you can make one cent, two cents and
three cents. Well actually by being really stingy we can also make zero cents.
Right same with our three cent coins. No coins give zero cents, one gives
three cents, and two gives six cents. Now here comes the first really cool bit. To get
everything possible using both types of coins we simply visually multiply the two
sums. So there multiply term by term and pretty magical. And pretty obvious that
this will give all possible ways of combining up to three one cent coins with up to two
three cent coins. Now just tidy up a bit all those extra nothings in the top row
are really superfluous so let's zap them. Neat, we've translated finding all those
combinations into algebra. Now to find out what amounts we've made let's add up. For example
1 plus 1 plus 3 plus 3 is 8 and so on. But how can we do this adding up automatically. Well
the way we've pictured things makes it look like we're multiplying those coins rather than adding
right. Here is a neat idea. What if we use powers? Can you see why? Well products of powers
translate into sums of the exponents. Have a look. So the exponent 8 is exactly the coin sum we noted
earlier. Okay let's do this everywhere. There. Okay now let's add up. And everywhere else.
So there we got three in two different ways. And those two ways are automatically
recorded by our weird coin algebra, there goes the two. Same thing here. Two ways
to make six. Another two there. Okay the black circle up there stands for nothing,
so zero and x to the power of 0 is 1. So wrapping it all up what
does this polynomial tell us? What it says is that with three one cent coins
and two three cent coins we can make one cent in one way, okay, two cents in
one way, three cents in two ways, and so on, and of course we also get that one way
of making zero cents there right at the beginning. And remember this is the strange
coin product we started with. Or swapping the coins for powers this is what
we started with. Pretty cool and it's easy to see that this works for any combination of coins.
For example if we add a single 10 cent coin to the mix the product that will do the trick is this one
there. Okay back to the product we started with. Can you decipher the product now and
figure out the corresponding coins? Well the first bracket means we have 100 one cent
coins to play with, a dollar's worth. Okay next bracket we have a dollar's worth of five cent
coins. Then a dollar's worth of 10 cent coins, and so on. There 25 50 100. Got it? But what if we
include more coins? Well remember we were asking about the number of ways to make change for a
dollar. And for that question including more coins can't make any difference, right? For example the
greatest number of one cent coins we can possibly use is 100, so using more one cent coins than 100
with which we began won't give any more ways to make change and this means that the coefficient
of x to the power of 100 that 293 is exactly the number of ways to make change for a dollar.
Pretty damn ingenious isn't it? I love this stuff. What else do all these numbers over there tell us?
Well let's have a look at the previous terms. This tells us that there are 252 ways to make change
for 99 cents and also 252 ways to make change for 98 cents. In general all the coefficients for
powers up to 100 will give the exact number of ways to make change for those corresponding
amounts. For the powers beyond 100 cents the coefficients are lower than the total number of
ways to make change. For example that 292 that goes with 101 cents doesn't account for the one
way of making change with 101 one cent coins. Here at the end only one way of making change
for 600 cents is covered using all our coins. Of course there will be zillions more. Okay to
finish this chapter here are some challenges for you. First how many ways are there to make change
for a dollar if we don't use 100 cent coins. That's an easy one right. Okay now for a slightly
more challenging question and a nice aha moment. Say you've got one one cent coin, one two cent
coin, one four cent coin and one eight cent coin. What cent amounts can you make with these four
different coins and in how many different ways? For maximum aha impact try to solve this puzzle
using the weird product I showed you earlier. Well what if, as well, you use one 16 cent
coin one 32 cent coin and so on, one each of all the other infinitely many power of two
coins? Leave your answers in the comments. What's this up there. Yep the multiplication
table. You are of course very familiar with it. And there is nothing that you don't know about
it right? Well let's see. Mental mathematicians and lightning calculators will memorize well
beyond the 10 times table. They are looking at something like this. Have you taken this bird's
eye view before? The extended multiplication table exhibits some curious patterns. Can you see the
different shades of gray. What are those? Well let me highlight the different regions that are
jumping out at us there. What's the explanation for these regions? You've got it? No? Well let's
zoom in on one of the edges between regions. Okay zoom zoom zoom. So the regions are formed
by the products with different numbers of digits and the edges are where we jump from a
certain number of digits to the next number. Makes sense. And what about the shape of the
boundary curves? Ring a bell? Yep they're pretty hyperbolic 1/xeee looking aren't they?
And it's actually really easy to see that these curves are approximately hyperbolic. Right?
If this is the x-axis and this is the y-axis, then this border between three-digit and
four-digit numbers is approximated by the curve with equations x times y equals the
smallest four-digit number one thousand. Or y is equal to one thousand over x. Hyperbolic
great. Anyway there's a lesson to be learned. Even if we know how something works in principle
and we're familiar with the little examples, taking things to telescopic extremes may produce
some real surprises. This also turns out to be the true for the change giving puzzle. Let me show
you. Remember we figured out there were 293 ways to make change for a dollar. What about making
change for ten dollars? Want to take a guess? Two million a bit ways to make
change for ten dollars. Let's see how this plays out when we go even
bigger. There there getting pretty big. Yep the numbers are huge but can you also see
a strange pattern emerging? Let me highlight the pattern for you. There amazing right? From
one thousand dollars on we get the same numbers separated by strings of threes and zeros.
It turns out that this extends to infinity and along the way there we get the
answer to our original question: what is the number of ways to make change for
googol dollars. Here is the monster answer. Very impressive and totally unexpected isn't it?
Take a moment to let this sink in. Got it. Right. Actually what I just showed you is impressive
in another way. How did I calculate those huge numbers in the first place? Hmm, well in principle
our product trick, as well as other brute force enumeration tricks will work for any amount of
dollars. So to apply the product trick you just have to adjust the maximum exponent. There for
two dollars we would use this larger product. But as we go larger and larger even the
computer will quickly begin to get scared of the amount of calculation to be done. So here
is a double challenge for my programmer friends. Try to come up with an efficient program that
computes the number of ways to make change for full dollar amounts and then use it to continue
this sequence over there. For your program anything goes you don't have to use the product
trick. If you think you've got a better idea. Tell us about your discoveries in the comments.
Also let us know how far you can push things before your program and computing setup starts
to take over an hour to produce the next answer. How close to two times a googol did you get?
Not very close I promise :) okay so computers get us so far. How far does our brain
get us? Let's find out together. Okay our goal is to prove that crazy formula
for googol change. But before we get into it I think I'd better highlight two basic facts to
make sure we're all on the same page. Fact one the formula for the sum of an infinite geometric
series. Very familiar right? That one has come up in Mathologer videos about a googol times. And
remember that the formula only works for values of x between -1 and 1. For fact two we quickly have
to remind ourselves about binomial coefficients, that n choose k thing. Probably easiest to just
write down an example like nine choose four. All right the pattern is clear, right? Four
factors going up in the denominator and four factors going down in the numerator. Also if the
number at the bottom is zero then the binomial coefficient is equal to one. Now fact 2 is this
formula here let's bring it in. There ponder it for a moment. You've got it? Well it's possible
to prove the second formula up on top by raising both sides of the first formula to a power of n.
It's obvious that this works on the right side. There the orange is the nth power of the green. To
show from scratch that the left side of the second formula is the nth power of the first formula
is also not terribly hard. Just quickly for n is equal to one all the binomial coefficients
get a zero at the bottom and so are equal to one and so for n is equal to one the second formula
is really just the first formula. Nice. Maybe give squaring and cubing the left side of the first
formula a go to prove the formula for n is equal to two and n is equal to three. Actually there's
also a much much easier calculus based proof. Simply differentiate the first formula below n
minus 1 times on both sides and you arrive at the second formula on top. If you are comfortable
with calculus you should definitely treat yourself to proving the formula this way. Anyway for what
follows we'll really only need the special case n is equal to 6. So I might as
well highlight that for you now. Okay so when I spring this on you in a
minute or two you won't be surprised, right? Now with these two formulas under our belt
we are ready to explain those long strings of threes and zeros in the numbers of ways
to make change for powers of ten dollars. To do this let's see how far we can push the
product trick. Then we'll push a little further:) as we've seen the product over there gives the
number of ways of making change for a dollar. Upping the power from 100 to 200 gets us the
number of ways to make change for two dollars, and so on so. Let's think big and
take this all the way to infinity. So expanding this crazy product should give
us all the ways of making change for all possible amounts. But how can we expand this
product? Well have a look at the first factor. Looks familiar doesn't it? Our first formula
tells us that this factor is equal to 1/(1-x). Here's the second factor. Aha do you see the
trick? Yep this is just the first formula again, but with x to the power of
5 in the role of x, right? Plugging x to the power 5 into the first
formula gives this. There plugging in is this. And of course all the other factors in our
crazy product are equal to similar fractions. Which means that our crazy product is equal to
this product of fractions. Okay that looks a lot simpler than the crazy product but does
it help? Not so clear, right? The idea is to massage this expression a bit until all six
denominators are the same. After that it turns out we can apply our second formula. Let me show
you how this is done using some algebra autopilot. Don't worry too much about the details. If you get
the general idea of what's going on that's plenty. Don't you just love algebra autopilot? :)
and things are now all primed to use our second formula and apply it to the bit in orange.
There let's just do it. Cool. And now a bit more massaging. First take a deep breath, cross your
fingers and expand the big product in the middle. Just brute force nothing ingenious going
on there. Okay degree 81 polynomial 82 terms. Don't get to deal with something like
that every day. And yes it's scary but remember we started with a big product of infinite sums.
So all in all maybe count our blessings. Okay the name z has served its purpose. Let's
switch back to x to the power of five. How are you going? Hanging in there? Well almost
there, promise :) let's remind ourselves what it is that we're looking at. What we have here
is the original crazy product consisting of six infinite sums massaged into a product
consisting of the two finite sums at the top and that infinite sum at the bottom. Okay
now let me show you how you can derive from this massaged sum a formula for the number of
ways to make change for full dollar amounts. After that i'll use this formula to explain
the mysterious expanding strings of threes. To begin let's figure out the number of ways to
make change for four dollars, that is 400 cents. For this we have to pinpoint the
different ways to pick one term each from the three factors whose powers of
x combine into x to the power of 400, now one way sticks out right: 1 times 1 times
x to the power of 400 is x to the power 400. If that was the only way to produce x to the
power 400 then there would be exactly those blue 9 choose 5 ways to make change for
400 cents. But there are others. Take a look at the second factor in the middle.
This factor contains four terms with multiples of 100 as exponents. There those ones. That means
we can also make x to the power 400 like this. One times x to the power of 100 times x to the
power of 300 equals x to the power of 400. Here's another way and another way and another way. But
that's it. Maybe pause the video and think about this for a moment. What I just pulled out are
the only ways to produce x to the power 400. But this means that the number of ways
to make change for 400 cents is this. But actually there was nothing
special about four dollars or 400 cents. Exactly the same reasoning shows
that the general formula for k dollars or k times 100 cents, the 100 is
really important here, is this. Actually that's not quite true. This is the
formula for all k greater than three. The formula doesn't work for n is equal to one, two, and three
at least not straightaway. Challenge for you: why doesn't the formula work for those small
dollar amounts? And how can we adapt the formula to make it also work for these amounts?
Leave your answers in the comments. Now just a bit more algebra autopilot to hammer
this formula in the simplest possible form. Pretty amazing. Not the prettiest polynomial
ever but after all the gymnastics with infinities flying this way and that, that's
a surprisingly simple formula. Impressed? I know you are. All right now for the
final dash to the peak. Let's use this formula to explain the expanding strings of
threes. Okay a bit more algebra autopilot. Okay ready for some grand finale magic. Great
sub in k is equal to one hundred thousand. Then all those powers of k on the
far right will also be powers of 10 and so we'll just be moving the decimal points of
these numbers on the right by different amounts. And that is where all those threes come from.
What a nice aha moment, don't you think? Okay mission accomplished. Next time you have to make
change for a googol dollars you know what to do :) let me just end with three remarks. First remark.
You may think that with coins soon to become an endangered species all this nice maths i've been
talking about today will soon become obsolete. That's not the case at all. In fact some of you
may already have realized that change making maths is really part of the incredibly applicable theory
of integer partitions the topic of my recent video on Euler's pentagonal number theorem. Imagine
that you have an unlimited supply of coins of all possible integer denominations: one cent
coins, two cent coins, three cent coins, etc. Then the question of how many ways you can
make change for n cents is exactly the same as asking in how many different ways you can write
the number n as a sum of positive integers. Well that may still sound like no big deal but it
is. To find out why this question is so important and why Euler and Ramanujan are featured in the
logo of the video over there check out the video. Second remark. The trick of first interpreting
a sequence of numbers as the coefficients of an infinite power series and then investigating
the sequence by manipulating the power series is very powerful in mathematics indeed. If you'd
like to find out more what's possible in this respect googol the term generating function. Of
course we'll also revisit this circle of ideas again in the future. I've also included some links
in the description of this video. Final remark. I first learned about change making maths
from the brilliant book concrete mathematics by mathematical heavyweights Ron Graham
and Donald Knuth and oren Patashnik. An absolutely beautiful and fun must read
by some genuine giants. A book all about combining continuous maths, that is calculus, with
discrete maths. The result- concrete mathematics. There’s even fun in the title. I've never met
Donald Knuth or Oran Pataschnik but I do know Ron Graham, that is I did know Ron Graham. Ron
passed away last year aged 84. Ron was an absolute amazing mathematician and an all-round great
guy with many many interests and accomplishments in and outside mathematics. You may be familiar
with graham's number which is a lot bigger than googol even in googolplex or if you're a
juggler you may recognize him as one of the past presidents of the international jugglers
association. Anyway let me take the opportunity to dedicate this video to Ron Graham. And that's all
for today. I hope you enjoyed this video and I'm looking forward to all your solutions to today's
challenge problems. Until next time stay safe.
