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
A very nice Mathematica file created by Andrew Neitsch in 2005 covers pretty much every aspect of change making mathematics. andrew.neitsch.ca/publications...
Here is a pdf version of this file: andrew.neitsch.ca/publication...
What I cover in the last part of this video is pretty much fleshing out and animating the section "Coin change revisited". All this is part of to Andrew's answer to a post on math.stackoverflow stackoverflow.com/questions/1...
The visual algebra approach to calculate the number of ways to make change at the very beginning of this video was inspired by this article G. Pólya, On Picture-Writing, Am Math Monthly 63 (1956), 689-697. www.jstor.org/stable/2309555
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).
A complete list of all the different ways to make change for a dollar appears in this post www.maa.org/frank-morgans-mat...
The book "Generatingfunctionology" by Herbert Wilf, is a great intro to generating functions :) www2.math.upenn.edu/~wilf/Dow...
Ron Graham to who this video is dedicated did a couple of videos with Numberphile. So if you'd like to see him in action, check out those videos. A lot of other interesting articles about Ron Graham can be found on his wife's (also a math professor) website. www.math.ucsd.edu/~fan/ron/
As usual the music in the video is from the free KZhead 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
A "short" video for a change, "only" 30 minutes long :)
Sir please make a video on collatz conjecture and staircase paradox
For a "change," I see what you did there.
A short video on change
@@candiman4243 dangit I was gonna make that joke
They are never long enough my friend. I could watch these for days.
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.
One of those cases where I wonder if the question setter properly understood what they were asking.
Don't forget to re-compile the formulas for 20p instead of 25c coins and to include 2p.
I'd say the sentence is open for interpretation, "how many different ways can you make £3.10 using coins" is not strictly the same as "given the official GBP coins, what is the maximum number of different ways possible to combine any number of each, to sum up to exactly £3.10". When I read it as a task for a 7 year old, I myself put stress on the word "you", which then makes the question referring to the subjective ability of the girl in question. A little like her English teacher might give her the assignment "in how many ways can you express 'I love my parents'", where the girl will explore her vocabulary, not deduce all possible ways of expressing affection on a certain level using the English language. Feels like the task at hand is great for stimulating her exploration of arithmetic addition of natural numbers, where she herself will create the terms and add them up, as opposed to writing the answer to "3+5=_", "5+1=_", "9+1=_", "2+3+4=_", etc. over and over again. Who knows maybe she'll even bring out some coins on the desk and start playing around, thus naturally start connecting mathematics to the real world around her. In my opinion a great assignment, but I do indeed giggle along seeing the irony when interpreted from some more strictly mathematical perspective.
A child should solve it by brute force. It's not that hard.
@@Craphtex and we have a £2 coin too
"We started with an infinite sum so let's count our blessings" Well it does seem like there are countably many...
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.
He also devised the potrzebie system of weights and measures, the quarter-imaginary numeral system, and named the surreal numbers.
Massive props to the dude
Don’t you mean LaTeX? By yeah, it is the best!!!
@@coleabrahams9331 LaTeX is built on top to TeX. It is basically a set of macros, written in the TeX language.
Yup, amazing man. I notice that you, quite rightly, specify that he's responsible for the professional quality appearance - rather than professional quality content. That's an important distinction. But yes, they do look nice.
I studied the infinite generating function for high school math competitions. They are very useful in combinatorics problem!
Same, but not only in combinatorics problems!
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. I'm not pasting five million digits in here. See pastebin.com/MA2a9p3R 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.
quick answer: a lot
I think its more than 3...
@@bludeat7398 No it is higher than 3.14!
Or none, because there's not enough currency in existence to do it. 🤔
I already knew about generating functions, but seeing that automated algebra and the reason for all those 3s and 0s was seriously amazing
The power of 2 coins can make any amount in exactly one way! (binary representations :))
That was quick :)
@@Mathologer I could hardly wait on seeing a Mathologer video! Still trying to make a program to find the coefficients without using your trick with generating functions
@@subhasishmukherjee9196 Well will be interesting to see what you and others come up with :)
@@subhasishmukherjee9196 I think it's a common problem in dynamic programming
It's cool to see "unique representation in base 2 exists" formulated differently. Works for other bases too, except for example in base 3 you say "I can have 0, 1, or 2 coins worth 1 each, 3 each, 9 each, ..." So the polynomial you have for, say 3 digits in base 3 would be (1 + x + x^2)(1 + x^3 + x^6)(1 + x^9 + x^18) and as expected that is equal to the sum of all x^j for j from 0 to 26 (because 26 = 3^3 - 1) so base 3 numbers can represent natural numbers uniquely too.
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.
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.
Woah, brilliant insight! I couldn't figure it out
Yep. Realised that instantly
In the classic set of hollywood apple crates, you have a 1 inch, 2 inch, 4 inch and 8 inch, which lets you raise whatever it whoever you want to raise any integer number of inches from 1-15.
Base factorial is a thing? Amazing!
i am actually not convinced of this, its true if you limit yourself to having exaxtly 0 or 1 of each coin type, otherwise i could represent 4 as both 2(4)'s or 4(1)'s. since binary doesnt allow for digit values over 1, this excludes a great many other partitions
Last time i was this early, The sum of all natural numbers still equaled infinity
Last time it was this early for me (5 a.m.) was yesterday :)
The last time that I was this early, Kaliningrad had 7 bridges and was still called *Königsberg* !
@@Mathologer On an unrelated note, which do you prefer sir, math or maths? Edit: I really want a t-shirt with your catchphrase - "Cool isn't it?" or "Exactly what we started with!"
it always has been -1/12 source: the astronaut behind you.
@@sofia.eris.bauhaus "Wait there's an astronaut behind me?"
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.
I've been a fan ever since your humble beginning, and I'm more excited than ever for new Mathologer vids!
Actually I always wondered whether KZhead would ever consider making a list of subscribers in chronological order available in a reasonable way. Still waiting :(
Actually, KZhead should have sent you an email each time someone subscribed. If you rank your 647K subscription emails, you will know who subscribed before whom.
@@SaveSoilSaveSoil any reasonable person will have turned that off :)
@@SaveSoilSaveSoil They only send you an e-mail if you tick a certain box and if you've got lots of subscribers you most definitely don't want to tick that box :)
@@Mathologer that sounds more like an argument for filtering your emails through Python
This video makes a lot of cents.
Very funny :)
Oh my god
Mebamme, NO! Go stand in the corner till you learn _'shame'_ ; ))))))))
MAKE GOGOOL CENTS
It's like pennies from heaven!
Glasses: +50 iq Nerdy math t-shirt: +80 iq German accent: +6000 iq
Looks like I've got is all covered :) How about bald vs. Einstein hair ?
@@Mathologer Bald +10IQ No need to scratch head to solve problems 😁
@@dogslife4831 Nice
@@Mathologer Bald → mathematicians Einstein hair → physicists
@@Mathologer Sabine Hossenfelder machte vor kurzer Zeit ein Video zum Thema deutscher Akzent, damit sich das Englisch wie jenes von Einstein anhört ;)
The formula shown at 24:00 works for any dollar amount if you let n choose m = 0 for n
That's it :)
Imagine not getting a heart and reply from Mathologer.
Okay, I have to admit that I was tempted ...
Harry Potter is dead! Huuuh huh huuuuuuuh!
@@gabor6259 Do you too love Harry Potter?
@@coleabrahams9331 Of course.
This is simply a brilliant explanation. Your videos are getting better and better. I am astounded at the ideas and creativity you have in the topics you cover. Thanks!
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)!
This is absolutely mind blowing. Please never stop producing content like this! I absolutely love the channel.
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
Viewer in 2030: "what is "change"?" Viewer in 2040: "what are "dollars"?"
Viewer in 2100: "what?"
@@riadsouissi in 2200: algebra autopilot w -> m h -> a a -> t t -> h
Everyday you upload feels like christmas. I was always fascinated by generating functions. Thanks for the great content as always! Greetings from Germany :)
:) I love this video! I have just been learning about q series! It's so strange how your videos are always surprisingly relevant
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.
This feels like all those math lectures that really made me realize how amazing Mathematics is. Thoroughly enjoyed this, and such a cool result!!
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 sooooo much easier than Quotient rule when it comes to taking more and more derivatives in this case.
ye i agree totally. i just seem to be stuck on the left side somehow. not sure where my error of thought is
@@dramwertz4833 Induction is a better way to do it if you know induction.
This is a really cool video and reminded me of when I first came across generating functions when figuring out the probability in regard to the sums of the outcome of dice, and this actually deepened my understanding of them a bit as they always felt a bit like magic to me.
Loved your dedication, Professor Polster. A side story: I interviewed with Ron Graham years ago for a PhD position at UCSD. While I did not get the offer, my conversation with him is one of my treasured memories.
Thank you, for your videos. "fresh" ideas and content and ton of work behind them.
great video!! I'm really grateful that as a high school student wanting to become a mathematician I have access to such inspiring channels as mathologer and 3b1b, giving beautiful yet still accessible mathematics to sink your teeth in to!
Sir I love all of your videos, gotta admit dont understand some parts of them because I am very not familiar with stuff like the geometric series, but anyway, I just started watching your videos and do really like all the aha moments you give to us to find, and I also love the tightly-knit community. KEEP UP THE GOOD WORK. The long videos make it a tiny bit difficult to watch em but I like em! Thank you!
23:56 It doesn't work for k
Exactly :)
@@Mathologer You had me pondering this for a while. Since I already understood that nCk = 0 when n
@@richardschreier3866 It depends how you define the nCk function and how you choose its domain, I guess? It is quite natural to define it as n!/(k!(n-k)!) and restrict it to integers n ≥ k ≥ 0; but if it is extended beyond that, then these other integer cases normally equal 0 indeed.
Mathologer, wonderful video! You are a legend and you explain things so beautifully.
We are impatient to see the next video, I need more of this great content!
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).
it feels like forever since the last Mathologer video. Good to see you,again.
This will come in useful in the gym later when I am scratching my head figuring out how to load up the barbell.
I love how the 9 flips at 24:45! Lovely video!
This is so fascinating! Really enjoyed watching this video :)
Great video as always, even after chapter 1 I was amazed. Thanks for this :)
Magic all around, not the least in the graphical animations. Wonderful - as always. Viele Grüße!
Choosing _this_ particular t-shirt for _this_ particular topic is a stroke of satirical genius. My highest compliments! (Not just for the t-shirt ;-) )
At university I did a discrete mathematics course which featured generating functions and could never fully wrap my head around why they are such an effective tool for counting. I wish I had this coin example back then, such a great explaination really shows the intuition behind them
Great video! Quite approachable and always enjoyable. 😁 And RIP Ron Graham. ❤️
I thoroughly enjoyed this video, but it definitely reminded me why I've done my best to avoid serious combinatorics :)
Once you get there, it´s so obvious where all those threes come from! (but you have to get there first; thanks for taking us along in this trip)
23:56 I guess that the formula doesn't work because the binomial coefficient "isn't defined" if the number on the top is smaller than the one on the bottom. I think that, if we define the choose function to be 0 in those cases, it works just fine. When you replaced them by algebraic expresions, you indeed set them to be 0 in those cases, so the last formula works in general.
That's it :)
Yep!
This is the most satisfying video of 2021 so far ^^
What a gift! I never expected another video so soon.
Well, this video is a bit shorter than the last couple of videos. That really helps. Sadly semester 1 here in Australia will start at the beginning of March and full-time teaching will again slow me down quite a bit again :(
I always thought Mathologer was in Germany. How surprising!
Hope you will never stop making videos :)
Best thing I watched this week even though it was uploaded 4 mins ago
Amazing video as always!! Love it
Love to watch your videos! Though this time I must admit I could not really follow, probably have to watch it again and stop at many steps to think about. : )
I love this, amazing work !
"One over x-ey looking, aren't they?" is one of my favorite sentences in the English language; thanks professor!
"Do you understand why ? Weeeelll... [insert any magical mathematical tricks here]". Your channel is great ! And thank you for the subtitle, as a non native english speaker it help me a lot to keep concentrate on the demonstration :)
"Coins will be gone soon!" *Laughs in Zinc Lobbyists*
I sure wouldn't want to live in a world without zinc.
@@SirDerpinson you wouldn't, but I think that's what you ment
@@SirDerpinson Come back zinc, come baaack
@@binaryagenda In french zinc is the name of the bar in a bar
Aww, this is sweet!... I knew it, that this clever way of dealing with the coin change problem must have been done already! I've played with this coin change problem recently, deliberetely not knowing about backtracking approach or dynamic programming - I just wanted to see what can I discover on my own (later on, I found that I did not do anything radically new, but I was pleased anyway). I'd loved, of course, to find some formula for it, but theoretical approach was not my goal back then, I just wanted to make my computer to calculate the damn thing. I was not particularly interested in calculating the minimum number of coins (of certain denominations) that add up to a given amount of money, but only in the number of ways such amount of money can be presented. I was also not very keen in writing computer program to do the job, just to make a table, filled with formulae that are calculating everything. The reason for all this is that for many years dealing with various problems I developed for myself a lazy approach to programming - part of the work (a huge chunk of it, if possible) can be done in table forms, another part - with much simpler program, if writing such a program is inevitable, otherwise custom functions are good enough in many cases (I mean, in Excel spreadsheets). So, practising such "programming" style helped me to learn how to compartmentalise any heuristic problem in smaller, more "edible" problems. Firstly, I made a counter that gives me the answer, just for verifying the results (for relatively small amount of money, of course; for bigger ones it has to count for hours). Easy-peasy. The analysis of the problem resulted in following table: 1. The number of columns = the number of 'n' distinct positive integer values (whole numbers), arranged in increasing order as c(1) through c(n); oddly, the results do appear in the leftmost column, associated with the smaller coin in the set, c(1). The set of coins may be whichever one wants {1; 2; 5; 10; 20; 50; 100;...}, {1; 2; 5; 10; 25; 50; 100;...}, or some exotic: {3; 7; 12; 19}, {1; 2; 3; 5; 7; 11; 13; 17; 19;...}. One even can play dumb and use a set as {6; 9; 18; 30}, but the table will give back zeroes for all odd and not divisible by 3 sums anyway. 2. The number of rows is not limited above, with increment of 1 cent per row. Naturally, you should have 100 rows if you want to calculate the function for 1 dollar, or 250 rows if the target is 2 dollars and 50 cents. 3. In every cell [x, y] there is a formula that does one simple thing (for the leftmost column is slightly different) - it calculates the ways 'x' dollars can be presented by coins with nominal value >= c(y): cell[x, y] = sum( cell[x - c(y), j] ) for j = y to n / for 1st column: cell[x, 1] = cell[x-1, 1] + sum( cell[x, j] ) for j = 2 to n. This is all, now every row will give you the corresponding number, for example, in the sequence A000008 (it is only for set [1, 2, 5, 10], doesn't include coins of 20, 50, 100 cents). If we use all coins and banknotes up to 20$ , {1; 2; 5; 10; 20; 50; 100; 200; 500; 1000; 2000}, the sum $20,21 will be presented in 30,399,653,516 ways. Clearly my counter will outlive me here ;-). Now on, the hypothetical program is easy to be written and if one looks closer a little bit on the method, will see that this program will have to memorise maximum n*c(n) numbers to do its job (or even less, if you are greedy), for arbitrary large amount of money. I was delighted that this problem has such simple practical solution, but thankfully, here I learned about the heavy, theoretical stuff, and they are also so elegant. The practical approach has some similarity with Pascal's triangle, so, no wonder that binomial coefficients do appear here and there.
Mathologer is reading my mind... During the last video, I had to make a presentation about tilings, now I have an exam about discrete mathematics including these infinite generating functions in 3 days. Coïncidence? I think not!
Amazing video: I really enjoy it. Thank you Mr. Mathologer.
fantastic video! this may have given me to tools i needed to solve a math problem i’ve banged my head against for years!
Love you mathologer Please make more videos like this
visualizing combinations in ths way is amazing
great stuff as always, thumbs up first time patreon, seeing my name felt real good bit disappointed it was only 30min long rather than full hour
Ron Graham seems to have been a man of many talents. Juggling, out of all things... reminds me of your video on the mathematics of juggling.
as always: EXCELLENT
This is ingenious. Thanks for the video.!
youtube never recommends mathologer.... but, it's a part of youtube we mathologists love.
9:33- I don’t know if it is correct but I think we can make all the integers between 1 and 15 (including 1 and 15) only once. I didn’t use the product it’s just the same idea of binary notation. If you have infinitely many coins with all the powers of two it is the same idea: all the integers only once.
Wow, you never stop blowing me away with your videos! I'd offer you a googol dollars for letting me watch it, but I'm afraid I don't have the exact change!
Yes I very much indeed love algebra autopilot, the music, the pace, the ending...
This channel is the jewel of youtube
Lots of marvelous generating functions-- moment generating function, Laplace transform, Fourier transform, and my personal fave, probability generating function. A bunch more that I don't know, I'll bet.
Amazing video as always
Great explanation! Thank you (nice t-shirt, by the way)
"And of course we also get that one way of making zero sense". I chuckled a few times throughout the video :)
You are amazing! Love your videos.
As some one familiar in computer science, the 1, 2, 4, 8 question comes easy answer as all the binary representation of numbers from 1 to 15. Using the (1+x), (1+x^2), (1+x^4), (1+x^8), it can be seen by multiplying all with (1-x), we will get (1-x^16), and divide that of (1-x), we will get (1+x+x^2+x^3+...+x^15), aka the same answer. This is such a very interesting connection between polynomials and binary numbers!
I believe I left a similar comment on the previous video, but the book Analytic Combinatorics covers the topic of this video extensively. It was the main reference of a class I took last year, though the introduction was through Knuth’s Concrete Mathematics.
The change-making problem, when dealing with small numbers, is a good introductory problem when learning dynamic programming. You define a two-dimensional array dp[i][j] = (the number of ways to make i cents using only the first j denominations). Then it satisfies the recurrence dp[i][j] = dp[i][j-1] + dp[i-value[j]][j]. A common optimization is to note that each row only depends on the previous row, so it can be implemented using only a one-dimensional array. But you still need an array as big as the total amount you're trying to make. Another approach is to compute column-by-column. In this case you need to keep track of a number of values in each row equal to the corresponding denomination, as sort of a sliding window. The key is to notice that the operation of sliding the window can be expressed as a matrix multiplication. The size of the matrix is equal to the sum of the denominations. The repeated matrix multiplications are just a matrix exponentiation, and there are efficient algorithms for matrix exponentiation that will let you efficiently compute the result even when the total amount is as big as googol. For an interesting programming challenge, see how far you can optimize things when the denominations that happen to be relatively prime (yes, I know, a highly impractical money system).
Touching dedication to Ron Graham at the end of the video ❤️
Loved the counterpoint music at the end.
*reads how to make googol dollars* Nobody: Bill Gates and Jeff Bezos:That’s not a dare, that’s Tuesday.
I like the idea of coins with powers of 2. Having coins of 1, 2, 4 and 8 allows us to make charge for all values up to 15. It is basically binary numbers. If each coin is a bit and you have 4 of those bits (1, 2, 4 and 8) you can make charge for 0 to 15, exactly 2^4=16 different amounts.
Really much entertaining and informative. 🤗🤗🤗
Great dedication..! 💙
13:27 I would guess there is a O(N^2 * M) dynamic programming approach for that (N = the amount we want to partition, M = the number of distinct coins). I will assume we have a sufficient amount of every coin type. Let's define count(i, j) as being the number of ways to partition i dollars with the first j coins (coin values are sorted in ascending order). Then count(0, j) = 1 for all j and count(i, 0) = 0 for all i. The recursion comes out to be count(i, j) = count(i, j-1) + count(i - c[j], j-1) + count(i - 2*c[j], j-1) + ... The answer will then be stored in count(N, M). If you do some clever stuff with the memoization, the time complexity can also be reduced to O(N * M), I think.
Hey Burkard, thank you for your amazing videos, now that's my fav Friday night entertainment! Just out of curiosity, what kind of software do you use to make such a beautiful animation (and how much time does it take to prepare a video like this one?) Thanks!
23:56 Challenge for k = 0, so long as we define (n choose k) = 0 for all k > n
Wonderful as usual.
Those crazy polynomials are going to hunt me in my dreams
@@masonhunter2748 I would have to factor it in my sleep
9:12 You can get change for all amounts smaller than the next power of 2 after the last available power. So with 1, 2, 4 and 8, you can get change for all amounts from 1 to 15 cents (smaller than 16). And, there is exactly one way to get change for each of those amounts, which corresponds to the fact that all numbers have a unique binary representation (representation in base 2).
Thanks for putting out such great content. This is way better than my video on generating functions. Do you have any tips for someone with a new math channel looking to improve?
The first time I encountered generating functions was when I was having fun filling up paper charting how many vertices, edges, faces, etc. there are in a line segment, square, cube, 4-cube, etc. and finding the patterns. I showed this to a math teacher, and he was like, “or you could find the coefficients of (2 + x)^n.” (Where n is the dimension of the cube, and the power of x is the dimension of the face.) I was blown away and mystified and had no idea how it worked. To find the k-faces of an n-cube, you doubled the k-faces of the (n-1)-cube and added the (k-1)-faces of the (n-1) cube. Which shows that (2+x)*f_(n-1)(x)=f_n(x). And f_1(x)=2+x, because you start with a line segment, with 2 vertices and 1 edge. So you have proof by induction. You could even start with f_0=1, and start with a single point (Pointland). But the proof by induction isn’t that satisfying, and doesn’t quite bring a greater understanding. I’ll look into it tomorrow morning.
Using the coin counting trick, we have the product (1+x)(1+x²)...(1+x^(2^n)) If we multiply the product by (1-x), we have (1-x)(1+x)(1+x²)...(1+x^(2^n)) = (1-x²)(1+x²)...(1+x^(2^n)) = (1-x^(2^(n+1))) So the product is (1-x^(2^(n+1)))/(1-x) Notice that this is equivalent to the geometric sum 1+x+x²+...+x^(2^(n+1)-1) So there is exactly one way to make change for values from 1 to 2^(n+1)-1 (This can be visualized in binary)
That's it. Nice, isn't it?
Once again, great work, Mathologer! However, I see a tiny error there in the distribution of terms at 4:22 You would expect the empty set in the "first column" in the cross product, but you made the leading empty terms disappear (except for the very first partial product). In Mathematica, by the way, it would look like this: with Distribute[{{}, {1}, {1, 1}, {1, 1, 1}}, {{}, {3}, {3, 3}}, List, List] you get {{},{}},{3}},{{},{3, 3}},{{1},{}},{{1},{3}},{{1},{3,3}},{{1,1},{}},{{1,1},{3}},{{1,1},{3,3}},{{1,1,1},{}},{{1,1,1},{3}},{{1,1,1},{3,3}}} Anyway: a very exciting topic! As a chemist, I see great applications there: e.g. if you ask for the possible elementary compositions for a given (exact) molar mass, you can get all conceivable "sum formulas" this way (and with a few chemoinformatics tricks even the valid molecular formulas). Looking forward to future videos! Here are a few "wish titles": Polya-enumerations of isomers, automorphism groups of graphs or even solving functional equations.
Thanks so much for the video!
9:30 As a CS major, I can tell you that you cannot make any duplicate values with these coins. This is the same thing as binary, each of those coins is a power of 2. It's the same thing has having 4 bits of information. You can make values 0 to 15, but there is no permutation which makes duplicate values. There is exactly 1 representation for each possible value. But I understand why people might not realize that immediately looking at the question. It's not a common intuition, it's something you learn.