"There's life before you understand generating functions, and then there's life after you understand generating functions." Having taken those courses, I can 100% agree.
Indirect inventor of Hadamard-Rademacher-Walsh also known as Walsh-Fourier transform which can be used to derive the transformed equation with just sign flips and additions. (But there's more of them than in plain discrete Fourier transform which uses multiplications - now he actually devised Hadamard matrix and its properties.)
3:54 "To be clear, this lesson is definitely much more about the journey than the destination". This is the biggest difference between this channel and other channels that show math problems: it doesn't just show you one correct solution to a specific problem, but it teaches you how to think about a new problem. And that is no small feat. Thank you, Grant.
Two other excellent channels for that are zetamath and Aleph 0. I only wish they had more videos! It's understandable when you think of how much work has to go into this sort of thing.
I think that it's because these videos can't really replace actual academia, and Grant, as an academic himself, knows this. Instead of trying to teach you a lesson, he instead tries to instill in you a certain intuition that will help you. In other words : You are given the illusion of learning to keep you hooked onto the video, and while this is happening, he finds ways to still make you remember some interesting facts or methods. I can't get myself to remember every step, but I still understood that you can find functions that act simmilarly to sets, and that every time you have a question that ends up talking about frequency filtering, complex numbers often are a very elegant way to answer. It's not about the actual hard facts learned, it's about the ideas and mindsets that you bring to class next time, while still fostering your inner mathematical curiosity. This is where I find that most channels fail, when they don't understand that trying to teach someone a new idea won't always stick, if at all, but that you can absolutely shift someone's mindset over problem-solving.
@@JustFiscuscalculus and combinatorics are whole different beasts, m8. Calc was merely a preliminary to everything, plug&chug in formulas most of the time, whilst combinatorics & number theory do induce lots of "outside the box" moments. I would heavily recommend "Principle and Techniques in Combinatorics" by Koh-Khee-Meng & Chen Chuan Chong and "Elementary Number Theory" by David M. Burton just in case.
At exactly 14:31 I realized where you were going. I just love this feeling when it "clicks" and your videos never fail to deliver on that, thank you for this great content!
Same! I was about to say the exact same thing, it was a really good idea to foreshadow complex numbers at the beginning. The moment he said “rotate” i was like WAIT WAIT I GET IT YOOO
I'm an Applied Maths major and sometimes is hard to see why I'm learning about complex numbers, analytic geometry and other things and it's harder to see how they are connected. It's truly beautiful to see how it all comes together, thanks.
I watched this about a year ago and remember having no understanding of anything beyond the generating functions. I watched your lockdown math lectures on complex number fundamentals and have a perfect understanding of the video now. Its a beautiful solution I think it's one of your best yet. Thank you
Grant, I'm sure you've heard this before, but I want to express how much I appreciate the extra special care you take that even a person with zero mathematical training like myself could follow along a complicated exposition like this. It's invaluable to me (and countless others). I humbly thank you. Also, lovely illustrations! Add the rhetorical style, and it all comes together in a most gratifying, soulful, and rich experience. Somebody in the comments used the word 'sublime', and that's accurate.
I love how this channel embraces the math and ACTUALLY TEACHES. So many channels want to make math/physics fun and approachable but end up sacrificing substantiative content to do so. This channel doesn't compromise and I love it. Keep it coming!!
In the quest of bringing a love of math to uninterested or even antagonistic people towards it, some channels have reduced mathematics to the level of simple party tricks which you just simply were not taught. It does it a huge disservice in that it sacrifices its elegance, genius and truer intuition. 3b1b masterfully circumvents the need for such sacrifice and still does somewhat appeal to the people that are otherwise unenthusiastic about math. Peak teaching.
@@nasorusvandark69 i think there is value in the approach of those other channels. Back when I thought I hated math those style of videos kept me interested/wanting to learn more. It would help me find math as fascinating, where at the time 3blue1brown videos were just over my head. While I think Grant's content is great, especially now, it is a lot more difficult than a lot of other math content. Truthfully they just made me feel stupid when I "hated" math instead of inspiring a yearning for more
@@skylarkesselring6075 I have no problem with math vulgarisation per se, as I myself developed my love of the subject from videos like those. What I don't like is how some videos oversimplify the subject to an almost meaningless defree at times. Though maybe I'm wrong in that that could be perfectly fine, while just aimed towards a different audience, who knows, I might be making a big deal out of nothing. I guess ultimately what I meant is that you absolutely should not make a vulgarisation of something like a millenium problem, as it rids the topix if all its substance, at least in my opinion.
People with an electrical engineering background might see the roots of unity just like filtering a discrete-time signal in the z-domain. Super cool to see the parallels with the same math used for something seemingly completely different and explained so well!
@@johnnelcantor4739 Pretty much any digital signal processing book will discuss filtering in terms of complex numbers. My personal favorite though is by Proakis and Manolakis. but the most recent revision is by Manolakis and Ingle. Same material in spite of having different authors.
Plato said "The highest form of pure thought is in mathematics" and I got a sense of it when I watched this video. I seriously fell in love with the thought of "rotating by 72" 💓 This video is a perfect example for good story telling and the importance of story telling in math education and to inspire students to naturally get a sense for using complex objects for seemingly simple questions. Often what demotivates students at college is that do not quite understand why things have to get so complicated! Perhaps things only get simpler is apparent complication. Videos such as these can be true demonstrations of what I mean.
Oh you're the channel that 3blue1brown shouted out on his website! Awesome to see you here- love seeing Grant showing some love to underrated educational RUclipsrs
every time grant mimics a student like "why do complex numbers show up in a counting problem?" I remember that I spend more time with group theory than many target viewers, because my immediate thought is "well the roots of unity are a really natural analog for modular arithmetic"
The real answer is that complex numbers contain all sorts of structures inside them, and it's simpler for our minds to use complex numbers for everything than to invent the minimal sufficient subset for every task. That's the same reason why quarternions are used in 3D geometry - what you really need is rotors, but they're a subalgebra of quarternions so you might as well use quarternions.
Not sure what group theory or modular arithmetic is, but this video combined with the words "natural analog" remind me of Veritasium's videos about analog computers.
Every time I watch this guys videos I am blown away by how intelligent people can be, how I would never be able to arrive at any of these ideas, and above all the quality of this guy's videos. The production value is through the roof.
If you feel that you can not arrive at these conclusions then the videos aren't serving their purpose. I'm not trying to be mean - rather asking you to be more confident, the people discovering these have way more experience under their belt and we too might be able to do the same or greater with the same experience.
lots going on here! to dive into deeper underrstanding you can search up on the topics he mentions! complex numbers are hard to grasp for many, if not most and the rules/shortcuts they come up with in complex analysis seem like magic alot of time. To really get the grasp you have to start diving deep and practice practice practice! lots of cool stuff in this video, makes me miss my pure mathematics major at UC santa cruz
this is one of many, many reasons why getting exposed to math competitions at a young age is both really useful and entertaining. Too bad, most secondary school teachers are not educated nor paid enough to perform at this level.
@@mclovin3725 No it's exactly secondary school. I took part, briefly, but I was nowhere near smart enough. It's true most secondary school teachers can't coach at this kind of level. Thank goodness for the internet and people like Grant producing these videos nowadays.
As someone who has participated and done decently in the USAMO and CMO (top 20 and top 5 respectively), you typically need to broaden your understanding rather than go into everything in depth. You're not expected to use analysis or topology, but you should know tons more algebraic tricks and ideas than what is taught in highschool. I still managed to do quite well despite not knowing calculus at the time that I did them.
@@ffc1a28c7 Are you Self taught and how did you know to avoid going in too much depth and rather concentrate usefully on algebraic tricks etc. What resources did/do you use?
Incredible video - I remember the Fourier transform video about "wrapping" functions around the unit circle (in the complex plane) and the complex part of this video was extremely reminiscent of that. So much so that I was able to follow along exactly where it was heading. That's when I realized that your videos have fundamentally allowed me to learn math and truly enjoy it. You are my favorite YT channel by far. THANK YOU!
It should look reminiscent, because it's the exact same technique. What he's actually doing here is, he's evaluating the discrete Fourier transform (DFT). At 17:14 he acknowledges that. If you look at the equation with the sum symbol, and plug the phi into it, it's the formula for DFT (or rather, for its value at carefully chosen frequency). The next step in the learning process is to see how this technique generalizes.
@@KohuGaly Fourier transforms are my favorite... They are just so fascinating. I recognized it was an extremely similar process but I didn't feel fully confident in labelling it as the same because I'm not an expert in any way. Thank you for your explanation! I appreciate it a lot!
I'm a math student and teacher (10-14y/o students). This was one amazing presentation of a "simple" question and a solution I could follow seamlessly even though I'm not a genius nor a professional mathematician. Love the simplicity in the design choices and the passion that was put into this! Always a blast listening to your work!! Love from Austria ;)
Having just finished studying some undergraduate level abstract algebra, this video gave me a greater understanding roots of unity and their applications. Your work never fails to both stimulate the creative mathematician in each of us as well as supplement our previous education with new insight. What a gift this channel is, I cannot wait to see what it continues to give in the future. Thank you, Grant, for everything you do.
I'm not the kind of viewer that pauses and try to solve the problems by myself because I know I'm getting nowhere, but I watch all your videos and come back to watch them again after a while and it's surprising that, even if don't remember the steps to the solution, it gets less magical and starts to sound more like something that I would have come up by myself. Thanks!
I remember a time in math class doing series where I wanted to "filter" only odd numbers for some simple sine series, and ended up using a trick with powers of negative one. It's awesome to learn that not only is that technique actually used in practice, but there's a much cooler version out there as well (and yet another use for Very Cool complex numbers :) )
yeah back in my mathcounts days I even managed to discover up to using powers of i (4th root of unity) but I didn't make the connection to arbitrary roots of unity until later
To be fair, I think he over-complicated the beginning. You could ask some pre-algebra students to list all the ways to use the numbers 1,2,3,4,5,6,7 to add up to something like 11 (using each number at most) and put them in a column. And then ask them to list all the terms in the expansion of (1+x)(1+x^2)(1+x^3)(1+x^4)(1+x^5)(1+x^6)(1+x^7) that give you x^11 and put them in a column. Comparing the columns side-by-side makes the correspondence clear. Column A Column B ---------------- ---------------- x^(7+4) 7+4 x^(6+5) 6+5 x^(7+3+1) 7+3+1 x^(6+4+1) 6+4+1 x^(6+3+2) 6+3+2 x^(5+4+2) 5+4+2 x^(5+3+2+1) 5+3+2+1 (not sure if the columns will be aligned correctly after I post) The pre-algebra students would not have the knowledge to follow the roots of unity filter for the powers of 5. But they might be able to handle it for powers of 4. Because the 4th roots of unity are just 1, -1, i, -i. Even the final step where you plug the roots of unity into (1+x)(1+x^2)(1+x^3)(1+x^4) becomes a lot more simple because many factors are simply 0 unlike with 5th roots of unity. So if you took this problem and changed it from multiples of 5 to multiples of 4, you would still have a solution that used polynomials and imaginary numbers to solve a problem whose answer is a real integer, so it would maintain the weirdness, but it would be approachable to a much younger audience.
This feels very much like my real analysis class: I can see what you're doing and how you got there, and it's very impressive, but there's no way I could do it myself.
You will get there. In a couple years you will look back at the problems you are struggling with now and wonder what the hell was stopping you from seeing what now feels like an braindead obvious idea. It happens to all of us.
@@connordavis4766 that's how one learns mathematics. Get stumped, let the unconscious mind work-out the details, and in a matter of time the answers seem as obvious as arithmetic.
My math professor once said something that changed the way how I saw math - he said (when discussing a new PDE) - "if this doesn't make sense to you, don't worry about, it's not supposed to, but once you repeat it enough times it will become natural, like 2+2"
This channel doesn’t make bad videos. The quality is there in every video. You can tell they are not throwing up videos just to put up content. There’s real effort and thought involved in each video.
When I was doing my undergraduate course in physics, I fell In love with complex analysis. A way to re-think older problems (infinite trig integrals etc.) with seemingly disconnected injections of complex numbers. But the fact that they *arent* at all disconnected is the beauty in it. Its not 'imaginary' but a very real expression of the root of mathematics (ergo, logic). Probably one of the hardest courses I took. And absolutely my favourite. I wish I had more opportunity in my professional life to get back into complex analysis. For now I think I'm going to just dig up my old notebooks.
I'm so excited for that Riemann zeta function video - the old one on analytic continuation is one of my all time favourites on this channel, I watched it just after learning what complex numbers even are. And now look how far we've come... I've even come to actually _like_ complex numbers in the mean time...
What I really like about this is that literally anyone who understands the problem can come up with a pretty accurate guess. The error would only be 1/2^1598 of the real answer!
@@sciencedoneright Isn't it 1/2^1598? The answer is (1/5) * (2^2000 + 4*2^400) which is the same as (1/5) * (2^2000 + 2^402) The difference between the guess and the correct answer is (1/5) * 2^402 so the fraction of the final answer would be (1/5) * 2^402 / (1/5) * (2^2000 + 2^402) which is approximately 2^402 / 2^2000 which is 1 / 2^1598, right? Is the approximation wrong?
If you consider that the 400 numbers divisible by 5 make no contribution to the sum, you can see that the answer has to be divisible by 2^400. If you then minimise the error, you get the correct answer: 2^400 x ((2^1600-1)/5 +1).
This makes me nostalgic. Remembering my high school days in the IMO training camp, solving these problems. Didn't make it to the team by a few marks, but enjoyed the experience a lot. Those were the days.....
I want to thank you for this channel. A video a saw here last year was the spark that was missing to ignite strongly enough my desire to pursue a master degree and, despite all the fears and challenges I knew I'd have to overcome by going through with this, finally apply. And now that I'm here trying to conciliate work with the academic life - and also with having a life -, this is, again, the kind of content that reminds me of the passion I feel for the field and that can feel distant when we're struggling in the routine.
Thank you so much for coming to Tufts! It was so great seeing your work and meeting you! I also love how you’re incorporate the “live” elements where you can see the use of a cursor like in a more traditional lecture to expand and clarify elements. Such a great style!
I literally cried seeing the solution finally works out. It is so satisfying. Math will never die. Thank you for making this video, for preserving knowledge and stimulating curiosity.
Thanks! This is such a brilliant explanation. Really appreciate the effort which went into making this video so clear. On a side note, 27:57 "The expression ... is almost identical... it just has minus sign" -- this is not the only difference, as the powers in the top expression go from 1 to 5, and the powers in the new expression are from 0 to 4. Of course ζ⁵ = ζ⁰ by earlier argument, but this was slightly unclear. Same at 28:22 "the right hand side turns into the thing that we want to evaluate", again not quite.
When I stumbled upon this video when it first came out, I paused and tried to solve the puzzle. Today, I solved it, and it happens that my method is very similar to yours (or quite identical until the very end). But the way I created the generating function didn't involve a leap of faith, quite the contrary. I didn't read all the other comments to see if someone else brought it up, but here's how I worked it out : I think of the subsets of {1,2,...,n} as blocks that I stack in columns. Each column is labeled 0, 1, 2, and so on. Those labels represent the possible sums of subsets. When a subset has a sum of 6, I place its block in the 6-labeled column and so on. It's easy to see how to generate the subsets of {1,2,...,n} if you already know the subsets of {1,2,...,n-1} : take all the previous subsets, copy them and add the element "n" to each new copy. Consequently, the sums of those new copies of subsets are all the original sums +n, thus the copied blocks are to be shifted by "n" and then stacked on top of the original ones. Now, if you think of the number of blocks in each labeled column as coefficients in front of powers of x (the k-th power is the k-th column), then everything comes around quite nicely. Assume you know the polynomial associated with {1,2,...,n-1} (let's call it p_{n-1}(x) ), then to generate the next polynomial, add p_{n-1} to a shifted version of p_{n-1} (to emulate what we did with the blocks). To shift all the coefficients, simply multiply the copy of p_{n-1} by x^n. Therefore, p_{n} = p_{n-1} + x^n • p_{n-1}. Factor p_{n-1} and you get : p_{n} = p_{n-1} • (1 + x^n). Unroll this product recursively and you get the polynomial in its product form. Voila, no leap of faith!
Beautiful video. The answer is striking and as another poster mentioned, it is reminiscent of Burnside's theorem. I'll outline a solution below. Imagine 400 "concentric" pentagons. Label the vertices of the innermost pentagon 1-5, with 1 at the top, proceeding clockwise. On the next largest pentagon, label the vertices 6-10, 6 at the top, proceeding clockwise again. Now, color the vertices with one of 2 colors, say red or green. If the pentagon is fixed, there are 2^2000 ways to do this. When vertex is green, include it in the subset, exclude if it's red. Consider two colorings equivalent if one can be obtained from the other by a rotation of 0, 72, 144, 216, or 288 degrees. By Polya's enumeration/Burnside, there are (1/5)*(2^2000 + 4*2^400) ways to color the vertices. The catch is that in each group of equivalent colorings, one and only one set of green-colored vertices will be a multiple of 5. Thus, the number of colorings is equal to the number of subsets whose sum is a multiple of 5. To see this a bit better, for the simpler {1,2,3,4,5} case, consider just one pentagon and suppose three consecutive vertices are colored green, the other two red. This corresponds to the five 3-element subsets {1,2,3}, {2,3,4}, {3,4,5}, {4,5,1}, and {5,1,2}. Only one of these, {4,5,1}, has a sum that is a multiple of 5. Edit: Spelling
I don’t see how this is correct. Consider the colouring {1,6,11,16,21} which sums to 55. Rotated this gives {2,7,12,17,22} which sums to 60, and so on. So all sets in this group of equivalent colourings sum to a multiple of 5.
@@Simon-ts9fu Right! Back to the drawing board for me. I was looking for something with 5-fold symmetry and at first, I was thinking of a 2000-gon, but then this idea of nested pentagons came to mind. I'll give this some thought and if (when!) I think of a different way to interpret this, I'll reply again.
@@Simon-ts9fu I think I have a fix for my original argument. If the size of the set is not a multiple of 5, it should still work. If it is a multiple of 5, then either every pentagon is uniformly colored (in each pentagon, all are red or all are green) or there is some pentagon that has a mixture of red and green vertices. If all are uniformly colored, all rotations produce the same sets. If there is some pentagon that has a mixture of red and green vertices, find the pentagon of this type closest to the center. When the pentagon is rotated, rotate all labels except for this special pentagon. In your example, the 1 in the set {1,6,11,16,21} would remain unchanged, so the next set would be {1,7,12,17,22}. The argument isn’t as elegant as I would like it to be, but it works.
I've been watching this channel since i was in my second last year of highschool, I'm now in my third year of my bachelor's in pure math and this channel still amazes me every time, the videos are accessible even to people with hither to no background in mathematics and yet are full of insights that even three years after embarking on a formal education journey in pure maths, the quality and entertainment value of the videos on this channel never ceases to amaze me
I saw the first problem, and noticed that I've solved it earlier by monte carlo simulation, but I've never thought about doing it in another way! Now I'm really pondering about it
Absolutely astonished by the visual style of this video and how it differs from others in the channel, it embodies a form of storytelling and the math parts are presented much more like a DIY thing than a "let the screen do the math" which was absolutely perfect for this kind of problem-solving video, looking forward to other beautiful ways you can present math but also more of this kind of style. These type of videos are what embodies my love for math and education and I'm completely thrilled for what other ways of story telling and teaching math you can scheme. Thanks as always Grant, this was amazing.
he is very brilliant but he mentions he never was a savant of any kind, he has spent countless hours studying math and coming to realizations and learned hwo to communicate rather complex stuff to us in such a beautiful way with amazing animations! they just get better and better. we live in a time where we get this kind of explanation on youtube, for absolutely free. Makes me sad most people watch endless tiktoks without learning anything but nonsense, instead of devoting an hour a day to learn some stuff like this! not applicable to many lives i guess but i just cant but help to be fascinated by math,.
This is actually insane! When I first watched this video, I was so captivated by generating series and I looked for them in the descriptions of all the math classes at my uni. I found out a class that I was going to take in the Fall introduced them. It ended up being my favourite class so far and we also covered finding the closed form expression for recurrence relations like Fibonacci. I actually love this channel so much
Watching this while taking a course on groups, rings and fields ended up surprising me in the similarities between this and the Galois groups of field extensions. I think a video on abstract algebra could end up very interesting
and then when I actually try to come up with it on another olympiad problem, everything feels difficult again :') but it's nice to be able to follow the arguments haha
This is a trick that I've used countless times in high school math, yet I never imagined the connection between generating functions, the Riemann hypothesis and Fourier series. Truly marvellous. I also wanted to thank you. It is because of educational creators of you, that I am now in one of the premiere mathematical institutions in my country. I never even imagined that I would get selected, I only gave the exam because I find math beautiful, and you, along with many other creators, I believe, are to thank for that. Love your vids.
So I used to prepare for math olympiads a lot in high school, and a lot of problems involved analyzing a sequence defined by a recurrence relation. Just went through the first couple pages of generatingfunctionology and HOLY SHIT, how the hell did I not know this technique?! It's sooo useful and it's so simple.
Another fun way to get g(x)=2 would be to return to the simplified problem about {1,2,3,4,5} [where g(x)=(1+x)(1+x^2)...(1+x^5)]. We know the answer in this smaller case is 8. Therefore, (g(ζ)+g(ζ^2)+...+g(ζ^5))/5=8. From here we get g(ζ)=(40-2^5)/4=2. Thanks for your stunning show, and a special thanks for the puzzles at the end!
There’s another nice way of solving this problem in log(n), where n is the size of the set (in this case, 2000) by exponentiating a 5x5 matrix! Generating functions are fun as well :)
@@goblin5003 It's the matrix that transforms the vector containing the mod 5 totals after considering the first n numbers, into the mod 5 totals after considering the first n+5 numbers. Consider for example the totals at 5: 0 mod 5 will have 4 subsets: {}, {1,4}, {2,3}, {5}, 1 mod 5 has 3: {1}, {1, 5}, {2, 4}, and so on. Now consider the effect of adding just 6. We can either include or not include 6, which is 1 mod 5, which means that the entry in this vector for (as an example) 0 mod 5 up to n = 6 is the entry for 0 mod 5 when n=5 + the entry for 4 mod 5 when n=5. You can make a matrix for adding a number 0-4 mod 5, then multiply the matrix together to get the one that brings you from n to n+5. While all of the other matrices are different, this one is always the same, so you can repeatedly apply it. (From there, you can get an explicit formula again to solve it in O(1) time by using eigendecomposition/Jordan Normal Form. It's another, albeit less general, method of solving recurrence relations.)
@@OmnipotentEntity do you have any link/reference to a webpage, book or video where this kind of procedure is applied? I didn't quite understand the logic behind it with just the comment :(
This channel is so underrated. The way you make something like this so interesting and so fun and easy to watch is so fascinating. Never thought I'd watch 32 minutes of complex math, understand it, and feel entertained while doing so. Thank you sir.
What do you mean by "underrated"? The channel has 5 million subscribers, despite being about math and usually diving deep into the topic. That's basically a miracle. It's even surpassed Numberphile, despite being much less accessible (albeit, more beautiful).
In my set of discrete math courses in college, I was fortunate enough to learn about generating functions, and had the wonderful opportunity to explore them more in my senior thesis. My favorite generating functions are the rook polynomials! When you introduced the problem, I was immediately thinking “Hm, how would I make a generating function for that?” Awesome video as always!
yeah once you know the trick for generating function, for like huge huge sets or so, you kinda intuitively want to make a function with coefficients that are countable or reduce it by a margin! its really neat! i wish i could study more math for school, so expensive and cant right now, maybe one day ill be fortunate to finish my pure maths degree and get a masters after!
Here's another way to solve this problem, which also gives us the number of subsets whose sum is 1,2,3,4 mod 5 respectively too. The idea is taken from the book titled 'Problems From The Book', co-authored by Titu Andreescu as well: Denote c₀, c₁, c₂, c₃, c₄ as the number of subsets whose sum is 0,1,2,3,4 mod 5 respectively, then taking f(x) = (1+x)(1+x²)...(1+x²⁰⁰⁰) evaluated at ζ, we have, by compiling coefficients congruent mod 5, f(ζ) = c₀ + c₁ ζ + c₂ ζ² + c₃ ζ³ + c₄ ζ⁴. But we know f(ζ)=2⁴⁰⁰ (The video has covered this). Therefore c₀ + c₁ ζ + c₂ ζ² + c₃ ζ³ + c₄ ζ⁴ = 2⁴⁰⁰, or equivalently (c₀-2⁴⁰⁰) + c₁ ζ + c₂ ζ² + c₃ ζ³ + c₄ ζ⁴ = 0. In the field of rational numbers, the polynomial 1+x+x²+x³+x⁴ is the minimal polynomial of ζ, so whenever ζ is a root of some a₀ + a₁x + a₂x² + a₃x³ + a₄x⁴ =0 where aᵢ are rational, then 1 + x + x² + x³ + x⁴ divides a₀ + a₁ x + a₂ x² + a₃ x³ + a₄ x⁴, or simply a₀=a₁=a₂=a₃=a₄. Therefore c₀-2⁴⁰⁰=c₁=c₂=c₃=c₄. Since c₀+c₁+c₂+c₃+c₄=2²⁰⁰⁰, we get that c₀=(2²⁰⁰⁰+4×2⁴⁰⁰)/5 c₁=(2²⁰⁰⁰-2⁴⁰⁰)/5 c₂=(2²⁰⁰⁰-2⁴⁰⁰)/5 c₃=(2²⁰⁰⁰-2⁴⁰⁰)/5 c₄=(2²⁰⁰⁰-2⁴⁰⁰)/5 So, not only have we found the number of subsets that have sum divisible by 5, we also found the number of subsets that sum up to other remainders modulo 5 too, and they are surprisingly evenly distributed! (However, take note that this method only works because 5 is prime, whereby we've used the fact that 1+x+x²+x³+x⁴ is irreducible in Q.)
We can always find all the other sums modulo 5 because f(ζ^n) = sum k=1->N of c_k ζ^nk are exactly the DFT coefficients of the sequence (well, up to some choice of convention for the scaling and sign of the powers). The inverse DFT in this case is then c_n = 1/N sum k=0->N-1 of f(ζ^k) ζ^-nk. For n=0, ζ^-nk = 1 for all the terms and we get the straight sum, but for the others we get something else. Actually, because our coefficients are real f(ζ^k) = f(conj(ζ^k)) = f(ζ^-k), and with the identity e^ix+e^-ix=2cos(x), we can actually say that c_n = f(1)/5 + 2/5 sum k=1->(N-1)/2 of f(ζ^k) cos(nk2pi/N). For this case that works out to c_n=/=0 = 2^2000/5 + 2/5*2^400*(cos(2pi/5) + cos(4pi/5)). Those cosines sum to -1/2, which gets the required c_n=/=0 = (2^2000-2^400)/5.
This was really cool! I learned about the roots of unity in my engineering program, but we never saw any applications of them. They were just an exercise in complex numbers. It's cool to see how they can be useful!
Another fun application: 19 year old Gauss used similar tricks with roots of unity to show that a regular 17-gon can be constructed with compass and straight edge, the first advance since the time of Euclid
Just sent this to my former discrete math professor. I did an independent study with her on error correction codes where generating functions and roots of unity came up so I was so excited to share.
When I first encountered this problem (it was in fact the number of subsets of {1 .. 300} whose sum was divisible by 3), I came up with the following solution: Generalized question: How many subsets of {0 .. 3n-1} are divisible by 3? I will call this number a(n). I will call b(n) the number of subsets of {0 .. 3n-1} whose sum has rest 1 modulo 3. For symmetry reasons this is exactly half of all subsets which have a sum not divisible by 3. It follows that a(n)+2*b(n)=2^3n We now look at a(n)-b(n): Simple case: n=1. We consider subsets of U={0..2} Let f(x):=(x+1) mod 3. Then for each subset s let f(s)={f(x)|x€s}. It's easy to see that f³(s)=s for each subset s of U and that exactly one of s, f(s) and f²(s) has a sum divisible by 3 for any s - except s=U and s={}. So of the 8 subsets of U, four subsets have a sum divisible by 3, two have a sum =1 mod 3 and two have a sum =2 mod 3. We see that a(1)=4 and b(1)=2, so a(1)-b(1)=2. We now assume that we know a(n) und b(n) for a specific n. Let s be a subset of {0 .. 3n-1} and s0 be a subset of {0..2}. Let g(s,s0)=s U {3n+x|x€s0}. The sum of g(s,s0) equals the sum of the sums of s and s0 mod 3. It's also easy to see that for every subset t of U={0 .. 3n+2} there is exactly one subset s of {0 .. 3n-1} and one subset s0 of {0..2} with t=g(s,s0). A subset g(s,s0) of U has sum divisible by 3 iff either both sums are divisible by 3 or both sums are not divisible by 3 and have different rests mod 3. This leads to a(n+1)=a(1)*a(n)+2*b(1)*b(n) and b(n+1)=a(1)*b(n)+b(1)*a(n)+b(1)*b(n). From this follows that a(n)-b(n)=2^n for every n. Conclusion: b(n)=(2^(3n)-2^n)/3 and a(n)=(2^(3n)-2^n)/3+2^n It's obviously irrelevant whether we look at the subsets of {0 .. 3n-1} or of {1 .. 3n} The same reasoning also works for primes other than 3 and leads to Let a(k,n) be the number of subsets of {1 .. k*n} whose sum is divisible by k. Let b(k,n) be the number of subsets of {1 .. k*n} whose sum has rest 1 mod k. Then a(k,n) + (k-1)*b(k,n) = 2^(kn) and a(k,n) - b(k,n) = 2n, so a(k,n) = (2^(kn)-2n)/k + 2n which in this case means there are (2^2000-2^400)/5 + 2^400 subsets of {1 .. 2000} whose sum is divisible by 5. Seems I am more Bob than Alice.
The last two paragraphs preceding the final sentence should read as follows: Then a(k,n) + (k-1)*b(k,n) = 2^(kn) and a(k,n) - b(k,n) = 2^n, so a(k,n) = (2^(kn)-2n)/k + 2^n which in this case means there are (2^2000-2^400)/5 + 2^400 subsets of {1 .. 2000} whose sum is divisible by 5.
I can see the symmetry case for n=3 but for any prime larger then 3 how do we know that the subsets whose size equals 1,2,3,4, , , p-1 modulo p are of equal amount?@@michaelhaffer5639
This was one of the tougher videos for me to get through. It took a few attempts, however, my final watch through I feel like I unlocked a bit of knowledge for myself. Thanks. :)
honestly this video not only teaches math, but also teaches how to teach math. Everything you present is so elegant, every smallest detail is done with perfection which is just a cherry on top of a beautiful problem and solution you presented.
Oof man you have taken me on a trip and I just fucking love when there is craY craY nuances in a single problem. There is a reason why i recommend your videos to kids i used to teach. It deserves the praise and recognition it deserves ❤️🙏🏻
I solved this using induction of two linked series: An and Bn, where An represents the number of subsets of which the sum is divisible by 5 and Bn represents similar ones of which the remainder is 1, 2, 3 or 4. Of course, A1=8 and B1=6. We can work out: An+1=8An+24Bn and Bn+1=6An+26Bn. To check our work, we should see An+1 + 4*Bn+1 = 32*(An+4Bn). Great, as expected! Interestingly, we can notice An+1-Bn+1 = 2*(An-Bn). With these two, we can find out: An+4Bn = 32^n and An-Bn=2^n. Therefore, An = (32^n + 4*2^n) / 5. The answer of the original questions = A400. Tada :)
Awesome! I'd like to understand. Why is A_{n+1}=8An+24Bn and B_{n+1}=6An+26Bn? I can kind of see where the "8An' in "A_{n+1}=8An+24Bn" comes from - with A_{n+1} you're adding into consideration 5 new numbers whose remainders mod 5 are 0, 1, 2, 3, and 4 and there are 8 subsets of the 32 possible subsets of these 5 new numbers that have a sum that is divisible by 5; therefore, you can take each subset represented by An and join it with each of the 8 new subsets to get a subset that still sums to something divisible by 5. But where does the "24Bn: in "A_{n+1}=8An+24Bn" come from? And where do the "6An" and "26Bn" in "B_{n+1}=6An+26Bn" come from?
@@joseville For the first 5 numbers, you have residuals of 0 8 times, and 1-4 6 times each. Consider what happens when you add the next 5 numbers. You will end up with a residual of 0 if you start at 0 with 8 combinations or start at one of the of other numbers with 6 combinations. so a(n+1)=8a(n) + 4*6B(n). You will end up with a residual of 1 if you start at 1 with 8 combinations (i.e. add 0), if you start at 0, with 6 combinations (i.e. add 1), and if you start at 2-4 with 6 combinations,. Thus b(n+1) = 6*a(n) + (8+3*6)b(n).
@34:11 :: The answer to prob 2 is 3^n . This can be easily done by expanding Σ into 2⁰(nC0)+2¹(nC1)+2²(nC2)+.....+2^n(nCn). If you know binomial theorem ,then you may see that it's in the form of (1+x)^n ,where x=2. Hence,the required answer is 3^n.
I might have stumbled upon generating functions, when I attempted to generalise some board game dice probabilities, but I was left at a standstill not knowing where to go... This has given me some Ideas for possibly solving a month long nightmare I had stuck in my head! thank you so much!
i have to admit, i was interrupted multiple times while watching this resulting in me watching this over the course of multiple days and definitely forgot we were solving for {1,...,2000} instead of {1,...,Infinite} and it suddenly makes a lot more sense at 29:03. Thanks to the power of Thanks.
It's really interesting that you are doing this whole problem with groups and polynomial rings without even mentioning them. I enjoyed this video. Thanks
While you can't bruteforce this, it's possible to use dynamic programming for this problem. Let's first look at the empty set {}, it has only one subset which is divisible by 5. so we have 1 subset with remainder of 0 and zero subsets with remainders of 1, 2, 3 and 4, let's write it down: (0:1, 1:0, 2:0, 3:0, 4:0) Next step we add number 1 to the set. Now we have one extra subset with remainder of 1: (0:1, 1:1, 2:0, 3:0, 4:0) What happens when we add 2? Every subset we had before will produce one extra subset by including 2 into them. So now we have one new subset with remainder of 3 and another one with remainder of 4: (0:1, 1:1, 2:1, 3:1, 4:0) And when we add 3, previous subsets with remainders of 0 will produce new ones with remainders of 3, 1 => 4, 2 => 0, 3 => 1, 4 => 2: (0:21:22:13:24:1) Similar: {+4} (0:41:32:33:34:3) {+5} (0:81:62:63:64:6) - as 5 is divisible by 5, adding it to every subset just doubles their amounts {+6} (0:141:142:123:124:12) and so on, let's code it: #!/usr/bin/python from decimal import * def solve(n): answer = [Decimal(1),Decimal(0),Decimal(0),Decimal(0),Decimal(0)] for x in range(1,n+1): r = x % 5 old_answer = answer[:] for i in range(0,5): answer[(i+r)%5] += old_answer[i] return answer a = solve(2000) print(a[0]) print((Decimal(2)**2000 + 4*Decimal(2)**400)/5) # to compare with the answer given in the video Output: 2.296261390548509048465666392E+601 2.296261390548509048465666402E+601 Sure it's not what this video is about, but maybe someone will find this useful for some reason? Also sorry for my bad english :( And thanks for this amazing video which somehow was recommended for me!
That is some serious level of counting right there. WOW! You got the exact answer for a problem that would've taken eons to solve if one had brute forced it. I want this knowledge. This is some serious power.
Its so cool to finally be of age to watch these videos. Ive been watching numberphile, mathologer and you for the last 4 years but now im 18 so for the first time ever know what you're talking about.
Grant, as much as anyone, has changed how I view what education should be. And as valuable as the visuals are here, I'm sure he could do a reasonable facsimile with a whiteboard and lectern. It's all in the mystery. And yes, I'm just ripping off the points he made in his TED talk. But he sure does walk the walk.
Давно дивлюсь цей канал англійською, але дякую тим, хто зробив переклад субтитрів українською. Тільки сьогодні дізнався, що автор каналу почав додавати переклади до своїх відеоматеріалів. Thank you very much for the Ukrainian subtitles, @3Blue1Brown. I appreciate your work and educational videos and how much effort you put into them. You're a shiny diamond on the platform.
As a new math teacher, this channel reminds me how much left I have to learn. Every time I watch, I’m usually dumbfounded and unsure of the next step, but enjoy the process. Today was the first time where I arrived at the answer before it was spoken. I was so excited I immediately used the idea of roots of unity to calculate how many subsets’ sums were divisible by 4, and 10, and I’m working on 7. Thanks for the fun watch, and thanks for always keeping me on my toes!
This is way above my level but yet I love this so much. This might honestly be my favorite video from you. I have been slowly losing interests in stuff, I barley have the motivation to do anything, I don't find the same pleasure of doing stuff I loved. However, with all those in mind, this managed to become my favorite video. Im so mad at myself for not watching this earlier, when my love for math was at its peak. Thank you for this video.
Just to clarify something: at 28:35, you say that the value of that polynomial is precisely two. When looking at the two equations that you are saying are equal, it appears that they wouldn't be, due to their differing exponents. The key is to remember that the (1+z^0) term on the bottom is the same as (1+z^5) term above.
thank you, i was following along nicely and that is where i lost track. how is (-1-z^0) the same as (1+z^0) !? so as you answer, they are not equivalent column by column, but there is an equivalent with one in a different spot.
English is my second language And you confused the hell out of me when you said "it appears that they wouldnt be" I understood that you were saying that they arent equal 🙂
I went from not understanding generating functions to understanding them not so long ago, and I think the way they were introduced to me was very natural. Generating functions for me started out as just a way to represent sequences of numbers which has very simple rules of addition and multiplication (just as you characterised them). It makes perfect sense if you want to evaluate the function at a point x, just the same for a polynomial. But when you consider representing combinatorial objects with generating functions, it turns out that construction of a combinatorial class using disjoint unions and cartesian products alligns beautifully with construction of generating functions using addition and multiplication. To me introducing generating functions to a combinatorial problem is something like introducing calculations with algebra to geometrical problems. It's groundbreaking and very insightful, which is why I find the title of the video to be an understatement. It's not just the olympiad level counting, it's simply the most awesome way of counting! I also appreciate the addition links. Thank you so much for the video!
This video is absolutely beautiful. It explains all concepts clearly and I love them.
2 года назад+29
Quick note on the side, this puzzle is also an interesting way to practice dynamic programming, a very important technique in the design and analysis of algorithms. The approach shown in the video is certainly more profound and beautiful.
How exactly would you make a dynamic programming algorithm to solve this puzzle? What I would think to do is for a given number i (since the numbers are in order) the number of subsets up to 5 is just dp [ i - 1 ] [5 - (i mod 5) mod 5 ] where dp [ i ] [ j ] denotes the number of terms up to i that sum up to j (mod 5)
@@lintstudios3072 There's a tiny optimization, namely you don't need to keep as much history behind. You only need the previous and the current array of 5 elements. Since the relation is linear there's another more important optimization of using matrices to skip through and lead to large amounts of i, but j must be fixed in that case.
Have loved this channel and the videos since high school days, and still love them as I just graduated from university! Having studied some discrete math in university over the past 4 years, at 7:45 it suddenly clicked and I was screaming "Fourier" in my head. I just wanted to add that the "leap of faith" that Grant was talking about is truly mindblowing when you first see it, but truth is, once you've studied enough math, it almost ceases to be a leap at all. When I was learning about Discrete/Fast Fourier Transforms (DFT/FFT), it was very clear that these polynomials were related to sets, subsets, sums of subsets, and complex numbers. In fact, in computer science the fastest known way to count subsets with fixed sums is by using FFT, which directly means using these polynomials with special coefficients, and evaluating them at roots of unity (complex numbers). Turns out that the fastest known way to simply multiply two numbers also involves the same technique. But to the highschool me, I would not have known any of these at all and they would have been straight up black magic. I guess to justify Grant's supposed "leap of faith", you could say that once you discover Fourier Transforms, it becomes a tool that becomes natural to use in these situations, so you will be able to naturally arrive at this "leap of faith". But the first time you see it is definitely nothing short of a giant leap of faith into some devilish witchcraft that turns out to be a heavenly miracle instead. Props to Fourier for finding it first though, I can't imagine how much ingenuity it took for him.
I just felt down the chair listening to you. Wonderful, I never got in touch with generating function and the (generic) usefulness of the complex plane for extracting the correct coefficients of a polynomial function ... and now I have a *visual* of this all. Thanks a lot I learned a lot.
Mind blowing!! And the visual presentation was so elegant! Thanks - This is why I keep coming back to 3B1B When I started thinking about the solution - before I played the full video, I was thinking we just need a set of 400 copies of 1, 2, 3, 4, 5, then I did the ways 5, 10, 15 could be broken up with these numbers (I did not consider 0 as fitting the answer...)., and then........ I was stuck. After seeing the video and the elegant solution, on a Friday night, I will sleep well with a smile on my face!
In an IMO environment you'd probably solve this by induction on set size (jumping by 5s, so start with the set 1 to 5, then go from 1 to n to 1 to n+5). Once you see a path to a solution in an IMO it's best to punch the solution out rather than look for a more elegant option. Still I really love the intuitive leaps here.
Very interesting. I did think that this generative functions tool was a rather complex (no pun intended) tool for a competitive mathematician to have in their belt
The moment you showed the circle and mentioned the roots of unity, I instantly made the connection to Fourier transforms and how this was in some ways a frequency question. But I’d love to hear more about that connection! Like why exactly does this question look so similar to the intuition we use for Fourier transforms?
From some cursory googling, it seems that the Fast Fourier Transform takes advantage of the connection to the roots of unity- my guess is that just tinkering with the roots of unity will land you at this “raising roots to powers -> permuting them” connection. I also think thats the basis for the non-Galois Theory proof of the insolvability of the quintic
There is another way to solve that uses the discrete Fourier transform. As in the video, if we try this with n=5, there are 8 subsets that sum to 5. There are also 6 subsets where the sum divided by 5 has remainder 1, and 6 each with remainder 2, 3, and 4 as well. There's a matrix A that describes this, it's the matrix with 8 on each diagonal element, and 6 on each off-diagonal. Then the number of subsets that Grant is looking for is the 1,1 element (the upper left element) of A^(400). The matrix A can be raised to a high power easily by diagonalizing it, that is, by finding a matrix T such that D=TAT^{-1} is diagonal, because then A^m = T^(-1}D^{m}T, and it's easy to raise a diagonal matrix to a power. The matrix T that does this is the discrete Fourier transform matrix! The DFT matrix always diagonalizes circulant matrices, which A is.(A is circulant because the addition table for modular arithmetic is circulant.) Diagonalizing gives D = diag(32,2,2,2,2), which explains why the answer includes terms like 32^400 and 2^400. The 1/5 shows up because the inverse of T is the complex conjugate transpose of T, divided by 5.
Congratulations, your title change worked. I opened this video a few days ago in a tab and but never watched it. And now I opened it again with the new title, and I thought it looked familiar. So now I have this video open in two different tabs, same video and URL, but different titles 😂
"There's life before you understand generating functions, and then there's life after you understand generating functions." Having taken those courses, I can 100% agree.
They’re phenomenal, absolutely mind boggling, the math counts for you, who, how?
What courses?
@@ketchup2707 Combinatorics in Uni I believe :)
@Greg LeJacques Thou art mighty among all created beings!
I guess I will have just one life :D
"The shortest path between two truths in the real domain passes through the complex plane" - Jacques Hadamard. Excellent video!
Indirect inventor of Hadamard-Rademacher-Walsh also known as Walsh-Fourier transform which can be used to derive the transformed equation with just sign flips and additions. (But there's more of them than in plain discrete Fourier transform which uses multiplications - now he actually devised Hadamard matrix and its properties.)
"The shortest and swiftest path between two galaxies in real vast space, should pass through an imaginary wormhole..."
so the easiest way to prove 1 + 1 = 2 uses complex numbers as proof?
@@opticalreticle It's got to be easier than what Russell came up with.
Yes, I'd agree with that
There's teaching math, and then there's this channel. This isn't just math education, its a window into the sublime
Well said brother
what did you learn?
@@billymonday8388 everything
@@pvic6959 What did it cost?
@@thatchessguy7072 nothing
(well, almost nothing considering time and electrical energy spent 😆)
3:54 "To be clear, this lesson is definitely much more about the journey than the destination".
This is the biggest difference between this channel and other channels that show math problems: it doesn't just show you one correct solution to a specific problem, but it teaches you how to think about a new problem. And that is no small feat. Thank you, Grant.
Two other excellent channels for that are zetamath and Aleph 0. I only wish they had more videos! It's understandable when you think of how much work has to go into this sort of thing.
So, this is a mathematics channel that teaches people math, ie. how to think in a way that enables you to solve arbitrary problems.
I think Grant once said, that storytelling is one of the most usefull and motivating things, when teaching maths.
@@1betrieb1 Probably Grant is one of few people who really could teach others how to teach.
That should be true about most lessons if not all of them anyway right so kind of obvious or redundant to say..but maybe even more so about this one.
As a freshman, I understand only a quarter of the things this man says, but somehow, I still find myself learning. This is mystifying to me.
I think that it's because these videos can't really replace actual academia, and Grant, as an academic himself, knows this. Instead of trying to teach you a lesson, he instead tries to instill in you a certain intuition that will help you. In other words : You are given the illusion of learning to keep you hooked onto the video, and while this is happening, he finds ways to still make you remember some interesting facts or methods. I can't get myself to remember every step, but I still understood that you can find functions that act simmilarly to sets, and that every time you have a question that ends up talking about frequency filtering, complex numbers often are a very elegant way to answer. It's not about the actual hard facts learned, it's about the ideas and mindsets that you bring to class next time, while still fostering your inner mathematical curiosity.
This is where I find that most channels fail, when they don't understand that trying to teach someone a new idea won't always stick, if at all, but that you can absolutely shift someone's mindset over problem-solving.
lol
I’ve gotten As in every math class through Calc 3 and differential equations and I barely understand half of what he says
@@JustFiscuscalculus and combinatorics are whole different beasts, m8. Calc was merely a preliminary to everything, plug&chug in formulas most of the time, whilst combinatorics & number theory do induce lots of "outside the box" moments. I would heavily recommend "Principle and Techniques in Combinatorics" by Koh-Khee-Meng & Chen Chuan Chong and "Elementary Number Theory" by David M. Burton just in case.
Keep going!
At exactly 14:31 I realized where you were going. I just love this feeling when it "clicks" and your videos never fail to deliver on that, thank you for this great content!
Delightful to hear, that's exactly what I'm aiming for :)
Same! I was about to say the exact same thing, it was a really good idea to foreshadow complex numbers at the beginning. The moment he said “rotate” i was like WAIT WAIT I GET IT YOOO
16:41 for me. And it really is like a CLICK in your head. Almost audible maybe. Weird huh
It took a little longer for me. It was at 22:15 :)
SAME! Exactly 14:31!
I'm an Applied Maths major and sometimes is hard to see why I'm learning about complex numbers, analytic geometry and other things and it's harder to see how they are connected. It's truly beautiful to see how it all comes together, thanks.
This channel does not simply teach math, it shows math in all of it’s beauty. I would’ve never knew that I like math so much if not for these videos
Very good point -- I fully agree. But you used the wrong form of "its."
@argon i agree ☝️
@argon yup. I am ukrainian plus learning spanish now so i kinda mess up basics from time to time.
"One does not simply teach maths."
@@bbb33748también aprendo español 😁
I watched this about a year ago and remember having no understanding of anything beyond the generating functions. I watched your lockdown math lectures on complex number fundamentals and have a perfect understanding of the video now. Its a beautiful solution I think it's one of your best yet. Thank you
Grant, I'm sure you've heard this before, but I want to express how much I appreciate the extra special care you take that even a person with zero mathematical training like myself could follow along a complicated exposition like this. It's invaluable to me (and countless others). I humbly thank you.
Also, lovely illustrations! Add the rhetorical style, and it all comes together in a most gratifying, soulful, and rich experience. Somebody in the comments used the word 'sublime', and that's accurate.
I love how this channel embraces the math and ACTUALLY TEACHES. So many channels want to make math/physics fun and approachable but end up sacrificing substantiative content to do so. This channel doesn't compromise and I love it. Keep it coming!!
In the quest of bringing a love of math to uninterested or even antagonistic people towards it, some channels have reduced mathematics to the level of simple party tricks which you just simply were not taught. It does it a huge disservice in that it sacrifices its elegance, genius and truer intuition. 3b1b masterfully circumvents the need for such sacrifice and still does somewhat appeal to the people that are otherwise unenthusiastic about math. Peak teaching.
Nah generating functions are the star here. They literally count for you. They are so much more than just this.
@@nasorusvandark69 i think there is value in the approach of those other channels. Back when I thought I hated math those style of videos kept me interested/wanting to learn more. It would help me find math as fascinating, where at the time 3blue1brown videos were just over my head.
While I think Grant's content is great, especially now, it is a lot more difficult than a lot of other math content. Truthfully they just made me feel stupid when I "hated" math instead of inspiring a yearning for more
@@skylarkesselring6075 I have no problem with math vulgarisation per se, as I myself developed my love of the subject from videos like those. What I don't like is how some videos oversimplify the subject to an almost meaningless defree at times. Though maybe I'm wrong in that that could be perfectly fine, while just aimed towards a different audience, who knows, I might be making a big deal out of nothing. I guess ultimately what I meant is that you absolutely should not make a vulgarisation of something like a millenium problem, as it rids the topix if all its substance, at least in my opinion.
People with an electrical engineering background might see the roots of unity just like filtering a discrete-time signal in the z-domain. Super cool to see the parallels with the same math used for something seemingly completely different and explained so well!
This is exactly where my mind went as I am taking a discrete time signals cource atm 😄
Do you have the name of a book where i could look up for this signal filtering with complex numbers?
@@johnnelcantor4739 Pretty much any digital signal processing book will discuss filtering in terms of complex numbers. My personal favorite though is by Proakis and Manolakis. but the most recent revision is by Manolakis and Ingle. Same material in spite of having different authors.
Ah, nice analogy!
@@johnnelcantor4739 Oppenheim is GREAT! And it has full lectures on MIT's OCW channel. Look it up!
Fun fact : Titu Andreescu (the author of the book ) was the coach behind the only perfect win of USA in IMO ( all 6 students got perfect scores )
ROMANIA 💪🏻💪🏻🇷🇴🇷🇴💪🏻💪🏻
@@brominelover6747 dada , Romania❤🇷🇴🙂
Titu❤️
peste tot suntem :))
Ce surpriza faina sa gasesti romani pe aici :))
Plato said "The highest form of pure thought is in mathematics" and I got a sense of it when I watched this video. I seriously fell in love with the thought of "rotating by 72" 💓
This video is a perfect example for good story telling and the importance of story telling in math education and to inspire students to naturally get a sense for using complex objects for seemingly simple questions. Often what demotivates students at college is that do not quite understand why things have to get so complicated! Perhaps things only get simpler is apparent complication. Videos such as these can be true demonstrations of what I mean.
Man, that was a wild solution!
Congrats for the presentention, it was astonishing!
Thanks for the video!
Good to see another Brazilian here. Love your videos!!!
AYOOOO o grande
O Bruxo no seu tempo livre.
A lenda do pão de queijo de proporções áureas chegou
Tu por aqui
Once again, 3b1b making math look absolutely beautiful. Viewers should feel lucky at what they're seeing ❤️
Oh you're the channel that 3blue1brown shouted out on his website! Awesome to see you here- love seeing Grant showing some love to underrated educational RUclipsrs
Does anyone know what software he uses to make the animations?
@@theodorekim2148 Maniam I think, it’s based on math and I think he made it himself. If anyone else sees this, correct me if I’m wrong.
@@theodorekim2148 Premiere Pro from what I've heard.
I'm 'gonna quibble: "Illustrating the beauty of Maths". Mathematics is beautiful. A lot of folks sadly have not seen it.
every time grant mimics a student like "why do complex numbers show up in a counting problem?" I remember that I spend more time with group theory than many target viewers, because my immediate thought is "well the roots of unity are a really natural analog for modular arithmetic"
You've got an xkcd 2501 situation
The real answer is that complex numbers contain all sorts of structures inside them, and it's simpler for our minds to use complex numbers for everything than to invent the minimal sufficient subset for every task.
That's the same reason why quarternions are used in 3D geometry - what you really need is rotors, but they're a subalgebra of quarternions so you might as well use quarternions.
Well that's cool, I might study group theory then
Not sure what group theory or modular arithmetic is, but this video combined with the words "natural analog" remind me of Veritasium's videos about analog computers.
@@WanderTheNomad yeah that's. completely different. analog= comparable to another thing, analogue= continuous signals
This might be one of the greatest 3b1b videos of all time. The combination of problem solving and visual beauty is breathtaking.
Every time I watch this guys videos I am blown away by how intelligent people can be, how I would never be able to arrive at any of these ideas, and above all the quality of this guy's videos. The production value is through the roof.
If you feel that you can not arrive at these conclusions then the videos aren't serving their purpose. I'm not trying to be mean - rather asking you to be more confident, the people discovering these have way more experience under their belt and we too might be able to do the same or greater with the same experience.
For me, this is one of the most challenging 3B1B videos to wrap my mind around.
lots going on here! to dive into deeper underrstanding you can search up on the topics he mentions! complex numbers are hard to grasp for many, if not most and the rules/shortcuts they come up with in complex analysis seem like magic alot of time. To really get the grasp you have to start diving deep and practice practice practice! lots of cool stuff in this video, makes me miss my pure mathematics major at UC santa cruz
this is one of many, many reasons why getting exposed to math competitions at a young age is both really useful and entertaining. Too bad, most secondary school teachers are not educated nor paid enough to perform at this level.
Cos its higher than secondary school bruh
@@mclovin3725 The International Math Olympiad is for pre-tertiary education students only.
@@mclovin3725 No it's exactly secondary school. I took part, briefly, but I was nowhere near smart enough. It's true most secondary school teachers can't coach at this kind of level. Thank goodness for the internet and people like Grant producing these videos nowadays.
As someone who has participated and done decently in the USAMO and CMO (top 20 and top 5 respectively), you typically need to broaden your understanding rather than go into everything in depth. You're not expected to use analysis or topology, but you should know tons more algebraic tricks and ideas than what is taught in highschool. I still managed to do quite well despite not knowing calculus at the time that I did them.
@@ffc1a28c7 Are you Self taught and how did you know to avoid going in too much depth and rather concentrate usefully on algebraic tricks etc. What resources did/do you use?
Incredible video - I remember the Fourier transform video about "wrapping" functions around the unit circle (in the complex plane) and the complex part of this video was extremely reminiscent of that. So much so that I was able to follow along exactly where it was heading. That's when I realized that your videos have fundamentally allowed me to learn math and truly enjoy it. You are my favorite YT channel by far. THANK YOU!
It should look reminiscent, because it's the exact same technique. What he's actually doing here is, he's evaluating the discrete Fourier transform (DFT). At 17:14 he acknowledges that. If you look at the equation with the sum symbol, and plug the phi into it, it's the formula for DFT (or rather, for its value at carefully chosen frequency).
The next step in the learning process is to see how this technique generalizes.
@@KohuGaly Fourier transforms are my favorite... They are just so fascinating. I recognized it was an extremely similar process but I didn't feel fully confident in labelling it as the same because I'm not an expert in any way. Thank you for your explanation! I appreciate it a lot!
@@KohuGaly that’s where he got the idea of wrapping frequencies around a circle to explain how the FT works! I feel I should have known it...
I'm a math student and teacher (10-14y/o students). This was one amazing presentation of a "simple" question and a solution I could follow seamlessly even though I'm not a genius nor a professional mathematician. Love the simplicity in the design choices and the passion that was put into this!
Always a blast listening to your work!!
Love from Austria ;)
Having just finished studying some undergraduate level abstract algebra, this video gave me a greater understanding roots of unity and their applications. Your work never fails to both stimulate the creative mathematician in each of us as well as supplement our previous education with new insight. What a gift this channel is, I cannot wait to see what it continues to give in the future. Thank you, Grant, for everything you do.
I'm not the kind of viewer that pauses and try to solve the problems by myself because I know I'm getting nowhere, but I watch all your videos and come back to watch them again after a while and it's surprising that, even if don't remember the steps to the solution, it gets less magical and starts to sound more like something that I would have come up by myself.
Thanks!
I remember a time in math class doing series where I wanted to "filter" only odd numbers for some simple sine series, and ended up using a trick with powers of negative one. It's awesome to learn that not only is that technique actually used in practice, but there's a much cooler version out there as well (and yet another use for Very Cool complex numbers :) )
yeah back in my mathcounts days I even managed to discover up to using powers of i (4th root of unity) but I didn't make the connection to arbitrary roots of unity until later
Your videos are like a well narrated detective story where a seemingly difficult problem slowly reveals its solution. It's just mesmerizing.
To be fair, I think he over-complicated the beginning. You could ask some pre-algebra students to list all the ways to use the numbers 1,2,3,4,5,6,7 to add up to something like 11 (using each number at most) and put them in a column. And then ask them to list all the terms in the expansion of (1+x)(1+x^2)(1+x^3)(1+x^4)(1+x^5)(1+x^6)(1+x^7) that give you x^11 and put them in a column. Comparing the columns side-by-side makes the correspondence clear.
Column A Column B
---------------- ----------------
x^(7+4) 7+4
x^(6+5) 6+5
x^(7+3+1) 7+3+1
x^(6+4+1) 6+4+1
x^(6+3+2) 6+3+2
x^(5+4+2) 5+4+2
x^(5+3+2+1) 5+3+2+1
(not sure if the columns will be aligned correctly after I post)
The pre-algebra students would not have the knowledge to follow the roots of unity filter for the powers of 5. But they might be able to handle it for powers of 4. Because the 4th roots of unity are just 1, -1, i, -i. Even the final step where you plug the roots of unity into (1+x)(1+x^2)(1+x^3)(1+x^4) becomes a lot more simple because many factors are simply 0 unlike with 5th roots of unity. So if you took this problem and changed it from multiples of 5 to multiples of 4, you would still have a solution that used polynomials and imaginary numbers to solve a problem whose answer is a real integer, so it would maintain the weirdness, but it would be approachable to a much younger audience.
This feels very much like my real analysis class: I can see what you're doing and how you got there, and it's very impressive, but there's no way I could do it myself.
You will get there. In a couple years you will look back at the problems you are struggling with now and wonder what the hell was stopping you from seeing what now feels like an braindead obvious idea. It happens to all of us.
@@connordavis4766 that's how one learns mathematics. Get stumped, let the unconscious mind work-out the details, and in a matter of time the answers seem as obvious as arithmetic.
My math professor once said something that changed the way how I saw math - he said (when discussing a new PDE) - "if this doesn't make sense to you, don't worry about, it's not supposed to, but once you repeat it enough times it will become natural, like 2+2"
"The first time it's a trick, the second time it's a technique." -- my PDE prof
This channel doesn’t make bad videos. The quality is there in every video. You can tell they are not throwing up videos just to put up content. There’s real effort and thought involved in each video.
When I was doing my undergraduate course in physics, I fell In love with complex analysis. A way to re-think older problems (infinite trig integrals etc.) with seemingly disconnected injections of complex numbers. But the fact that they *arent* at all disconnected is the beauty in it. Its not 'imaginary' but a very real expression of the root of mathematics (ergo, logic). Probably one of the hardest courses I took. And absolutely my favourite. I wish I had more opportunity in my professional life to get back into complex analysis. For now I think I'm going to just dig up my old notebooks.
I'm so excited for that Riemann zeta function video - the old one on analytic continuation is one of my all time favourites on this channel, I watched it just after learning what complex numbers even are. And now look how far we've come... I've even come to actually _like_ complex numbers in the mean time...
What I really like about this is that literally anyone who understands the problem can come up with a pretty accurate guess. The error would only be 1/2^1598 of the real answer!
You mean 1/2^1798, but that's even better!
@@sciencedoneright Isn't it 1/2^1598?
The answer is (1/5) * (2^2000 + 4*2^400) which is the same as (1/5) * (2^2000 + 2^402)
The difference between the guess and the correct answer is (1/5) * 2^402
so the fraction of the final answer would be (1/5) * 2^402 / (1/5) * (2^2000 + 2^402)
which is approximately 2^402 / 2^2000
which is 1 / 2^1598, right? Is the approximation wrong?
If you consider that the 400 numbers divisible by 5 make no contribution to the sum, you can see that the answer has to be divisible by 2^400. If you then minimise the error, you get the correct answer: 2^400 x ((2^1600-1)/5 +1).
This makes me nostalgic. Remembering my high school days in the IMO training camp, solving these problems. Didn't make it to the team by a few marks, but enjoyed the experience a lot. Those were the days.....
I want to thank you for this channel. A video a saw here last year was the spark that was missing to ignite strongly enough my desire to pursue a master degree and, despite all the fears and challenges I knew I'd have to overcome by going through with this, finally apply.
And now that I'm here trying to conciliate work with the academic life - and also with having a life -, this is, again, the kind of content that reminds me of the passion I feel for the field and that can feel distant when we're struggling in the routine.
Thank you so much for coming to Tufts! It was so great seeing your work and meeting you! I also love how you’re incorporate the “live” elements where you can see the use of a cursor like in a more traditional lecture to expand and clarify elements. Such a great style!
With some friends we mapped this problem to a constrained spin model and the results gives exactly back the polynomial you were talking about.
I literally cried seeing the solution finally works out. It is so satisfying. Math will never die. Thank you for making this video, for preserving knowledge and stimulating curiosity.
your funny lol
@@austinmchaney what about their funny
@@dpage446 why would you cry when you can watch the video again?
@@austinmchaney what did his funny do?
what
Thanks! This is such a brilliant explanation. Really appreciate the effort which went into making this video so clear.
On a side note, 27:57 "The expression ... is almost identical... it just has minus sign" -- this is not the only difference, as the powers in the top expression go from 1 to 5, and the powers in the new expression are from 0 to 4. Of course ζ⁵ = ζ⁰ by earlier argument, but this was slightly unclear. Same at 28:22 "the right hand side turns into the thing that we want to evaluate", again not quite.
When I stumbled upon this video when it first came out, I paused and tried to solve the puzzle. Today, I solved it, and it happens that my method is very similar to yours (or quite identical until the very end). But the way I created the generating function didn't involve a leap of faith, quite the contrary. I didn't read all the other comments to see if someone else brought it up, but here's how I worked it out :
I think of the subsets of {1,2,...,n} as blocks that I stack in columns. Each column is labeled 0, 1, 2, and so on. Those labels represent the possible sums of subsets. When a subset has a sum of 6, I place its block in the 6-labeled column and so on.
It's easy to see how to generate the subsets of {1,2,...,n} if you already know the subsets of {1,2,...,n-1} : take all the previous subsets, copy them and add the element "n" to each new copy. Consequently, the sums of those new copies of subsets are all the original sums +n, thus the copied blocks are to be shifted by "n" and then stacked on top of the original ones.
Now, if you think of the number of blocks in each labeled column as coefficients in front of powers of x (the k-th power is the k-th column), then everything comes around quite nicely. Assume you know the polynomial associated with {1,2,...,n-1} (let's call it p_{n-1}(x) ), then to generate the next polynomial, add p_{n-1} to a shifted version of p_{n-1} (to emulate what we did with the blocks). To shift all the coefficients, simply multiply the copy of p_{n-1} by x^n. Therefore, p_{n} = p_{n-1} + x^n • p_{n-1}. Factor p_{n-1} and you get : p_{n} = p_{n-1} • (1 + x^n). Unroll this product recursively and you get the polynomial in its product form. Voila, no leap of faith!
Beautiful video. The answer is striking and as another poster mentioned, it is reminiscent of Burnside's theorem. I'll outline a solution below.
Imagine 400 "concentric" pentagons. Label the vertices of the innermost pentagon 1-5, with 1 at the top, proceeding clockwise. On the next largest pentagon, label the vertices 6-10, 6 at the top, proceeding clockwise again. Now, color the vertices with one of 2 colors, say red or green. If the pentagon is fixed, there are 2^2000 ways to do this. When vertex is green, include it in the subset, exclude if it's red. Consider two colorings equivalent if one can be obtained from the other by a rotation of 0, 72, 144, 216, or 288 degrees. By Polya's enumeration/Burnside, there are (1/5)*(2^2000 + 4*2^400) ways to color the vertices. The catch is that in each group of equivalent colorings, one and only one set of green-colored vertices will be a multiple of 5. Thus, the number of colorings is equal to the number of subsets whose sum is a multiple of 5.
To see this a bit better, for the simpler {1,2,3,4,5} case, consider just one pentagon and suppose three consecutive vertices are colored green, the other two red. This corresponds to the five 3-element subsets {1,2,3}, {2,3,4}, {3,4,5}, {4,5,1}, and {5,1,2}. Only one of these, {4,5,1}, has a sum that is a multiple of 5.
Edit: Spelling
I don’t see how this is correct.
Consider the colouring {1,6,11,16,21} which sums to 55. Rotated this gives {2,7,12,17,22} which sums to 60, and so on. So all sets in this group of equivalent colourings sum to a multiple of 5.
@@Simon-ts9fu Right! Back to the drawing board for me. I was looking for something with 5-fold symmetry and at first, I was thinking of a 2000-gon, but then this idea of nested pentagons came to mind. I'll give this some thought and if (when!) I think of a different way to interpret this, I'll reply again.
@@Simon-ts9fu I think I have a fix for my original argument. If the size of the set is not a multiple of 5, it should still work. If it is a multiple of 5, then either every pentagon is uniformly colored (in each pentagon, all are red or all are green) or there is some pentagon that has a mixture of red and green vertices. If all are uniformly colored, all rotations produce the same sets. If there is some pentagon that has a mixture of red and green vertices, find the pentagon of this type closest to the center. When the pentagon is rotated, rotate all labels except for this special pentagon. In your example, the 1 in the set {1,6,11,16,21} would remain unchanged, so the next set would be {1,7,12,17,22}. The argument isn’t as elegant as I would like it to be, but it works.
The problem was hard enough. Explaining it in such a thorough yet engaging way is even harder. Hats off to 3Blue1Brown for this one.
This reminds me a lot of Burnside's theorem, without having to go through understanding groups, orbits, or stabilizers. Amazing video!
The lemma formerly known as Burnsides
It can be solved this way. I added a comment elsewhere with an outline of how it can be done. Let me know if you can’t find it and I’ll explain again.
I've been watching this channel since i was in my second last year of highschool, I'm now in my third year of my bachelor's in pure math and this channel still amazes me every time, the videos are accessible even to people with hither to no background in mathematics and yet are full of insights that even three years after embarking on a formal education journey in pure maths, the quality and entertainment value of the videos on this channel never ceases to amaze me
This channel is a true treasure. Thank you so, so much for sharing, educating, and engendering a sense of wonder and discovery in us all. 🌱
16:19 - The reasoning of this “trick” is just perfect. This makes this whole process much more intuitive.
Yeah! New 3blue1brown video= 5 hours of enjoyment and math pondering
That's what I love to hear, sounds like you'll be doing the homework from the end?
I saw the first problem, and noticed that I've solved it earlier by monte carlo simulation, but I've never thought about doing it in another way! Now I'm really pondering about it
@@3blue1brown Yeah definitely! Except maybe problem 1 since I haven't learnt yet calculus in a formal way
Absolutely astonished by the visual style of this video and how it differs from others in the channel, it embodies a form of storytelling and the math parts are presented much more like a DIY thing than a "let the screen do the math" which was absolutely perfect for this kind of problem-solving video, looking forward to other beautiful ways you can present math but also more of this kind of style. These type of videos are what embodies my love for math and education and I'm completely thrilled for what other ways of story telling and teaching math you can scheme. Thanks as always Grant, this was amazing.
I am not sure, that I understood even the 20 % of the video, but I am sure, that this guy is brilliant
he is very brilliant but he mentions he never was a savant of any kind, he has spent countless hours studying math and coming to realizations and learned hwo to communicate rather complex stuff to us in such a beautiful way with amazing animations! they just get better and better. we live in a time where we get this kind of explanation on youtube, for absolutely free. Makes me sad most people watch endless tiktoks without learning anything but nonsense, instead of devoting an hour a day to learn some stuff like this! not applicable to many lives i guess but i just cant but help to be fascinated by math,.
This is actually insane! When I first watched this video, I was so captivated by generating series and I looked for them in the descriptions of all the math classes at my uni. I found out a class that I was going to take in the Fall introduced them. It ended up being my favourite class so far and we also covered finding the closed form expression for recurrence relations like Fibonacci. I actually love this channel so much
Watching this while taking a course on groups, rings and fields ended up surprising me in the similarities between this and the Galois groups of field extensions. I think a video on abstract algebra could end up very interesting
literally same here
same
Can you please tell me more about courses
Screw the video. The world need “the essence of abstract algebra” series!
@@dhruv1614 what do you want to know?
Fantastic explanation. You took me from "I have no idea" to "oooooohhhh I could have come up with that" in 20 minutes!
and then when I actually try to come up with it on another olympiad problem, everything feels difficult again :') but it's nice to be able to follow the arguments haha
This is a trick that I've used countless times in high school math, yet I never imagined the connection between generating functions, the Riemann hypothesis and Fourier series. Truly marvellous.
I also wanted to thank you. It is because of educational creators of you, that I am now in one of the premiere mathematical institutions in my country. I never even imagined that I would get selected, I only gave the exam because I find math beautiful, and you, along with many other creators, I believe, are to thank for that. Love your vids.
Congratulations, I hope you enjoy your studies!
@@3blue1brown Thank you! :D
So I used to prepare for math olympiads a lot in high school, and a lot of problems involved analyzing a sequence defined by a recurrence relation. Just went through the first couple pages of generatingfunctionology and HOLY SHIT, how the hell did I not know this technique?! It's sooo useful and it's so simple.
Another fun way to get g(x)=2 would be to return to the simplified problem about {1,2,3,4,5} [where g(x)=(1+x)(1+x^2)...(1+x^5)]. We know the answer in this smaller case is 8. Therefore, (g(ζ)+g(ζ^2)+...+g(ζ^5))/5=8. From here we get g(ζ)=(40-2^5)/4=2.
Thanks for your stunning show, and a special thanks for the puzzles at the end!
There’s another nice way of solving this problem in log(n), where n is the size of the set (in this case, 2000) by exponentiating a 5x5 matrix! Generating functions are fun as well :)
Do you have a link for this method? I’d love to see how they do it
@@goblin5003 It's the matrix that transforms the vector containing the mod 5 totals after considering the first n numbers, into the mod 5 totals after considering the first n+5 numbers. Consider for example the totals at 5: 0 mod 5 will have 4 subsets: {}, {1,4}, {2,3}, {5}, 1 mod 5 has 3: {1}, {1, 5}, {2, 4}, and so on. Now consider the effect of adding just 6. We can either include or not include 6, which is 1 mod 5, which means that the entry in this vector for (as an example) 0 mod 5 up to n = 6 is the entry for 0 mod 5 when n=5 + the entry for 4 mod 5 when n=5. You can make a matrix for adding a number 0-4 mod 5, then multiply the matrix together to get the one that brings you from n to n+5. While all of the other matrices are different, this one is always the same, so you can repeatedly apply it. (From there, you can get an explicit formula again to solve it in O(1) time by using eigendecomposition/Jordan Normal Form. It's another, albeit less general, method of solving recurrence relations.)
I apologize if it's a bit confusing. RUclips comments are not the best place to communicate complex math ideas.
@@OmnipotentEntity do you have any link/reference to a webpage, book or video where this kind of procedure is applied? I didn't quite understand the logic behind it with just the comment :(
You can reduce the 5x5 matrix to 2x2
This channel is so underrated. The way you make something like this so interesting and so fun and easy to watch is so fascinating. Never thought I'd watch 32 minutes of complex math, understand it, and feel entertained while doing so. Thank you sir.
What do you mean by "underrated"? The channel has 5 million subscribers, despite being about math and usually diving deep into the topic. That's basically a miracle.
It's even surpassed Numberphile, despite being much less accessible (albeit, more beautiful).
In my set of discrete math courses in college, I was fortunate enough to learn about generating functions, and had the wonderful opportunity to explore them more in my senior thesis. My favorite generating functions are the rook polynomials! When you introduced the problem, I was immediately thinking “Hm, how would I make a generating function for that?” Awesome video as always!
yeah once you know the trick for generating function, for like huge huge sets or so, you kinda intuitively want to make a function with coefficients that are countable or reduce it by a margin! its really neat! i wish i could study more math for school, so expensive and cant right now, maybe one day ill be fortunate to finish my pure maths degree and get a masters after!
Thanks!
this was a rollercoaster ride through and through. never knew maths could be so intense
Here's another way to solve this problem, which also gives us the number of subsets whose sum is 1,2,3,4 mod 5 respectively too. The idea is taken from the book titled 'Problems From The Book', co-authored by Titu Andreescu as well:
Denote c₀, c₁, c₂, c₃, c₄ as the number of subsets whose sum is 0,1,2,3,4 mod 5 respectively, then taking f(x) = (1+x)(1+x²)...(1+x²⁰⁰⁰) evaluated at ζ, we have, by compiling coefficients congruent mod 5,
f(ζ) = c₀ + c₁ ζ + c₂ ζ² + c₃ ζ³ + c₄ ζ⁴.
But we know f(ζ)=2⁴⁰⁰ (The video has covered this). Therefore c₀ + c₁ ζ + c₂ ζ² + c₃ ζ³ + c₄ ζ⁴ = 2⁴⁰⁰, or equivalently
(c₀-2⁴⁰⁰) + c₁ ζ + c₂ ζ² + c₃ ζ³ + c₄ ζ⁴ = 0.
In the field of rational numbers, the polynomial 1+x+x²+x³+x⁴ is the minimal polynomial of ζ, so whenever ζ is a root of some a₀ + a₁x + a₂x² + a₃x³ + a₄x⁴ =0 where aᵢ are rational, then 1 + x + x² + x³ + x⁴ divides a₀ + a₁ x + a₂ x² + a₃ x³ + a₄ x⁴, or simply a₀=a₁=a₂=a₃=a₄.
Therefore c₀-2⁴⁰⁰=c₁=c₂=c₃=c₄. Since c₀+c₁+c₂+c₃+c₄=2²⁰⁰⁰, we get that
c₀=(2²⁰⁰⁰+4×2⁴⁰⁰)/5
c₁=(2²⁰⁰⁰-2⁴⁰⁰)/5
c₂=(2²⁰⁰⁰-2⁴⁰⁰)/5
c₃=(2²⁰⁰⁰-2⁴⁰⁰)/5
c₄=(2²⁰⁰⁰-2⁴⁰⁰)/5
So, not only have we found the number of subsets that have sum divisible by 5, we also found the number of subsets that sum up to other remainders modulo 5 too, and they are surprisingly evenly distributed! (However, take note that this method only works because 5 is prime, whereby we've used the fact that 1+x+x²+x³+x⁴ is irreducible in Q.)
yooo where are the pftb fans at?
Nice, thanks for sharing!
For anyone reading this: one should replace "real" with "rational" (minor nitpicking).
@@michamiskiewicz4036 Ah yes! Thanks for spotting my mistake.
We can always find all the other sums modulo 5 because f(ζ^n) = sum k=1->N of c_k ζ^nk are exactly the DFT coefficients of the sequence (well, up to some choice of convention for the scaling and sign of the powers). The inverse DFT in this case is then c_n = 1/N sum k=0->N-1 of f(ζ^k) ζ^-nk. For n=0, ζ^-nk = 1 for all the terms and we get the straight sum, but for the others we get something else. Actually, because our coefficients are real f(ζ^k) = f(conj(ζ^k)) = f(ζ^-k), and with the identity e^ix+e^-ix=2cos(x), we can actually say that c_n = f(1)/5 + 2/5 sum k=1->(N-1)/2 of f(ζ^k) cos(nk2pi/N). For this case that works out to c_n=/=0 = 2^2000/5 + 2/5*2^400*(cos(2pi/5) + cos(4pi/5)). Those cosines sum to -1/2, which gets the required c_n=/=0 = (2^2000-2^400)/5.
Consistently blown away by this channel, thank you again for explaining something I didn't know I wanted to know.
This was really cool! I learned about the roots of unity in my engineering program, but we never saw any applications of them. They were just an exercise in complex numbers. It's cool to see how they can be useful!
Another fun application: 19 year old Gauss used similar tricks with roots of unity to show that a regular 17-gon can be constructed with compass and straight edge, the first advance since the time of Euclid
I am really filled with lots of gratitude for you, Grant. This channel is really a boon. You tell us how to see it differently.
Just sent this to my former discrete math professor. I did an independent study with her on error correction codes where generating functions and roots of unity came up so I was so excited to share.
26:30 His breath of relief when it all comes together
ye
When I first encountered this problem (it was in fact the number of subsets of {1 .. 300} whose sum was divisible by 3), I came up with the following solution:
Generalized question: How many subsets of {0 .. 3n-1} are divisible by 3?
I will call this number a(n). I will call b(n) the number of subsets of {0 .. 3n-1} whose sum has rest 1 modulo 3. For symmetry reasons this is exactly half of all subsets which have a sum not divisible by 3.
It follows that a(n)+2*b(n)=2^3n
We now look at a(n)-b(n):
Simple case: n=1. We consider subsets of U={0..2}
Let f(x):=(x+1) mod 3. Then for each subset s let f(s)={f(x)|x€s}. It's easy to see that f³(s)=s for each subset s of U and that exactly one of s, f(s) and f²(s) has a sum divisible by 3 for any s - except s=U and s={}.
So of the 8 subsets of U, four subsets have a sum divisible by 3, two have a sum =1 mod 3 and two have a sum =2 mod 3.
We see that a(1)=4 and b(1)=2, so a(1)-b(1)=2.
We now assume that we know a(n) und b(n) for a specific n.
Let s be a subset of {0 .. 3n-1} and s0 be a subset of {0..2}. Let g(s,s0)=s U {3n+x|x€s0}. The sum of g(s,s0) equals the sum of the sums of s and s0 mod 3.
It's also easy to see that for every subset t of U={0 .. 3n+2} there is exactly one subset s of {0 .. 3n-1} and one subset s0 of {0..2} with t=g(s,s0).
A subset g(s,s0) of U has sum divisible by 3 iff either both sums are divisible by 3 or both sums are not divisible by 3 and have different rests mod 3. This leads to a(n+1)=a(1)*a(n)+2*b(1)*b(n) and b(n+1)=a(1)*b(n)+b(1)*a(n)+b(1)*b(n).
From this follows that a(n)-b(n)=2^n for every n.
Conclusion: b(n)=(2^(3n)-2^n)/3 and a(n)=(2^(3n)-2^n)/3+2^n
It's obviously irrelevant whether we look at the subsets of {0 .. 3n-1} or of {1 .. 3n}
The same reasoning also works for primes other than 3 and leads to
Let a(k,n) be the number of subsets of {1 .. k*n} whose sum is divisible by k. Let b(k,n) be the number of subsets of {1 .. k*n} whose sum has rest 1 mod k.
Then a(k,n) + (k-1)*b(k,n) = 2^(kn) and a(k,n) - b(k,n) = 2n,
so a(k,n) = (2^(kn)-2n)/k + 2n which in this case means there are (2^2000-2^400)/5 + 2^400 subsets of {1 .. 2000} whose sum is divisible by 5.
Seems I am more Bob than Alice.
The last two paragraphs preceding the final sentence should read as follows:
Then a(k,n) + (k-1)*b(k,n) = 2^(kn) and a(k,n) - b(k,n) = 2^n,
so a(k,n) = (2^(kn)-2n)/k + 2^n which in this case means there are (2^2000-2^400)/5 + 2^400 subsets of {1 .. 2000} whose sum is divisible by 5.
I can see the symmetry case for n=3 but for any prime larger then 3 how do we know that the subsets whose size equals 1,2,3,4, , , p-1 modulo p are of equal amount?@@michaelhaffer5639
This was one of the tougher videos for me to get through. It took a few attempts, however, my final watch through I feel like I unlocked a bit of knowledge for myself. Thanks. :)
honestly this video not only teaches math, but also teaches how to teach math. Everything you present is so elegant, every smallest detail is done with perfection which is just a cherry on top of a beautiful problem and solution you presented.
Oof man you have taken me on a trip and I just fucking love when there is craY craY nuances in a single problem. There is a reason why i recommend your videos to kids i used to teach. It deserves the praise and recognition it deserves ❤️🙏🏻
I solved this using induction of two linked series: An and Bn, where An represents the number of subsets of which the sum is divisible by 5 and Bn represents similar ones of which the remainder is 1, 2, 3 or 4. Of course, A1=8 and B1=6. We can work out: An+1=8An+24Bn and Bn+1=6An+26Bn. To check our work, we should see An+1 + 4*Bn+1 = 32*(An+4Bn). Great, as expected! Interestingly, we can notice An+1-Bn+1 = 2*(An-Bn). With these two, we can find out: An+4Bn = 32^n and An-Bn=2^n. Therefore, An = (32^n + 4*2^n) / 5. The answer of the original questions = A400. Tada :)
This is exactly how I solved it as well! I had the same equations, though with f=A and g=B. The A(n)-B(n) was the key and was somewhat surprising.
Awesome! I'd like to understand. Why is A_{n+1}=8An+24Bn and B_{n+1}=6An+26Bn? I can kind of see where the "8An' in "A_{n+1}=8An+24Bn" comes from - with A_{n+1} you're adding into consideration 5 new numbers whose remainders mod 5 are 0, 1, 2, 3, and 4 and there are 8 subsets of the 32 possible subsets of these 5 new numbers that have a sum that is divisible by 5; therefore, you can take each subset represented by An and join it with each of the 8 new subsets to get a subset that still sums to something divisible by 5.
But where does the "24Bn: in "A_{n+1}=8An+24Bn" come from? And where do the "6An" and "26Bn" in "B_{n+1}=6An+26Bn" come from?
@@joseville For the first 5 numbers, you have residuals of 0 8 times, and 1-4 6 times each. Consider what happens when you add the next 5 numbers. You will end up with a residual of 0 if you start at 0 with 8 combinations or start at one of the of other numbers with 6 combinations. so a(n+1)=8a(n) + 4*6B(n). You will end up with a residual of 1 if you start at 1 with 8 combinations (i.e. add 0), if you start at 0, with 6 combinations (i.e. add 1), and if you start at 2-4 with 6 combinations,. Thus b(n+1) = 6*a(n) + (8+3*6)b(n).
@34:11 :: The answer to prob 2 is 3^n .
This can be easily done by expanding Σ into
2⁰(nC0)+2¹(nC1)+2²(nC2)+.....+2^n(nCn).
If you know binomial theorem ,then you may see that it's in the form of (1+x)^n ,where x=2.
Hence,the required answer is 3^n.
I thought the same of the pascal binomial triangle 😊
right.
I might have stumbled upon generating functions, when I attempted to generalise some board game dice probabilities, but I was left at a standstill not knowing where to go... This has given me some Ideas for possibly solving a month long nightmare I had stuck in my head! thank you so much!
i have to admit, i was interrupted multiple times while watching this resulting in me watching this over the course of multiple days and definitely forgot we were solving for {1,...,2000} instead of {1,...,Infinite} and it suddenly makes a lot more sense at 29:03. Thanks to the power of Thanks.
It's really interesting that you are doing this whole problem with groups and polynomial rings without even mentioning them.
I enjoyed this video. Thanks
I am not done watching but I can tell this took a lot of effort to produce. I love your content. TY
This has to be among the highest forms of education ever made, amazing content as always dude
While you can't bruteforce this, it's possible to use dynamic programming for this problem.
Let's first look at the empty set {}, it has only one subset which is divisible by 5. so we have 1 subset with remainder of 0 and zero subsets with remainders of 1, 2, 3 and 4, let's write it down: (0:1, 1:0, 2:0, 3:0, 4:0)
Next step we add number 1 to the set. Now we have one extra subset with remainder of 1: (0:1, 1:1, 2:0, 3:0, 4:0)
What happens when we add 2? Every subset we had before will produce one extra subset by including 2 into them. So now we have one new subset with remainder of 3 and another one with remainder of 4: (0:1, 1:1, 2:1, 3:1, 4:0)
And when we add 3, previous subsets with remainders of 0 will produce new ones with remainders of 3, 1 => 4, 2 => 0, 3 => 1, 4 => 2: (0:2 1:2 2:1 3:2 4:1)
Similar:
{+4} (0:4 1:3 2:3 3:3 4:3)
{+5} (0:8 1:6 2:6 3:6 4:6) - as 5 is divisible by 5, adding it to every subset just doubles their amounts
{+6} (0:14 1:14 2:12 3:12 4:12)
and so on, let's code it:
#!/usr/bin/python
from decimal import *
def solve(n):
answer = [Decimal(1),Decimal(0),Decimal(0),Decimal(0),Decimal(0)]
for x in range(1,n+1):
r = x % 5
old_answer = answer[:]
for i in range(0,5):
answer[(i+r)%5] += old_answer[i]
return answer
a = solve(2000)
print(a[0])
print((Decimal(2)**2000 + 4*Decimal(2)**400)/5) # to compare with the answer given in the video
Output:
2.296261390548509048465666392E+601
2.296261390548509048465666402E+601
Sure it's not what this video is about, but maybe someone will find this useful for some reason? Also sorry for my bad english :(
And thanks for this amazing video which somehow was recommended for me!
That is some serious level of counting right there. WOW! You got the exact answer for a problem that would've taken eons to solve if one had brute forced it. I want this knowledge. This is some serious power.
Its so cool to finally be of age to watch these videos. Ive been watching numberphile, mathologer and you for the last 4 years but now im 18 so for the first time ever know what you're talking about.
Grant, as much as anyone, has changed how I view what education should be. And as valuable as the visuals are here, I'm sure he could do a reasonable facsimile with a whiteboard and lectern. It's all in the mystery.
And yes, I'm just ripping off the points he made in his TED talk. But he sure does walk the walk.
Every new video this man releases is an absolute treat!
Thank you 3b1b for bringing such amazing content to the public.
Давно дивлюсь цей канал англійською, але дякую тим, хто зробив переклад субтитрів українською. Тільки сьогодні дізнався, що автор каналу почав додавати переклади до своїх відеоматеріалів.
Thank you very much for the Ukrainian subtitles, @3Blue1Brown. I appreciate your work and educational videos and how much effort you put into them. You're a shiny diamond on the platform.
As a new math teacher, this channel reminds me how much left I have to learn. Every time I watch, I’m usually dumbfounded and unsure of the next step, but enjoy the process.
Today was the first time where I arrived at the answer before it was spoken. I was so excited I immediately used the idea of roots of unity to calculate how many subsets’ sums were divisible by 4, and 10, and I’m working on 7. Thanks for the fun watch, and thanks for always keeping me on my toes!
This is way above my level but yet I love this so much. This might honestly be my favorite video from you. I have been slowly losing interests in stuff, I barley have the motivation to do anything, I don't find the same pleasure of doing stuff I loved. However, with all those in mind, this managed to become my favorite video. Im so mad at myself for not watching this earlier, when my love for math was at its peak. Thank you for this video.
The complex number method is so brilliant, I don't find words to express how beautiful I find it, thank you for sharing all this with us
I got convinced to watch this video because of your tiktok. At 1am. This video was great and really clear. Going to sleep now.
Your animation makes understanding these things sooo much more easier , thanks for sharing
Just to clarify something: at 28:35, you say that the value of that polynomial is precisely two. When looking at the two equations that you are saying are equal, it appears that they wouldn't be, due to their differing exponents. The key is to remember that the (1+z^0) term on the bottom is the same as (1+z^5) term above.
thank you, i was following along nicely and that is where i lost track. how is (-1-z^0) the same as (1+z^0) !? so as you answer, they are not equivalent column by column, but there is an equivalent with one in a different spot.
English is my second language
And you confused the hell out of me when you said "it appears that they wouldnt be"
I understood that you were saying that they arent equal 🙂
@@VENOM-tx6gp Yup, double negatives can be quite confusing
@@pseudolullus my problem wasnt double negatives
My problem was what he wrote
@@VENOM-tx6gp there is a phenomenon in English language called double negation he isn’t referring to the math.
I went from not understanding generating functions to understanding them not so long ago, and I think the way they were introduced to me was very natural.
Generating functions for me started out as just a way to represent sequences of numbers which has very simple rules of addition and multiplication (just as you characterised them). It makes perfect sense if you want to evaluate the function at a point x, just the same for a polynomial. But when you consider representing combinatorial objects with generating functions, it turns out that construction of a combinatorial class using disjoint unions and cartesian products alligns beautifully with construction of generating functions using addition and multiplication.
To me introducing generating functions to a combinatorial problem is something like introducing calculations with algebra to geometrical problems. It's groundbreaking and very insightful, which is why I find the title of the video to be an understatement. It's not just the olympiad level counting, it's simply the most awesome way of counting!
I also appreciate the addition links. Thank you so much for the video!
There are channels which will show us solutions which are easy to understand, but this channel shows what we really need to know!!!!!!
This video is absolutely beautiful. It explains all concepts clearly and I love them.
Quick note on the side, this puzzle is also an interesting way to practice dynamic programming, a very important technique in the design and analysis of algorithms. The approach shown in the video is certainly more profound and beautiful.
How exactly would you make a dynamic programming algorithm to solve this puzzle? What I would think to do is
for a given number i (since the numbers are in order) the number of subsets up to 5 is just
dp [ i - 1 ] [5 - (i mod 5) mod 5 ]
where dp [ i ] [ j ] denotes the number of terms up to i that sum up to j (mod 5)
@@lintstudios3072 There's a tiny optimization, namely you don't need to keep as much history behind. You only need the previous and the current array of 5 elements.
Since the relation is linear there's another more important optimization of using matrices to skip through and lead to large amounts of i, but j must be fixed in that case.
@@lintstudios3072 My idea was basically what you described :)
Have loved this channel and the videos since high school days, and still love them as I just graduated from university!
Having studied some discrete math in university over the past 4 years, at 7:45 it suddenly clicked and I was screaming "Fourier" in my head.
I just wanted to add that the "leap of faith" that Grant was talking about is truly mindblowing when you first see it, but truth is, once you've studied enough math, it almost ceases to be a leap at all. When I was learning about Discrete/Fast Fourier Transforms (DFT/FFT), it was very clear that these polynomials were related to sets, subsets, sums of subsets, and complex numbers. In fact, in computer science the fastest known way to count subsets with fixed sums is by using FFT, which directly means using these polynomials with special coefficients, and evaluating them at roots of unity (complex numbers). Turns out that the fastest known way to simply multiply two numbers also involves the same technique.
But to the highschool me, I would not have known any of these at all and they would have been straight up black magic. I guess to justify Grant's supposed "leap of faith", you could say that once you discover Fourier Transforms, it becomes a tool that becomes natural to use in these situations, so you will be able to naturally arrive at this "leap of faith". But the first time you see it is definitely nothing short of a giant leap of faith into some devilish witchcraft that turns out to be a heavenly miracle instead. Props to Fourier for finding it first though, I can't imagine how much ingenuity it took for him.
I just felt down the chair listening to you. Wonderful, I never got in touch with generating function and the (generic) usefulness of the complex plane for extracting the correct coefficients of a polynomial function ... and now I have a *visual* of this all. Thanks a lot I learned a lot.
Mind blowing!! And the visual presentation was so elegant! Thanks - This is why I keep coming back to 3B1B
When I started thinking about the solution - before I played the full video, I was thinking we just need a set of 400 copies of 1, 2, 3, 4, 5, then I did the ways 5, 10, 15 could be broken up with these numbers (I did not consider 0 as fitting the answer...)., and then........ I was stuck.
After seeing the video and the elegant solution, on a Friday night, I will sleep well with a smile on my face!
In an IMO environment you'd probably solve this by induction on set size (jumping by 5s, so start with the set 1 to 5, then go from 1 to n to 1 to n+5). Once you see a path to a solution in an IMO it's best to punch the solution out rather than look for a more elegant option.
Still I really love the intuitive leaps here.
Very interesting. I did think that this generative functions tool was a rather complex (no pun intended) tool for a competitive mathematician to have in their belt
@@richardpike8748 I recall being taught this in IMO training but never using it in any exam conditions.
I'm proud to say that just when grant said what about negative 1 I immediately figured out how complex numbers come into play
I know it when Grant mention (f(1)+f(-1))/2 and I thought "Wait a damn minute. Hooooly."
same
Yeah
The moment you showed the circle and mentioned the roots of unity, I instantly made the connection to Fourier transforms and how this was in some ways a frequency question. But I’d love to hear more about that connection! Like why exactly does this question look so similar to the intuition we use for Fourier transforms?
From some cursory googling, it seems that the Fast Fourier Transform takes advantage of the connection to the roots of unity- my guess is that just tinkering with the roots of unity will land you at this “raising roots to powers -> permuting them” connection. I also think thats the basis for the non-Galois Theory proof of the insolvability of the quintic
There is another way to solve that uses the discrete Fourier transform. As in the video, if we try this with n=5, there are 8 subsets that sum to 5. There are also 6 subsets where the sum divided by 5 has remainder 1, and 6 each with remainder 2, 3, and 4 as well. There's a matrix A that describes this, it's the matrix with 8 on each diagonal element, and 6 on each off-diagonal. Then the number of subsets that Grant is looking for is the 1,1 element (the upper left element) of A^(400).
The matrix A can be raised to a high power easily by diagonalizing it, that is, by finding a matrix T such that D=TAT^{-1} is diagonal, because then A^m = T^(-1}D^{m}T, and it's easy to raise a diagonal matrix to a power. The matrix T that does this is the discrete Fourier transform matrix! The DFT matrix always diagonalizes circulant matrices, which A is.(A is circulant because the addition table for modular arithmetic is circulant.) Diagonalizing gives D = diag(32,2,2,2,2), which explains why the answer includes terms like 32^400 and 2^400. The 1/5 shows up because the inverse of T is the complex conjugate transpose of T, divided by 5.
Congratulations, your title change worked. I opened this video a few days ago in a tab and but never watched it. And now I opened it again with the new title, and I thought it looked familiar. So now I have this video open in two different tabs, same video and URL, but different titles 😂
Danke!