This video stands alone but also continues from the previous induction video at ua-cam.com/video/bylFzBxzQ9M/v-deo.html Induction bonus video on Numberphile2 at: ua-cam.com/video/P-NVuOTsetM/v-deo.html More Zvezda on Numberphile: bit.ly/zvezda_videos
@@Dae-Ying-Kim12345 This problem is only concerned with pairs (a,b) that yield integer ratios. In other words, you can get non-integers, and you can get perfect squares, but you cannot get integers which are not perfect squares.
oh my god at 3:35 in the Terry Tao interview video he talks about "tracking down a Romanian woman who'd solved it cause it was really bugging me" It goes full circle!
@@mayshackNot necessarily, because you already know how to solve 2+2, you do not need to figure out how to solve addition. While Stankova needed to figure out how to do it, and then actually execute. Even knowing that it was an induction problem, my first instinct is to show that (a,b) = (1,1) works and then assume (a,b) works and show that (a,b+1) works like how induction is normally taught. Coming up with the idea to bring the numbers down towards 0 by looking at the square itself seems absurd to me.
There are 2 scary things about this problem: a) I can follow the proof but couldn't possibly come up with it from scratch b) Somone thought of it So credits to: 1) all solvers 2) the problem setter 3) Zvezdelina and this video for the explanation
I've watched every single Numberphile video. I can confidently say that this is the best video you've made, Brady. Great speaker, great interviewer, one part story, one part theory; very well balanced. Zvezda is amazing; her story is moving and inspiring. I'm a college math teacher so I love your channel, but this video is top notch.
Tao actually talked about his interaction with Zvezda in the Numberphile interview. However, his memory was a bit hazy, so he misremembered her as "Romanian" lol
Fun fact, Nicușor Dan, the current mayor of Bucharest, the capital city of Romania, was there as well and he got a gold medal as he solved all the questions with a perfect score.
@@MrIStillDontCare Romania actually had two members (out of six) with perfect scores that year. The country tied with China for second place (based on their team scores).
@@howard5992 Yes, Adrian Vasiu was the 2nd Romanian with a gold medal while the other 4 people got silver medals in 88'. Even more impressive in my opinion is that both Nicușor and Adrian also got gold in 87' as well, they were among the 5 (out of six) Romanian gold medalists in 87'.
So far I've seen 3 videos on this amazing and legendary Question #6. One by a mathematician who wasn't at the competition and took a year to crack it. The video with Terence Tao. And now this video which I find the most fascinating because it had detail that Terence Tao himself forgot, like asking Stankova for a hint to the question after the competition. I guess this whole affair puts me into a mood thinking about how all these lives are intertwined by even an unlikely thing like a maths question.
A Swiss participant accidentally fell asleep during the exam and he didn’t even finish the problems lol. The proctors asked if he was okay and he said he was thinking really hard.
I feel like a _slightly_ nicer solution would be to use the fact that the pair (a, b) gives the same r as the pair (b, a), which enables you to always rewrite it such that a >= b. This means that you only have to consider 1 quadratic and every step is "reduce a_n, flip a_n and b_n". Slightly more streamlined than having to "choose" which one to reduce first IMO.
I'm getting the strong feeling that someone should write a book about Question 6 (and the answer). Start with the history of the International Math Olympiad, then get into how contestants are chosen, who comes up with the questions. And (if possible) who came up with Question 6 - the whole story behind it, and what the organizers expected from the Olympians. THEN get into the solution - complete with the background on quadratic equations and Vieta's Formulas......
I'm getting a strong feeling, that I'm perfectly sure who should be this someone to write the book. Zvezda, I'll be the first one in the queue for preorders!
Why stop at a book? Someone should direct a psychological thriller about a group of mathematicians whose lives are all loosely intertwined due to them all being haunted by the evil of Question Six.
The evidence proving that the sequence always converges to one zero term was spread out through the video and not explained super thoroughly, so to recap: Every time you perform a reduction, at least one of the numbers is guaranteed to decrease by an integer amount. Also, Zvezda proved using Vietta's theorem that because the new number found in the reduction is a root of a specific quadratic polynomial, the theorem shows that this new root must be non-negative. Therefore, if at each step the numbers must strictly decrease by an integer amount, and the numbers cannot be negative, there exists a step after a finite number of iterations at which one of the numbers is guaranteed to be zero. In a computer science setting we'd call this proof by entropy.
Zvezda is so expressive, passionate and enthusiastic. I'd love to watch a collaboration between her and Cliff Stoll on a numberphile video. I wonder how it would be. Thank you Zvezda, thank you Brandy. ;)
Very nice proof and explanation. If I had no clue I would start trying solutions with small numbers and try to see if I could find structure. I can imagine I could find a solution eventually but certainly not in 20 minutes. Looking how Zvezdelina explained it, I now can at least imagine how she could solve this so quickly. Vieta's formulas, induction, root exchange, symmetry, the importance of a factor being allowed to be zero, etc. are really part of her native language and she understand the full impact.
Let's define: k = (a^2 + b^2) / (ab + 1) Since ab + 1 divides a^2 + b^2, we know that k is a positive integer. Our goal is to show that k is a perfect square. Finding a Recursive Relationship: Consider the expressions: A = b B = kb - a If we substitute these into A^2 + B^2 and simplify, we get: A^2 + B^2 = b^2 + (kb - a)^2 = b^2 + k^2b^2 - 2kab + a^2 = (k^2 + 1)b^2 - 2kab + a^2 = k(kb^2 - 2ab + a^2/k) = k(AB + 1) [Using the value of k] Descending a Ladder: Notice an exciting property: A^2 + B^2 is again of the same form as our original expression (a^2 + b^2), with the added bonus that A^2 + B^2 = k(AB + 1). This gives us a way to create a chain of numbers related to the original a and b, where at each step we get values similar in structure, with the same value of k. Base Case: We can continue creating smaller pairs (A, B) at each step. To end this descent, we'll eventually hit a case where either a or b (Assume 'a' without loss of generality) becomes 0. If a = 0, then from the original equation: b^2 = k(0 * b + 1) => k = b^2 In this scenario, k is obviously a perfect square. The Contradiction: Assume k is not a perfect square. Then, since its an integer it has some unique prime factorization. Using our recursive step with this non-square k, we can descend to smaller and smaller positive integer pairs (a, b). At each step, k remains the same. However, this descent of a and b is bounded by them being positive integers. We cannot keep "splitting" the prime factors in k indefinitely with smaller integers! There must be a step where this descent cannot progress. This contradicts our assumption that k is not a perfect square. Therefore, k must be the square of an integer. Additional Notes: There are multiple approaches to this proof. This one establishes a recursive descent. This result has a beautiful geometric interpretation involving Pythagorean triples.
Once you have a pair that contains zero, it occurs to me that you can work backwards starting with ANY natural number as it's mate. And 'r' for the particular solution is the square of that number.
That was so incredibly elegant! It gave so much insight into the structure of the object in such a simple algorithm. I'm actually in awe. I'd love to see Zvezda's variation, too. Is that recorded anywhere?
Hearing 'number theory', my brain goes straight to modulus, divisibility, and primes, and I can't help but feel like the 'constantly lowering the one of the inputs' part of the proof feels a lot like the Euclidean Algorithm. I wonder if the two are related somehow.
There's only one negative integer solution to the equation which is -5. The 8 non reducible sets of a and b are (-1,2) (-1,3) (2,-1) (3,-1) (1,-2) (1,-3) (-2,1) and (-3,1) and with these you can Vieta jump to larger absolute values. Like -5(3) - (-1) yields -14,3
Both Zvezdelina and Emanouil managed to solve this problem that decorated mathematicians had trouble with. However, Zvezda's solution used a complicated method, which is kind of impressive in my opinion.
That's absolutely wild. It's not at all how I would've approached the problem, but I guess that's why I didn't go to the math olympiad. I really enjoyed how clearly every piece fell together by the end.
The pairs of integers that fit the equation are x^(2n-1) - (n-2)x^(2n-5) + T(n-4)x^(2n-9) - TT(n-6)x^(2n-13) + TTT(n-8)x^(2n-17) - TTTT(n-10)x^(2n-21) + ... where T(n) is the triangle number TT(n) is the triangle number of the triangle numbers and TTT(n) is the triangle number of the triangle numbers of the triangle numbers and so on. If you substitute n = n - 1 you get the other pair and if the power becomes negative you stop the formula. So if n = 11 you get a=(x^21 - 9x^17 + 28x^13 - 35x^9+15x^5- x) b= (x^19 - 8x^15 + 21x^11 - 20x^7 + 5x^3) cause T(11-4)=28 TT(11-6) = 1+3+6+10+15 =35 TTT(11-8) = 1+1+3+1+3+6=15 TTTT(11-10) =1 and T(10-4)=21 TT(10-6)=1+3+6+10=20 TTT(10-8) = 1+1+3=5. All the coefficients add to either (1,1) (1,0) (0,1) (0,-1) (-1,0) or (-1,-1) so that x = 1 will result in 1.
This is one of the best videos youve put out. Such a difficult problem, but the proof was crystal clear and presented wonderfully. Zvezdelina Stankova is legitimately one of the best Numberphile presenters, ever
I can see how that might work using Vieta's product formula alongside the reduction procedure, thereby keeping track of the relation between the members of the sequences a_n and b_n.
@@jeffkaylin892 It is mostly over my head but my understanding is that by continually reducing a or b eventually one of them is zero so you end up with r=a^2/1.
@@numberphile The initial part struck a cord with me. Being a programmer, (non-infinite) recursion always ends with a fixed point. This was like reversing it to find the algorithm. Extremely clever.
About induction : I propose a little problem which is a "remix" of an old one. The original problem is the famous twelve coins problem, studied in Martin Gardner's chronicles (among others) : You have an old weighing machine (type Roberval) only able to give the answer heavier, lighter or equal. You are given twelve coins apparently identical but one of them is heavier or lighter than all the others which have the same weight. You have to find the fake coin and tell if it's heavier or lighter in three weighings. I modified the statement this way : You have to tell the six (3x2) sets of coins to compare *before* the first weighing. Some sequels : - what if you are allowed four weighings - or any number n for that matter? - produce a generic - i.e. for any n - automatic algorithm to choose the sets and to give the result *at a glance*. To solve this you NEED induction.
I feel like this would be very easily understood as a solution using equivalence classes, where (a1,b1) ~ (a2, b2) iff their ratios are the same. Then, noting that (a,b)~(b,a) and calling a>b WLOG, using this induction to show that all equivalence classes can be described as (a_n, 0). However, for a solution found in 20 minutes this is still insanely impressive!!
At the end you can see that 2 of the gold medalists were from Romania and actualy Nicusor Dan won 2 such medals with maximum points in 2 consecutive years ('87 and '88). Nicusor Dan is now the mayor of Bucharest
This process can be modeled by a cluster algebra. So while it's always possible to reduce the size of the solution the opposite is true too, it's always possible to make the solution larger. Hence the maximum number of steps is unbounded
Zvezdelina, you are an amazingly lucky person! Of the tiny handful of pairs that produce a perfect square, you just happened to find the Wonka Bar with the golden ticket! 30 and 112, let me write those numbers down.
Is this induction though? I'd call it an invariant/variant method similar to proving a programming loop correct. The invariant is the ratio r and the variant is the smaller of the pair (a,b) which gets smaller on each iterative step.
Well, i'm not sure, but the terms might be slightly different in each language. Here there is an interative part, but the key property is that every decreasing sequence of natural integers is finite (actually we have to use an adequate mapping from N² to N). I personnaly would not call this induction, but i'm not shocked by the term.
I'm not a mathematician by any means. I decided that I had to watch Simon Pampena's "curve popping out the paper into 3D space" explanation (that was weird) and blackpenredpen's proof by contradiction (that was a bit more digestible) to have a chance to follow along with this one. And they helped, but the landing on this one really left me unconvinced. So what Zvezda's saying at the end is that any pair of a and b that satisfies r being a perfect square can be reduced so that either a or b is zero, right? Simon also did that from the other way around. But how is that exhaustive though? Like, how does that convince you that no other pair exist outside of the ones you're working with, and that those pairs aren't gonna spit our r being a non-perfect square integer?
The idea is that we can always do the reduction process to any pair that produces an integer solution. So even if there are some pairs out there doesn't belong to our chain of solutions, it has to belong to other chains of solutions since we've proven that we can always produce a chain given a pair. And at the end of that chain, we can always find a 0 in it. Funny enough, by that fact alone, you can also immediately see that there can only exist 1 chain since there can only exist one end of the chain which is (sqrt(r),0). Multiple chains can never share an end so there's really only one path.
27:56 Another big name appears on the list: Ngô Bào Châu from Vietnam got a perfect score (42)... years before moving to France and earning a Fields medal!
To summarise the proof (how it works) for those not actually looking for a proof but just wondering about the logic behind it: If the ratio r is fixed, we can decrease either the values a or b, because we can convert the equation to a quadratic, and just take the lower root of the quadratic (with respect to the smaller number, either a or b) which returns the same ratio r. Another concept to note is that the two roots of the quadratic, when summed, becomes the negative of the b term. (As in ax²+bx+c) Since the b term of the quadratic is always negative, the lower root can never be negative. But since the lower root can always be decreased, we will reach a point where either a or b becomes zero. Let's assume a becomes zero, b²/(1+0b)=b² And vice versa Thus it is always a square
How do we guarantee that the algorithm produces a zero eventually? I haven’t done the details but perhaps the sequence is nonnegative and decreasing will always produce 0?
Yeah, so long as you're non-negative and decreasing by at least some fixed finite amount each time (since you're working with integers here, you can't decrease by less than 1), you have to stop after a finite number of steps. If you can continue for any non-zero value, then the only possible final number is 0, so you must reach it eventually.
Since we are dealing with integers we know that our decreasing sequence decreases by at least 1 each step so if we started from n, it will take at most n steps to reach 0. Solutions of the equation (a^2+b^2)/(1+ab)=r , have the property that if (a,b) is a solution then (-a,-b) is also a solution. It is also true that a*b must be greater or equal to 0 (I won't prove it here). So how can we go from the non-negative solutions to the non- positive ones using Vieta's formulas where we can change only 1 of the 2 numbers at a time? We need a number a where (a,b) a solution, a, b>=0 and (a,b') also solution, a, b'
This video stands alone but also continues from the previous induction video at ua-cam.com/video/bylFzBxzQ9M/v-deo.html
Induction bonus video on Numberphile2 at: ua-cam.com/video/P-NVuOTsetM/v-deo.html
More Zvezda on Numberphile: bit.ly/zvezda_videos
I think any video about induction has to be based upon a previous video about induction.
@@walterkipferl6729 Except for the base video, of course
* In the part 4:02,
I feel weird :
if ( a,b ) = ( 4 , 4 ) then [ a^2+b^2 ] / [ 1+a*b ] = [ 4^2+4^2 ] / [ 1+4*4 ] ........... it is [ 16+16 ] / [ 1+4*4 ] = 32 / 17 totally not perfect square ...........
if ( a,b ) = ( 4 , 3 ) then [ a^2+b^2 ] / [ 1+a*b ] = [ 4^2+3^2 ] / [ 1+4*3 ] ...........it is [ 16+9 ] / [ 1+12 ] = 25 / 13 totally not perfect square ........... * what's going on ........... *
@@Dae-Ying-Kim12345 This problem is only concerned with pairs (a,b) that yield integer ratios. In other words, you can get non-integers, and you can get perfect squares, but you cannot get integers which are not perfect squares.
@@zmaj12321 The base case is Aristotle's definition of induction. Everything else is based on that.
oh my god at 3:35 in the Terry Tao interview video he talks about "tracking down a Romanian woman who'd solved it cause it was really bugging me"
It goes full circle!
solved the question in 20 minutes, needed 28 minutes to explain it to us ... Madam you are a living LEGEND !
😅😂
@@mayshack broooo😅😂
Bruce Lee's motions had to be slowed down for camera to capture it at 24 FPS for us. This is the same.
@@mayshackNot necessarily, because you already know how to solve 2+2, you do not need to figure out how to solve addition. While Stankova needed to figure out how to do it, and then actually execute. Even knowing that it was an induction problem, my first instinct is to show that (a,b) = (1,1) works and then assume (a,b) works and show that (a,b+1) works like how induction is normally taught. Coming up with the idea to bring the numbers down towards 0 by looking at the square itself seems absurd to me.
@@itioticginger9520 haha not if you’re showing 2+2=4 with axioms
You're a lovely person Zvezda. thank you for your brilliant way of explaining and your enthousiasm.
Please, please have more videos with her. She's delightul to listen to and so brilliant.
There are 2 scary things about this problem:
a) I can follow the proof but couldn't possibly come up with it from scratch
b) Somone thought of it
So credits to:
1) all solvers
2) the problem setter
3) Zvezdelina and this video for the explanation
Welcome to a world where P and NP are (apparently) different things.
I can quite easily follow the proof but could never be able to explain it myself. Let alone with such passion, enthusiasm and brilliancy
Welp, that feels so simple even though the only thing I barely know how to word with is functions (just entered calculus)
not everyone who can appreciate music be Mozart and not everyone who can follow a step by step argument be gauss
false.
I've watched every single Numberphile video. I can confidently say that this is the best video you've made, Brady. Great speaker, great interviewer, one part story, one part theory; very well balanced. Zvezda is amazing; her story is moving and inspiring. I'm a college math teacher so I love your channel, but this video is top notch.
if you like that one i recomend proof of ptolemys theorem. i watch that every 6 month on average :D
Wow. Zvezda.... bravo.
Absolutely same.
??
One of my favourite videos from Numberphile, thank you Zvezdelina you are outstanding.
There's a joke to be made about how every video you watch just makes you want to watch one more video.
😀 Infinite induction
All you need now is to watch a video
Let V be the number of videos you want to watch.
V=V+1.
+
I've heard if you ever watch them all you get to meet David Hilbert in the Grand Hotel.
I love how she explains things
More of Zvezda! No spoon feeding the audience. Straight and to the point. And so clear you can understand it immediately. That’s what maths is about!
Tao actually talked about his interaction with Zvezda in the Numberphile interview. However, his memory was a bit hazy, so he misremembered her as "Romanian" lol
What a crossover!
Well Romania and Bulgaria being neighbors, understandable mistake 😅
Fun fact, Nicușor Dan, the current mayor of Bucharest, the capital city of Romania, was there as well and he got a gold medal as he solved all the questions with a perfect score.
@@MrIStillDontCare Romania actually had two members (out of six) with perfect scores that year. The country tied with China for second place (based on their team scores).
@@howard5992 Yes, Adrian Vasiu was the 2nd Romanian with a gold medal while the other 4 people got silver medals in 88'.
Even more impressive in my opinion is that both Nicușor and Adrian also got gold in 87' as well, they were among the 5 (out of six) Romanian gold medalists in 87'.
Professor Stankova is an outstanding presenter. Her students are really blessed.
Students can barely solve 1 problem in 4.5hrs and she solved all 3 in 1hr 20mins perfectly scoring 7 in all 3 of them. Pure genius❤❤
Amazing, both the proof and the history behind it. I wouldn't have made this a hidden follow-up video.
Not hidden anymore :^)
made this?
??
So far I've seen 3 videos on this amazing and legendary Question #6. One by a mathematician who wasn't at the competition and took a year to crack it. The video with Terence Tao. And now this video which I find the most fascinating because it had detail that Terence Tao himself forgot, like asking Stankova for a hint to the question after the competition. I guess this whole affair puts me into a mood thinking about how all these lives are intertwined by even an unlikely thing like a maths question.
Imagine falling asleep in the IMO and still getting a medal
badass award
Such a power move.
A Swiss participant accidentally fell asleep during the exam and he didn’t even finish the problems lol. The proctors asked if he was okay and he said he was thinking really hard.
the part at the beginning just talking about the olympiad as a "moment of no return" for her life is a really powerful anecdote, wow!
in the screenshot of the results you'll see she got P4, P5 AND p6 done with full marks in 1h20, what a flex!
17:21: "...We need to wrap this in a technical package so that it fits in our vehicle of induction". I love that. Epic.
You can see how math is a bit like programming: you also need glue code.
I feel like a _slightly_ nicer solution would be to use the fact that the pair (a, b) gives the same r as the pair (b, a), which enables you to always rewrite it such that a >= b. This means that you only have to consider 1 quadratic and every step is "reduce a_n, flip a_n and b_n". Slightly more streamlined than having to "choose" which one to reduce first IMO.
Neat!
Dont you still have to prove that you always hit a zero in the end?
@@broccoloodle You say "both", but it's just the same equation applied to both variables. And, yes, @norich111, you still have to do that.
You do have to prove then that after reducing a_n, it is not only less than the original a_n but drops below b_n, hence necessitating the flip
the question six ratio is a cyclic function
I'm getting the strong feeling that someone should write a book about Question 6 (and the answer). Start with the history of the International Math Olympiad, then get into how contestants are chosen, who comes up with the questions. And (if possible) who came up with Question 6 - the whole story behind it, and what the organizers expected from the Olympians. THEN get into the solution - complete with the background on quadratic equations and Vieta's Formulas......
I'm getting a strong feeling, that I'm perfectly sure who should be this someone to write the book. Zvezda, I'll be the first one in the queue for preorders!
Why stop at a book? Someone should direct a psychological thriller about a group of mathematicians whose lives are all loosely intertwined due to them all being haunted by the evil of Question Six.
@@vigilantcosmicpenguin8721 lol
There are plenty of hard imo problems, if this should, then all of them should.
Over excited teenagers ... Mehhhh
Solve trigonometry identities..
The evidence proving that the sequence always converges to one zero term was spread out through the video and not explained super thoroughly, so to recap: Every time you perform a reduction, at least one of the numbers is guaranteed to decrease by an integer amount. Also, Zvezda proved using Vietta's theorem that because the new number found in the reduction is a root of a specific quadratic polynomial, the theorem shows that this new root must be non-negative. Therefore, if at each step the numbers must strictly decrease by an integer amount, and the numbers cannot be negative, there exists a step after a finite number of iterations at which one of the numbers is guaranteed to be zero. In a computer science setting we'd call this proof by entropy.
Huh?
@@codycast what's wrong?
Thank you, that was the part that I didn't quite get
Huh?
Thank you!
Zvezda is so expressive, passionate and enthusiastic. I'd love to watch a collaboration between her and Cliff Stoll on a numberphile video. I wonder how it would be.
Thank you Zvezda, thank you Brandy. ;)
Zvezda is such a star. ⭐
Very nice proof and explanation. If I had no clue I would start trying solutions with small numbers and try to see if I could find structure. I can imagine I could find a solution eventually but certainly not in 20 minutes. Looking how Zvezdelina explained it, I now can at least imagine how she could solve this so quickly. Vieta's formulas, induction, root exchange, symmetry, the importance of a factor being allowed to be zero, etc. are really part of her native language and she understand the full impact.
Fascinating video. I'm not sure if this solution to the problem or the anecdote at the end fascinates me more.
21:45 mind blown 🤯🤯 Zvezdelina explanation was so clear and easy to follow.
I've been watching your channel since 2011. This is one of your best videos.
Let's define:
k = (a^2 + b^2) / (ab + 1)
Since ab + 1 divides a^2 + b^2, we know that k is a positive integer. Our goal is to show that k is a perfect square.
Finding a Recursive Relationship:
Consider the expressions:
A = b
B = kb - a
If we substitute these into A^2 + B^2 and simplify, we get:
A^2 + B^2 = b^2 + (kb - a)^2
= b^2 + k^2b^2 - 2kab + a^2
= (k^2 + 1)b^2 - 2kab + a^2
= k(kb^2 - 2ab + a^2/k)
= k(AB + 1) [Using the value of k]
Descending a Ladder:
Notice an exciting property: A^2 + B^2 is again of the same form as our original expression (a^2 + b^2), with the added bonus that A^2 + B^2 = k(AB + 1). This gives us a way to create a chain of numbers related to the original a and b, where at each step we get values similar in structure, with the same value of k.
Base Case:
We can continue creating smaller pairs (A, B) at each step. To end this descent, we'll eventually hit a case where either a or b (Assume 'a' without loss of generality) becomes 0. If a = 0, then from the original equation:
b^2 = k(0 * b + 1) => k = b^2
In this scenario, k is obviously a perfect square.
The Contradiction:
Assume k is not a perfect square. Then, since its an integer it has some unique prime factorization. Using our recursive step with this non-square k, we can descend to smaller and smaller positive integer pairs (a, b). At each step, k remains the same.
However, this descent of a and b is bounded by them being positive integers. We cannot keep "splitting" the prime factors in k indefinitely with smaller integers! There must be a step where this descent cannot progress. This contradicts our assumption that k is not a perfect square.
Therefore, k must be the square of an integer.
Additional Notes:
There are multiple approaches to this proof. This one establishes a recursive descent.
This result has a beautiful geometric interpretation involving Pythagorean triples.
Such a great story and a brilliant solution!
You should do a collab of Zvezda and Terence!
It sounds kinda tough flying around the world as a youngster to do terrifying maths problems!
Did you ever watch the international superintendo tournaments? That was supposed to be fun!
i can not believe this!!!! what a legendary question solved only with basic algebra knowledge. that's why i love mathematics
Thank you Brady and Professor Stankova. The elegance of the proof is beautiful.
The best thing of all this is the encounter of Zvedva and Terence.
The second best thing is Zvedva saying "Australia" and, no other word ever, in an Australian accent.
on theme too, the power of induction :D
Brady is, as ever, *obsessed* with whether mathematicians are jealous when another mathematician gets a solution first or a better solution.
Once you have a pair that contains zero, it occurs to me that you can work backwards starting with ANY natural number as it's mate. And 'r' for the particular solution is the square of that number.
That was so incredibly elegant! It gave so much insight into the structure of the object in such a simple algorithm. I'm actually in awe. I'd love to see Zvezda's variation, too. Is that recorded anywhere?
Hearing 'number theory', my brain goes straight to modulus, divisibility, and primes, and I can't help but feel like the 'constantly lowering the one of the inputs' part of the proof feels a lot like the Euclidean Algorithm. I wonder if the two are related somehow.
I think so... I am trying to find relation with that only
From what ive seen it doesn't relate to the euclidean algorithm its just vieta jumping
Very interesting! Great explanation. And as always it's humbling to hear an excellent mathematician reminisce about the achievements of their youth.
Film from the left is someone is right handed, if they are a lefty, film from the right. That way we can see what they write, while writing.
Induction with quadratic formula! This proof is beautiful.
I could watch prof. Stankova videos for eternity, never stop churning them out
There's only one negative integer solution to the equation which is -5. The 8 non reducible sets of a and b are (-1,2) (-1,3) (2,-1) (3,-1) (1,-2) (1,-3) (-2,1) and (-3,1) and with these you can Vieta jump to larger absolute values. Like -5(3) - (-1) yields -14,3
👌presented with clarity. >= vs > matters a lot in this case (for proving the descent of the alternating roots) .
Both Zvezdelina and Emanouil managed to solve this problem that decorated mathematicians had trouble with. However, Zvezda's solution used a complicated method, which is kind of impressive in my opinion.
I think Bulgarian teem in preparation for IMO solved some similar problems and was familiar with this method.
Oh boy, I've waited since the question 6 video to see her taking about it
“… and the conclusion will immediately follow.” If you say so. Brady, I am glad you let us bask in the brilliant shadow of giants with your videos!!!
The story at the end was epic!
And she explained it so nicely, she made me feel I could derive the proof myself.
All hail induction
Her story with Tao is so fascinating!
That's absolutely wild. It's not at all how I would've approached the problem, but I guess that's why I didn't go to the math olympiad. I really enjoyed how clearly every piece fell together by the end.
I love the “if you say so” okay when checking her division
The pairs of integers that fit the equation are x^(2n-1) - (n-2)x^(2n-5) + T(n-4)x^(2n-9) - TT(n-6)x^(2n-13) + TTT(n-8)x^(2n-17) - TTTT(n-10)x^(2n-21) + ... where T(n) is the triangle number TT(n) is the triangle number of the triangle numbers and TTT(n) is the triangle number of the triangle numbers of the triangle numbers and so on. If you substitute n = n - 1 you get the other pair and if the power becomes negative you stop the formula. So if n = 11 you get a=(x^21 - 9x^17 + 28x^13 - 35x^9+15x^5- x) b= (x^19 - 8x^15 + 21x^11 - 20x^7 + 5x^3) cause T(11-4)=28 TT(11-6) = 1+3+6+10+15 =35 TTT(11-8) = 1+1+3+1+3+6=15 TTTT(11-10) =1 and T(10-4)=21 TT(10-6)=1+3+6+10=20 TTT(10-8) = 1+1+3=5. All the coefficients add to either (1,1) (1,0) (0,1) (0,-1) (-1,0) or (-1,-1) so that x = 1 will result in 1.
Zvezda's lecture is so clear and easy to follow.
I’ve never heard of the vieta’s formulas, these are so cool and useful, the proof is really cool as well, love the video!
This is one of the best videos youve put out. Such a difficult problem, but the proof was crystal clear and presented wonderfully.
Zvezdelina Stankova is legitimately one of the best Numberphile presenters, ever
Excuse me, a notation point:
Natural numbers (written with that N) are: 0, 1, 2, 3, 4, ...
Positive integers (written as Z^+) are: 1, 2, 3, 4, ...
one of the best videos, thank you both
It can also be proved that if (a^2+b^2)/(1+ab)=r, where r is a positive integer, then r=gcd(a,b)^2.
I can see how that might work using Vieta's product formula alongside the reduction procedure, thereby keeping track of the relation between the members of the sequences a_n and b_n.
I thought that proving r is a square was the POINT. I didn't see that point confirmed. Did I miss it in passing?
@@jeffkaylin892 It is mostly over my head but my understanding is that by continually reducing a or b eventually one of them is zero so you end up with r=a^2/1.
Amazing, what a brilliant mind! Thank you for the great video.
"Number theory is not my forte"
Solved a legendary difficult number theory question in 20mn
This is fascinating! Beautifully explained.
Thanks for watching
@@numberphile The initial part struck a cord with me. Being a programmer, (non-infinite) recursion always ends with a fixed point. This was like reversing it to find the algorithm. Extremely clever.
Whatever Zveta is explaining - I love listen to it. Understanding it is another matter.
About induction : I propose a little problem which is a "remix" of an old one. The original problem is the famous twelve coins problem, studied in Martin Gardner's chronicles (among others) : You have an old weighing machine (type Roberval) only able to give the answer heavier, lighter or equal. You are given twelve coins apparently identical but one of them is heavier or lighter than all the others which have the same weight.
You have to find the fake coin and tell if it's heavier or lighter in three weighings.
I modified the statement this way : You have to tell the six (3x2) sets of coins to compare *before* the first weighing.
Some sequels :
- what if you are allowed four weighings - or any number n for that matter?
- produce a generic - i.e. for any n - automatic algorithm to choose the sets and to give the result *at a glance*.
To solve this you NEED induction.
This is my creation. I can do whatever I want. I'm the boss.......
My new attitude when approaching difficult calculations.
Much better than the previous videos on this problem
Congratulations and many thanks for this small series about Induction.
My math professor actually got this question right too!
I feel like this would be very easily understood as a solution using equivalence classes, where (a1,b1) ~ (a2, b2) iff their ratios are the same. Then, noting that (a,b)~(b,a) and calling a>b WLOG, using this induction to show that all equivalence classes can be described as (a_n, 0). However, for a solution found in 20 minutes this is still insanely impressive!!
At the end you can see that 2 of the gold medalists were from Romania and actualy Nicusor Dan won 2 such medals with maximum points in 2 consecutive years ('87 and '88).
Nicusor Dan is now the mayor of Bucharest
I tried to solve question 6 a few years ago. It took me 2 days. I'm not even sure that my proof is valid.
Brilliant that was rigorously entertaining....
finally making a video on it? I remember a lot of us were requesting to actual explain the solution as the original video only talked about the event
Brilliant proof! After watching this, I feel like I can join the Math Olympic if I were 30 years younger.
I was hoping Simon would be in this one. Try getting him in a future video, Brady. He's hilarious.
Wow! Just yesterday I saw your first video on question 6 and now there's another one!
Zvezda you are a true zvezda! What a disaster for Bulgaria was the brain drain from 89 to now.
So the key was to remember Vieta's Formulae?
This is a much nicer solution than in the first Numberphile video on the topic
i don't get it, why we hit the wall at 0 and not another integer? (how to prove that the minimum pair is (a,0) and not (a,b) with 0
It's like the Euclidean's Algorithm for finding GCD
Yes. Vieta jumping.
Im confused wasnt the answer supposed to be a curved piece of wire ?
when the engineer goes to a math conference
Always happy to see Zvezda!
If you watch Brady's interview with Terrence Tao, he also mentions asking Zvezda as a kid. Wonderful how both still remember each other!
This process can be modeled by a cluster algebra. So while it's always possible to reduce the size of the solution the opposite is true too, it's always possible to make the solution larger. Hence the maximum number of steps is unbounded
It might be unbounded, but you can clearly give bounds to its growth depending on a and b.
The homework question has to be a logarithm, right? Something like log(max(a, b))?
Respect.
So much respect!
….. and love.
@23:25 this equation doesn't belong in the video, she wasn't saying those first two quantities are equal, just that one or the other is equal to r.
27:30 SUCH A CUTE STORY!
Love it. I did this problem on my channel too, but used a proof by contradiction.
5:49 "Not just natural numbers, non-negative integers." Zvezda, I admire you greatly, but those are fighting words.
Yep, it always helps to write ℕ₀ regardless of one's personal preference. 🙂
Zvezdelina, you are an amazingly lucky person! Of the tiny handful of pairs that produce a perfect square, you just happened to find the Wonka Bar with the golden ticket! 30 and 112, let me write those numbers down.
Is this induction though? I'd call it an invariant/variant method similar to proving a programming loop correct. The invariant is the ratio r and the variant is the smaller of the pair (a,b) which gets smaller on each iterative step.
Well, i'm not sure, but the terms might be slightly different in each language. Here there is an interative part, but the key property is that every decreasing sequence of natural integers is finite (actually we have to use an adequate mapping from N² to N). I personnaly would not call this induction, but i'm not shocked by the term.
I'm not a mathematician by any means. I decided that I had to watch Simon Pampena's "curve popping out the paper into 3D space" explanation (that was weird) and blackpenredpen's proof by contradiction (that was a bit more digestible) to have a chance to follow along with this one. And they helped, but the landing on this one really left me unconvinced.
So what Zvezda's saying at the end is that any pair of a and b that satisfies r being a perfect square can be reduced so that either a or b is zero, right? Simon also did that from the other way around. But how is that exhaustive though? Like, how does that convince you that no other pair exist outside of the ones you're working with, and that those pairs aren't gonna spit our r being a non-perfect square integer?
The idea is that we can always do the reduction process to any pair that produces an integer solution. So even if there are some pairs out there doesn't belong to our chain of solutions, it has to belong to other chains of solutions since we've proven that we can always produce a chain given a pair. And at the end of that chain, we can always find a 0 in it. Funny enough, by that fact alone, you can also immediately see that there can only exist 1 chain since there can only exist one end of the chain which is (sqrt(r),0). Multiple chains can never share an end so there's really only one path.
Wow! That story really is an epic adventure.
This was one of the most beautiful solutions that I ever saw in math...
27:56 Another big name appears on the list: Ngô Bào Châu from Vietnam got a perfect score (42)... years before moving to France and earning a Fields medal!
How can a cubic polynomial come up during the problem-solving? Can someone guess? All I can think of is a quadratic...
To summarise the proof (how it works) for those not actually looking for a proof but just wondering about the logic behind it:
If the ratio r is fixed, we can decrease either the values a or b, because we can convert the equation to a quadratic, and just take the lower root of the quadratic (with respect to the smaller number, either a or b) which returns the same ratio r.
Another concept to note is that the two roots of the quadratic, when summed, becomes the negative of the b term. (As in ax²+bx+c)
Since the b term of the quadratic is always negative, the lower root can never be negative.
But since the lower root can always be decreased, we will reach a point where either a or b becomes zero.
Let's assume a becomes zero,
b²/(1+0b)=b²
And vice versa
Thus it is always a square
How do we guarantee that the algorithm produces a zero eventually? I haven’t done the details but perhaps the sequence is nonnegative and decreasing will always produce 0?
Yeah, so long as you're non-negative and decreasing by at least some fixed finite amount each time (since you're working with integers here, you can't decrease by less than 1), you have to stop after a finite number of steps. If you can continue for any non-zero value, then the only possible final number is 0, so you must reach it eventually.
Since we are dealing with integers we know that our decreasing sequence decreases by at least 1 each step so if we started from n, it will take at most n steps to reach 0.
Solutions of the equation (a^2+b^2)/(1+ab)=r , have the property that if (a,b) is a solution then (-a,-b) is also a solution. It is also true that a*b must be greater or equal to 0 (I won't prove it here). So how can we go from the non-negative solutions to the non- positive ones using Vieta's formulas where we can change only 1 of the 2 numbers at a time? We need a number a where (a,b) a solution, a, b>=0 and (a,b') also solution, a, b'