Explaining the bizarre pattern in making change for a googol dollars (infinite generating functions)

Okay, as it says in the title of this video, today's mission is to figure out how many ways there are to make change for one googol, that is 10^100 dollars. The very strange patterns in the answer will surprise, as will the explanation for this phenomenon, promise.

0:00 Intro
1:15 Chapter 1: curious count
9:05 Chapter 2: googol
14:10 Chapter 3: infinite change
28:41 Acknowledgements

Concrete mathematics by Graham, Knuth and Patashnik, the book I mentioned at the end of the video does the whole analysis for the coin set 1, 5, 10, 25, 50 (so no dollar coins).

As usual the music in the video is from the free YouTube audio library: No. 2 Remembering her by Ester Abrami, Morning Mandolin by Chris Haugen, First time experience and T'is the season by Nate Blaze

Today's t-shirts: google "only half evil t-shirt".

Enjoy!

Burkard

[Mathologer]

A "short" video for a change, "only" 30 minutes long :)

[KusacUK]

As we’re all home-schooling at the moment, the school is sending challenge sheets out to all the kids. The final question on my daughter’s maths one was “how many different ways can you make £3.10 using coins”.

She’s 7 years old...

I just changed the question to “think of a few ways you could” instead, because even I didn’t know how to solve it. But now I do! I don’t think I’ll be teaching this to her yet though.

[AlRoderick]

"We started with an infinite sum so let's count our blessings"

Well it does seem like there are countably many...

[suqichen]

I studied the infinite generating function for high school math competitions. They are very useful in combinatorics problem!

[thedoublehelix]

I already knew about generating functions, but seeing that automated algebra and the reason for all those 3s and 0s was seriously amazing

[maxwchase]

Programming challenge (did this around 13:41): because all of the coins evenly divide a dollar, it must be the case that a sum of coins to a multiple of a dollar can be separated into some groups of coins in which no single denomination adds up to a dollar, and the rest, in which each single denomination adds up to a multiple of a dollar. The former cases can be enumerated by doing the product trick without the exponent of 100, and taking the coefficient of each exponent divisible by 100, including 0. There are ways to make change like this for zero through four dollars inclusive. This gives us one part of the solution. The other part is to determine how many ways the remainder could be made. But this is a simpler problem, because it's equivalent to asking "How many ways are there to add five (number of denominations - 1) boundaries to a set of a given size" which is equivalent to asking for (size of set + 5) choose 5, which can be hard-coded as a sequence of multiplications followed by a division. (I could have tried expanding out the polynomial explicitly, but that sounds like effort).

So, the final answer is to, for each amount of dollars that can be made without using a dollar's worth of a single denomination, multiply that by the number of combinations for the remaining dollars.

I coded this up in Python, and it's pretty fast. I just started added zeroes to the exponent on the ten, and it was pretty acceptable performance up to 2 * 10 ^ 100, 000. I'll post the value for 2 * 10 ^ 1, 000, 000 when it finishes, because that's much slower. Okay, yeah, that took a few minutes. One sec... Oh geez, it overflowed the buffer.


EDIT: At 23:02 I'm seeing the same coefficients in the center row that I had my program calculate for "ways to make dollars without a single denomination adding up to a dollar" So I guess this is going in the same direction.

[WillToWinvlog]

I've been a fan ever since your humble beginning, and I'm more excited than ever for new Mathologer vids!

[kotschi]

Having coins worth 1, 2, 4, 8, ..., 2^n each exactly once will allow you to represent each number up to 2^(n+1) - 1 exactly once, because it's just the binary represantation of that choosen number. It will work for any number system in general. As long as you've got enough coins to fill up each digits place to its maximum, you will be able to represent each number up to the next digits value minus 1.
For example:
- 2 coins worth 1, 2 coins worth 3 and 2 coins worth 9 can represent each number up to 26 in base 3 exactly once and
- 1 coin worth 1, 2 coins worth 2, 3 coins worth 6 and 4 coins worth 24 can represent each number up to 119 in base factorial exactly once.

