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.
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.
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.
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.
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)!
Actually I always wondered whether TH-cam would ever consider making a list of subscribers in chronological order available in a reasonable way. Still waiting :(
Actually, TH-cam 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 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 :)
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.
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.
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.
@@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.
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
@@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
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.
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.
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 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!
Everyday you upload feels like christmas. I was always fascinated by generating functions. Thanks for the great content as always! Greetings from Germany :)
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.
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.
"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 :)
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.
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!
Choosing _this_ particular t-shirt for _this_ particular topic is a stroke of satirical genius. My highest compliments! (Not just for the t-shirt ;-) )
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.
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!
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!
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
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.
9:14 pretty obvious that it is a representation of a binary number. You can also generalize to be n-1 coins each of powers of n. Take n=10 you will be familiar of base 10 number system. 23:57 Not sure if it "doesn't work" because we haven't defined C(n,r) = 0 when n < r? The formula should work for k
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).
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).
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)
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 :(
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.
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.
23:57 The cases k=0,1,2,3 are problematic because then 4/3/2/1 of the binomial coefficients have an upper number smaller than 5. But doesn't this actually compute nicely without changing the formula since the binomial coefficient x choose y is zero for all x
Hi, I was thinking about an interpretation of the formula at 21:20. Imagine that whenever you have $1 worth of the same coin then you MUST put it in its own coin bag. Like those bags we used to have to deposit change into a bank. Then the binomial coefficients describe different combinations of coin bags the can make up each whole dollar, while the finite polynomial is the count for the leftover loose change. Taking the product covers all possibilities. Does that work?
13:25 it's fast Fourier transform. Have no idea how is it related to Fourier transform with complex integral, but FFT is algorithm calculating product of polynomials faster, you can find video in 3b1b-style(it was made with manim), explaining the work of such algorithm. Due to many zeros in polynomial it could be advanced to better work
For the programming challenge for dollar amounts, this is how I might try to calculate it: if a_n is the number of ways to make change for a value n coin using 1, 5, 10, 25, 50, and 100 value coins, I have the recurrence a_n = a_(n-1) + a_(n-5) + a_(n-10) + a_(n-25) + a_(n-50) + a_(n-100). (a_k for k < 0 is 0 and 1 for k=0). You could then just use the recurrence relation to calculate the first however many terms in the sequence. If you wanted a closed formula for a_n, Because each a_n depends linearly on the last 100, you can find a (sparse) 100x100 matrix of 0s and 1s that when applied to the vector [a_n, a_(n-1), a_(n-2),..., a_(n-99)] results in the vector [a_(n+1), a_n,...,a_(n-98)]. Then you could convert this to Jordan canonical form and find the change of basis matrix. In principle, you could figure out the formula for raising each of the Jordan block matrices to the n-th power, then use this to find a closed form expression for a_n. I have a feeling that the latter method might be very inefficient, and susceptible to round off error or something like that.
The reason why the formula around 23:00 doesn't work for k < 4 is that we have some extra options we should not have due to the way the formula was derived. For the k={1, 2, 3} cases one must not include the terms higher than k*100. The general formula works beacause there is only limited [and fully utilized] choices for 1st and 2nd part of the product only one valid chice raimains for the infinite 3rd part. While the 3rd part is infinite it behaves well. Only 5 of the terms work at the time. when including quite simple corretion factor. For k = 1 we have: (1)* (1)* (6*x^100) + (1) * (287*x^100) * (1) = (6 + 287) * x^100 = 293 *x^100 For k = 2 we have (I'll skip all the ones): (21 + (287 * 6) + 985 ) * x^200 = 2728 *x^200 For k = 3 we have: (56 + (287 * 21) + 6* 985 + 325 ) * x^300 = 12318 *x^300 For k > 3 we have (C representing the combinations operator and done before multiplications: ( 1*(k +5)C5 +287*(k + 4)C5 +985*(k+3)C5 +325*(k+2)C5 +2*(k+1)C5 )*x^(k*100) Now we can see that for k < 4 we use only k + 1 first terms of the general solution.
That's it :) An easy way to fix the formula is to define binomial coefficients with top < bottom to be equal to zero (makes sense when you think of Pascal's triangle surrounded by a sea of 0s :)
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!
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.
9:49 has the interesting conclusion that 1/(1-x)=sum[x^i,{i,0,Infinity}]=product[(1+x^(2^i)), {i,0,Infinity}] (at least if i didnt do anything wrong). very nice!
9:45 just from eyeballing the question, I can pretty clearly see that the answer is that you can make 15 different amounts (16 if you include 0) and they're all made in a unique way. What's more, if you have n coins, you can make every value in a unique way up to 2^n - 1 (Again, 2^n if you include 0). You can do this just like if you were counting in binary, which uses the powers of 2 to uniquely construct every whole number. Pretty cool if I do say so myself!
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!
9:48 As a computer person, it is *instantly* obvious this is binary. But to answer the question, using coin values of the first n powers of two (where the first is 2^0, or 1), you can make all integer amounts from 0 to (2^n)-1 [inclusive], each in exactly one way.
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.
Great video! The answer of how many ways of summing any number (equivalent to make change with coins of all numbers) does not come following the same argument/procedure without much troubles?
Trying to solve the problem at 9:08 without actually doing maths, I would say instinctively there is exactly 1 way to make any amount between 0 and 15. I haven't calculated this, but I'm fairly sure I'm right this time since this looks very very similar to counting in binary. Using more power of 2 coins you get exactly 1 way to make any amount between 0 and (2^x)-1, where x is the number of coins used. This is very interesting way to describe binary counting, so thanks for that.
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. : )
23:58 Choose function is undefined for negative values, but we can easily generalise known formula using generalisation of factorial - gamma function. Then everything works out nicely
Something like this. Actually the only thing you have to do is to extend the definition of binomial coefficients: anything with a top less than the bottom is set to 0 :)
9:08 With one of each of the first n powers of 2 coins, you can make any amount up to 2^(n+1)-1 exactly one way. This is like the base 2 representation of natural numbers in (I believe it's called) positional systems, which we use with arabic numerals. There's a general theorem for this, so, for example, you can make any amount up to 3^(n+1)-1 with TWO of each of the first n powers of 3 coins (1, 3, 9, 27, etc...) exactly one way; the obvious example is NINE of each of the first n powers of 10 coins (1, 10, 100, 1000, etc...). ^.^
22:59 Why not take x^2 from the first 1 from the second x^200 from the third? Or x^4 from first, 1 from second and x^100 from third etc.? IMHO there are more terms giving x^400 than the ones you showed. Am I missing something?
Does anyone know where i can find the music that plays during the algebra autopilot (19:35 for example)? Amazing video, i am looking forward to try these challenges!
Sorry if this was asked (too many comments to go thtough), but at 23:16, you can make x^400 in more ways, by using x^2 and x^4 from the first polynomial, or am I missing something here? Thanks for the great content!
8:56 293 - 1 = 292 9:12 1 through 15 and all unique because that's how binary works. Using the polynomial product, (1+x)(1+x^2)(1+x^4)(1+x^8) = (1+x^16)/(1-x) = 1+x+x^2+...+x^15. 24:00 because we don't need all the 5 highlighted terms from the 405-degree polynomial to make the product x^(k * 100). And to make the formula work, the answer is at 24:12 right?
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
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.
Please elaborate further!! I don’t understand the first sentence of the explanation, I may need a visual example.
The formula shown at 24:00 works for any dollar amount if you let n choose m = 0 for n
That's it :)
Why does it fall apart?
@@Lucashallal n choose 5 expands into n(n-1)(n-2)(n-3)(n-4)/5! ... and if n
@@BrentDeJong lol thanks for the response after 3 years, but yeah thats what I thought too
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 already knew about generating functions, but seeing that automated algebra and the reason for all those 3s and 0s was seriously amazing
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!
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)!
"We started with an infinite sum so let's count our blessings"
Well it does seem like there are countably many...
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 TH-cam would ever consider making a list of subscribers in chronological order available in a reasonable way. Still waiting :(
Actually, TH-cam 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
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.
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.
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.
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
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
@@subhasish-m Well will be interesting to see what you and others come up with :)
@@subhasish-m 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.
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 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 is absolutely mind blowing. Please never stop producing content like this! I absolutely love the channel.
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!
Everyday you upload feels like christmas. I was always fascinated by generating functions. Thanks for the great content as always! Greetings from Germany :)
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).
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.
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.
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* !
it always has been -1/12
source: the astronaut behind you.
@@sofia.eris.bauhaus "Wait there's an astronaut behind me?"
@@Danielagostinho21 yeah and you're ded naw
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. 🤔
"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 :)
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.
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!
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!
This feels like all those math lectures that really made me realize how amazing Mathematics is. Thoroughly enjoyed this, and such a cool result!!
it feels like forever since the last Mathologer video. Good to see you,again.
Choosing _this_ particular t-shirt for _this_ particular topic is a stroke of satirical genius. My highest compliments! (Not just for the t-shirt ;-) )
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.
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!
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.
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!
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
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.
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 ;)
9:14 pretty obvious that it is a representation of a binary number. You can also generalize to be n-1 coins each of powers of n. Take n=10 you will be familiar of base 10 number system.
23:57 Not sure if it "doesn't work" because we haven't defined C(n,r) = 0 when n < r? The formula should work for k
"Not sure if it "doesn't work" because we haven't defined C(n,r) = 0 when n < r". Yep, that's it :)
I love how the 9 flips at 24:45!
Lovely video!
Magic all around, not the least in the graphical animations. Wonderful - as always. Viele Grüße!
Thank you, for your videos. "fresh" ideas and content and ton of work behind them.
This is so fascinating! Really enjoyed watching this video :)
This is the most satisfying video of 2021 so far ^^
Great video! Quite approachable and always enjoyable. 😁
And RIP Ron Graham. ❤️
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).
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).
This will come in useful in the gym later when I am scratching my head figuring out how to load up the barbell.
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?
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!
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.
youtube never recommends mathologer.... but, it's a part of youtube we mathologists love.
23:56 Challenge for k = 0, so long as we define (n choose k) = 0 for all k > n
:) I love this video! I have just been learning about q series! It's so strange how your videos are always surprisingly relevant
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.
"One over x-ey looking, aren't they?" is one of my favorite sentences in the English language; thanks professor!
We are impatient to see the next video, I need more of this great content!
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)
Hope you will never stop making videos
:)
I thoroughly enjoyed this video, but it definitely reminded me why I've done my best to avoid serious combinatorics :)
Mathologer, wonderful video! You are a legend and you explain things so beautifully.
TIMESTAMPS :
0:00 Intro
1:20 Chapter 1 : Curious Count
9:55 Chapter 2 : Googol
14:10 Chapter 3 : Making Infinite Change
28:39 Credits
23:57
The cases k=0,1,2,3 are problematic because then 4/3/2/1 of the binomial coefficients have an upper number smaller than 5.
But doesn't this actually compute nicely without changing the formula since the binomial coefficient x choose y is zero for all x
No, that's exactly it :)
@@Mathologer ah, okay then ^^
Hi, I was thinking about an interpretation of the formula at 21:20. Imagine that whenever you have $1 worth of the same coin then you MUST put it in its own coin bag. Like those bags we used to have to deposit change into a bank. Then the binomial coefficients describe different combinations of coin bags the can make up each whole dollar, while the finite polynomial is the count for the leftover loose change. Taking the product covers all possibilities. Does that work?
13:25 it's fast Fourier transform. Have no idea how is it related to Fourier transform with complex integral, but FFT is algorithm calculating product of polynomials faster, you can find video in 3b1b-style(it was made with manim), explaining the work of such algorithm. Due to many zeros in polynomial it could be advanced to better work
Great video as always, even after chapter 1 I was amazed. Thanks for this :)
"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
For the programming challenge for dollar amounts, this is how I might try to calculate it: if a_n is the number of ways to make change for a value n coin using 1, 5, 10, 25, 50, and 100 value coins, I have the recurrence a_n = a_(n-1) + a_(n-5) + a_(n-10) + a_(n-25) + a_(n-50) + a_(n-100). (a_k for k < 0 is 0 and 1 for k=0). You could then just use the recurrence relation to calculate the first however many terms in the sequence. If you wanted a closed formula for a_n, Because each a_n depends linearly on the last 100, you can find a (sparse) 100x100 matrix of 0s and 1s that when applied to the vector [a_n, a_(n-1), a_(n-2),..., a_(n-99)] results in the vector [a_(n+1), a_n,...,a_(n-98)]. Then you could convert this to Jordan canonical form and find the change of basis matrix. In principle, you could figure out the formula for raising each of the Jordan block matrices to the n-th power, then use this to find a closed form expression for a_n. I have a feeling that the latter method might be very inefficient, and susceptible to round off error or something like that.
Cool :)
The reason why the formula around 23:00 doesn't work for k < 4 is that we have some extra options we should not have due to the way the formula was derived. For the k={1, 2, 3} cases one must not include the terms higher than k*100.
The general formula works beacause there is only limited [and fully utilized] choices for 1st and 2nd part of the product only one valid chice raimains for the infinite 3rd part. While the 3rd part is infinite it behaves well. Only 5 of the terms work at the time. when including quite simple corretion factor.
For k = 1 we have:
(1)* (1)* (6*x^100) + (1) * (287*x^100) * (1) = (6 + 287) * x^100
= 293 *x^100
For k = 2 we have (I'll skip all the ones):
(21 + (287 * 6) + 985 ) * x^200
= 2728 *x^200
For k = 3 we have:
(56 + (287 * 21) + 6* 985 + 325 ) * x^300
= 12318 *x^300
For k > 3 we have (C representing the combinations operator and done before multiplications:
( 1*(k +5)C5 +287*(k + 4)C5 +985*(k+3)C5 +325*(k+2)C5 +2*(k+1)C5 )*x^(k*100)
Now we can see that for k < 4 we use only k + 1 first terms of the general solution.
That's it :) An easy way to fix the formula is to define binomial coefficients with top < bottom to be equal to zero (makes sense when you think of Pascal's triangle surrounded by a sea of 0s :)
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
*reads how to make googol dollars*
Nobody:
Bill Gates and Jeff Bezos:That’s not a dare, that’s Tuesday.
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!
This channel is the jewel of youtube
nice :)
nice
nice
very nice
nice
nice
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.
9:49 has the interesting conclusion that 1/(1-x)=sum[x^i,{i,0,Infinity}]=product[(1+x^(2^i)), {i,0,Infinity}] (at least if i didnt do anything wrong). very nice!
Yes, very nice isn't it. Really worth actually expanding a partial product :)
fantastic video! this may have given me to tools i needed to solve a math problem i’ve banged my head against for years!
9:45 just from eyeballing the question, I can pretty clearly see that the answer is that you can make 15 different amounts (16 if you include 0) and they're all made in a unique way. What's more, if you have n coins, you can make every value in a unique way up to
2^n - 1 (Again, 2^n if you include 0). You can do this just like if you were counting in binary, which uses the powers of 2 to uniquely construct every whole number. Pretty cool if I do say so myself!
That's exactly it :) Try doing it with the product anyway, very satisfying...
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
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!
9:48 As a computer person, it is *instantly* obvious this is binary. But to answer the question, using coin values of the first n powers of two (where the first is 2^0, or 1), you can make all integer amounts from 0 to (2^n)-1 [inclusive], each in exactly one way.
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.
Best thing I watched this week even though it was uploaded 4 mins ago
Great video! The answer of how many ways of summing any number (equivalent to make change with coins of all numbers) does not come following the same argument/procedure without much troubles?
Trying to solve the problem at 9:08 without actually doing maths, I would say instinctively there is exactly 1 way to make any amount between 0 and 15. I haven't calculated this, but I'm fairly sure I'm right this time since this looks very very similar to counting in binary.
Using more power of 2 coins you get exactly 1 way to make any amount between 0 and (2^x)-1, where x is the number of coins used.
This is very interesting way to describe binary counting, so thanks for that.
That's 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. : )
23:58 Choose function is undefined for negative values, but we can easily generalise known formula using generalisation of factorial - gamma function. Then everything works out nicely
Something like this. Actually the only thing you have to do is to extend the definition of binomial coefficients: anything with a top less than the bottom is set to 0 :)
00:10 Yes, the overlords will abolish all cash and your digital money will only be in one central bank governed by the oligarchs.
9:08 With one of each of the first n powers of 2 coins, you can make any amount up to 2^(n+1)-1 exactly one way. This is like the base 2 representation of natural numbers in (I believe it's called) positional systems, which we use with arabic numerals. There's a general theorem for this, so, for example, you can make any amount up to 3^(n+1)-1 with TWO of each of the first n powers of 3 coins (1, 3, 9, 27, etc...) exactly one way; the obvious example is NINE of each of the first n powers of 10 coins (1, 10, 100, 1000, etc...). ^.^
22:59 Why not take x^2 from the first 1 from the second x^200 from the third? Or x^4 from first, 1 from second and x^100 from third etc.? IMHO there are more terms giving x^400 than the ones you showed. Am I missing something?
x^2 * 1 * x^200 = x^202
Does anyone know where i can find the music that plays during the algebra autopilot (19:35 for example)? Amazing video, i am looking forward to try these challenges!
check out the description of the video :)
"And of course we also get that one way of making zero sense".
I chuckled a few times throughout the video :)
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.
First time I see a Mathologer video where I have already seen everything on the university. Great stuff by the way.
...Probably last time as well.
Are you sure you already knew the times table stuff and the explanation for the strings of 3s? I am not aware of this being covered anywhere :)
@@Mathologer Hah, you got me there. I should've been more careful while writing!
Sorry if this was asked (too many comments to go thtough), but at 23:16, you can make x^400 in more ways, by using x^2 and x^4 from the first polynomial, or am I missing something here? Thanks for the great content!
No, you cannot use x^2. Just give it a try :) Try to combine x^2 with one each of the powers of x present in the second and third line into x^400 ...
@@Mathologer Yes, I see that now, I claim temporary insanity. Sorry for the noise!
@@vladduAll under control then :)
27:40 Oh wait, I have that book! I devoured it in 1 or 2 days because of how fascinating it was.
Hope you at least seasoned it with salt or pepper
8:56 293 - 1 = 292
9:12 1 through 15 and all unique because that's how binary works. Using the polynomial product, (1+x)(1+x^2)(1+x^4)(1+x^8) = (1+x^16)/(1-x) = 1+x+x^2+...+x^15.
24:00 because we don't need all the 5 highlighted terms from the 405-degree polynomial to make the product x^(k * 100). And to make the formula work, the answer is at 24:12 right?
All good :)
Loved the counterpoint music at the end.
RIP Graham, a true GOAT 🐐🐐