[BrentDeJong]

The formula shown at 24:00 works for any dollar amount if you let n choose m = 0 for n<m, which is a natural definition. It only falls apart when you expand the formula.

[Xubono]

Some of us will recognise Donald Knuth as the creator of the typesetting language TeX. For that alone, he has been responsible for the professional quality appearance of thousands of PhD theses.

[gabrielmel]

Extremely cool! Made me realize there’s a very practical strategy for handling these problems that, in my opinion, beats the pure programming AND pure math approach: programming this sort of thing correctly is nontrivial, and even with a smart implementation isn’t that fast (my quick and dirty python version takes about 20 seconds for $2500 - I just remembered I only bothered with 1, 5, 10, and 25 cent coins). The pure math approach to obtain a closed form expression through generating functions is mechanical and straightforward (and beautiful) but incredibly unwieldy for generating functions of this size. Even if you use Mathematica to do the algebra, you still face the problem of convincing yourself you didn’t make a mistake in writing the code! My approach, inspired by your video, is to simply observe that since the generating function is a rational function, its coefficients will be exponentials times polynomials in the index (and I think a bit more reasoning gets you to the fact that if you only extract coefficients with the same residue mod 100, they’ll just be polynomials (as you show for residue 0, of course)). For N coins, this polynomial will be of degree N-1. So pages and pages of computer algebra, in the end, are just to get N rational numbers! A much more direct way is to write a piece of code that is just barely fast enough to deliver N values of the function, and then solve the resulting linear system for the coefficients of the polynomial! No need for super slick iterative implementations, which will top out way before a million of dollars anyway; no need for huge amounts of algebra. Fast, easy, and delivers an essentially O(1) algorithm for a huge number of problems (ie. anything with a rational generating function, so anything produced by a finite state machine)!

[johnchessant]

21:15 "Oh wow, this formula implies that the coefficients for 5n, 5n+1, 5n+2, 5n+3, 5n+4 must be the same!"
*thinks about original problem for a minute*
... Oh.

[subhasish-m]

The power of 2 coins can make any amount in exactly one way! (binary representations :))

[matthewjensen]

Wow... I liken watching Mathologer to watching Bob Ross. I’m watching a man explain something far beyond my capabilities but just listening to him talk about something he loves and the intricacies therein is beautiful. I can follow the minutia but I can’t keep track of all of it. It’s just lovely watching these long strings of equations getting simplified and expanded and simplified again. Never stop, Mathologer, never stop.

[Jordan-zkwd]

There's something beautifully simple about this, once you get to the end it just feels completely obvious that it works. Love all your content, definitely helps me to see things in different perspectives and to engage with problems better! Now and then I get into little mathematical rabbit holes of my own and end up taking between a couple weeks and months to intermittently chip away at them til I get somewhere satisfactory, I actually just got started right now on a new such thing and probably am gonna have to break into programming cause the spreadsheets won't cut it. Thanks for the inspiration <3

[tobiasgorgen]

Last time i was this early, The sum of all natural numbers still equaled infinity

[wompastompa]

For anyone working on the problem at about 16:20 with derivatives, do yourself a favor and use (1-x)^(-1) instead of the fraction. Power rule & Chain rule is much easier than Quotient rule when it comes to taking more and more derivatives in this case.

[rafaelmoreira]

8:58- I think it is 292 (one less the result you gave us due to the fact we exclude the possibility of using the 100 cent coin).

[Matiburon]

This was a particularly fun one. I feel like I was able to follow pretty much every part of the proof. Enough hand-holding for casual viewers but no tricky stuff shoved to the background.
Even the algebra autopilot is fun to watch, as its pace and animation make it easy to understand and apreciate the cleverness involved. Many channels like to focus more on geometric proofs only (which are also nice) but algebra has some charm too.

[hewhomustnotbenamed]

Imagine not getting a heart and reply from Mathologer.