Too hard for the IMO? Too easy?
ฝัง
- เผยแพร่เมื่อ 5 ธ.ค. 2020
- We look at a problem that was shortlisted for the 1988 International Mathematical Olympiad.
Please Subscribe: th-cam.com/users/michaelpennma...
Merch: teespring.com/stores/michael-...
Personal Website: www.michael-penn.net
Randolph College Math: www.randolphcollege.edu/mathem...
Randolph College Math and Science on Facebook: / randolph.science
Research Gate profile: www.researchgate.net/profile/...
Google Scholar profile: scholar.google.com/citations?...
If you are going to use an ad-blocker, considering using brave and tipping me BAT!
brave.com/sdp793
Buy textbooks here and help me out: amzn.to/31Bj9ye
Buy an amazon gift card and help me out: amzn.to/2PComAf
Books I like:
Sacred Mathematics: Japanese Temple Geometry: amzn.to/2ZIadH9
Electricity and Magnetism for Mathematicians: amzn.to/2H8ePzL
Abstract Algebra:
Judson(online): abstract.ups.edu/
Judson(print): amzn.to/2Xg92wD
Dummit and Foote: amzn.to/2zYOrok
Gallian: amzn.to/2zg4YEo
Artin: amzn.to/2LQ8l7C
Differential Forms:
Bachman: amzn.to/2z9wljH
Number Theory:
Crisman(online): math.gordon.edu/ntic/
Strayer: amzn.to/3bXwLah
Andrews: amzn.to/2zWlOZ0
Analysis:
Abbot: amzn.to/3cwYtuF
How to think about Analysis: amzn.to/2AIhwVm
Calculus:
OpenStax(online): openstax.org/subjects/math
OpenStax Vol 1: amzn.to/2zlreN8
OpenStax Vol 2: amzn.to/2TtwoxH
OpenStax Vol 3: amzn.to/3bPJ3Bn
My Filming Equipment:
Camera: amzn.to/3kx2JzE
Lense: amzn.to/2PFxPXA
Audio Recorder: amzn.to/2XLzkaZ
Microphones: amzn.to/3fJED0T
Lights: amzn.to/2XHxRT0
White Chalk: amzn.to/3ipu3Oh
Color Chalk: amzn.to/2XL6eIJ
![ตัวอย่างภาพยนตร์ Venom: The Last Dance [Official - Sub Thai]](http://i.ytimg.com/vi/DHPjvAwmnRE/mqdefault.jpg)
Nice problem, thank you, Michael.
Here is a solution using matrices. Let A be the matrix
(0 1 0)
(0 0 1)
(-1 0 3)
Then the characteristic polynomial of A is p(x)=x^3-3x^2+1.
This implies that if a,b,c are the three roots of p(x), then
a^n+b^n+c^n=trace(A^n) (an integer, for all n)
By Cayley-Hamilton, we have that
A^3-3A^2+I =0, where I is the 3x3 identity matrix. It is possible to see that
A^1988= u A^2+ v A+ w I, where u,v,w are integers. In fact,
A^1988 == 14 I+16 A+9 A^2 mod 17
If we let N=1988, then
a^N+b^N+c^N=trace(A^N)==trace(14 I+16 A+9 A^2 )==1 mod 17.
The rest is just like Michael's solution.
This is a very nice approach!!
Amazing, Hector! Two questions: how do you find a matrix that fits the polynomial (usually one goes the other way, calculating its charac polynomial from a matrix), And how do you calculate A^1988.
@@Risu0chan there is something called the companion matrix that does that. Check it out in Wikipedia.
To do the computation, I used Mathematica.
PolynomialMod[PolynomialRemainder[p[x],q[x],x],17]
Where
p[x_]:=x^1988;
q[x_]:=1-3 x^2+x^3;
@@videolome Ah, interesting and useful.Thank you :)
Sweet.
This problem reminds me why I'm a mathematically competent scientist and not a real mathematician.
lol
Why do you say that? And doesn't it make you feel bad?
Agreed. My engineering background did not show me how to solve this problem lol.
Wow, yes do check out his channel! Very cool! I've been binging! Thanks for the recommendation.
@@jbtechcon7434 Thanks! Glad you enjoyed! :-)
I love how problem-solvers say "easy to see" even if it is very hard to notice
if you mean the part where he talks about the largest root being between 2 and 3, it comes straight from calculus. The function is strictly increasing to the right of sqrt(2).
well yeah, it's really hard to notice, but after that it's easy to see!
this problem was kind of brutal (solution looks easy but hard to think of so many things at once) . polynomials , functions , number theory all in one packet
Pretty easy to see x^3 outgrows 3x^2 past 3 lol
@@jkid1134 Since we later find there's two other real roots, this is not really needed.
24:18 Loading 98.2%... So close! Have a lovely Sunday, Michael and you all!
If you divide 24:18 with 24:20 isn't that 99.86%. Unless of course you're implying something different which I am very curious to find out.
@@vaibhavnanchahal4173 Loading 98.4%... Please have a look at the number of Michael Penn’s subscribers.
Of course! 😅
Can someone explain what this is about? Just curious
I love seeing extremely difficult math problems get solved.
I haven't looked at the video yet, but this is similar to Binet's formula for Fibonacci numbers. Applying the idea for x³−3x²+1, and reducing mod 17 gives a sequence of period 16, so that u[1988] ≡ u[4] ≡ 69 ≡ 1. Then since 1988 is even, α^1988 is slightly less than u[1988], so that floor(α^1988) = u[1988] − 1, which is divisible by 17.
How Is this familiar?🤔
Another really great problem. Amazing content at the moment from you Michael!
The observation of the congruence between the sum of the roots and the roots in the finite field F_(17) was pure gold!
I am not being able to fully understand this (it is probably because I don't have any background in field theory). Would you mind please explaining it to me?
@@williammauriciogiraldomuri9855 I think that the idea is that a^n+b^n+c^n has an expression in terms of a+b+c, ab+bc+ac and abc, that doesn't depends on wether you're in R or F17, because your working with integers coefficients regardless, that naturally projetcs in F17. In turn these three expressions have the "same value" wether a b and c are the real roots or the F17 ones, because they are given by the coefficients of the polynomial. I'm not sure how I would go about writing it rigorously so this may be wrong, but I couldn't make sense of it otherwise.
Great stuff, discovered your channel recently, in love with it! I do give some tries to the problems but don't go that far... yet!
The justification of the congruence equality at 19:40 is unclear and I think actually requires a lot more proof. It certainly does not seem immediate from the facts currently established.
After some additional thought, I conclude that it really is not immediate. The proof the congruence equality is not terrible or particularly long, but it feels off having it skipped over considering the carefulness and amount of rigor shown in the rest of the video
I feel like just saying it would be allowed in the competition. But for teaching purposes I think it might indeed be better to justify that.
edit: by the way, the justification that I am using to convince myself is that 4, 5 and 11, mod 17, satisfy the symmetric sums identities satisfied by alpha, beta and gamma. since alpha^n + beta^n + gamma^n mod 17 can be represented as a function of those sums, then setting that equal to 4^n + 5^n + 11^n is justified.
Yeah, it isn't necessarily a complicated justification, but I wouldn't call it obvious.
Yeah, this congruence does the bulk of the work in this problem, so it definitely needs to be justified carefully, and it just... isn't. You'd lose some points on the IMO for not justifying that step
This is the part of the vid I have the most trouble with
I solved almost the same way but with a slight change at the end. The sum of n powers of roots is exactly the formula of the n'th term of the recursion sequence starting from a0=3,a1=3,a2=9 and defined by taking thrice the previous term minus the term three positions from the current. You can check manually that mod17 it has a period of 16 and that a4=1
Thanks for all the great (!) videos.
You have very good handwriting, which is an underrated quality for a mathematician. Decades ago, when I was in school, I used to do my math(s) homework in ink. Not because I never made a mistake, but always because I needed to see what I was doing.
I also pepper my speech with “OK” and “great”. You eschew cliche thinking.
Mathematician: 3/8
Engineer: 9.5 mm
Great as always
20:38 Question says 1988! and then they magically changed at the next board.
I solved it in a slightly different way, without factoring in F_17
Let a[n] = α^n+β^n+γ^n. Then from x^3=3x^2-x^0 it follows that a[n+3]=3a[n+2]-a[n]
Values a[0,1,2] are easy to calculate from the symmetric polynomials: 3,3,9.
Thus, we both proved that a[n] is integer for every n, and have easy formula to calculate next a[n]
Direct calculation shows that modulo 17, the sequence of a[n] is periodic with period 16: a[n]=(3,3,9,7,1,11,9,9,16,5,6,2,1,13,6)
Then a[1988]=a[4]=1
Now, if we can show that the period must be 16 (some extension of Fermat's theorem) that would be really cool.
@@d.o.584 I guess, that won't be so easy. It is related to the fact that matrix [[0,1,0],[0,0,1],[-1,0,3]], that encodes the recurrence relation for a[n], is diagonalizable in F_17, and proving this requires factorization of its characteristic polynomial x^3-3x^2+1
@@d.o.584 tbh, you can reduce all that 16 calculations to only 3 calculations.
by FLT, the maximum period less than 17 is 16. so the minimum period has to be a positive multiple of 16 other than 16 which is 2,4,8.
I have had a dabble on many problems on this channel with success time to time. However I quickly came into conclusion that this was way beyond my capability. I tried to use Vieta's formulas, but I lacked a proper idea to follow thru. I also tried some recurrence ideas, but that came to a halt very quickly also. A fascinating solution!
I like being able to “almost” follow along, and really appreciate every video. I love math and wish I had been more disciplined when younger.
For 5:48: x^3-3x^2+1=x^2(x-3)+1, so if x>3, then both terms are positive.
Yes, I saw that one too. (That was the easy part of this!)
i feel like i learned a lot from this one problem O.O
the fact that a^n+b^n (...+c^n etc) can be written as a polynomial g_n(x,y) on x=ab, y=a+b is pretty cool!
it's obv trivial for n=0 and n=1 (it's g_0 = 2, g_1(x, y) = y^2-2x)
You can prove this then by [strong] induction:
a^(n+1) + b^(n+1) = (g(ab, a+b) - b^n) . a + (g(ab, a+b)-a^n) . b
= g(ab, a+b) . (a+b) - (a . b^n + b . a^n)
= g_n(ab, a+b) . (a+b) - a.b. (b^(n-1) + a^(n-1))
so g_(n+1) (ab, a+b) = g_n(ab, a+b) . (a+b) - ab . g_(n-1) (ab, a+b)
which is a polynomial in only ab and a+b! :)
Of the 30 of so videos I've watched on your channels, this is by far the most difficult solution to conceptualize. I'm curious of whether any alternative solutions exist through Cardano Del-Ferro's equation, converting the solution into Polar, then using De'Moivre's Theorem to expand the 1988th power, then somehow showing the floor of the rational part must be divisable by 17? This would be a total shot in the dark, but considering my Number Theory is quite weak it'd be my only idea.
that was really cool
These problems are really interesting but they make me feel like a worthless subhuman. I feel like a mathematical insect compared to these IMO gold winners.
It's like watching Bolt running 100 m. in 9"58, while normal people usually take their cars to ride more than 10 meters... :)
Nein, bloß nicht wortless fühlen!
I feel that way sometimes, but remember the IMO competitors often have an immense amount of preparation time wise and also working through the problems from previous competitions. They know what type of problems to expect.
Congrats on 100k subs!
Before watching the video, my quick guess is: Estimate the roots roughly, in particular the others are small. Then consider a linear relation (i.e., Fibonacci-like)
I might be wrong but for large value of n beta^2n+gama^2n is tending to zero hence floor of alfa^2n is equal to alfa^2n
Another hint (Descartes's rule of signs) would show why the root between 2 and 3 is the greatest root: f(x) has two sign-changes, so it has zero or two positive zeroes; f(-x) has one sign-change, so f(x) has one negative zero. Clearly, f(0)=1 and f(1)=-1, so (by the IVT) there is a positive zero less than 1; then as you found, there is another zero between 2 and 3, which is the only other possible zero and so must be the greatest.
This particular cubic gives nice answers in the general formula for the case of three real roots. I calculated that alpha = 1 + 2 cos (pi/9). I tried some trig tricks with powers of that but it didn't help me solve the problem! (The other two roots are 1 + 2 cos(5 pi/9) and 1 + 2 cos(11 pi/9). )
starting with instead χ³-3χ+1=0. Using cardano's method. Obtaining -2cos(π/9) as one of the roots. Attaining others as well by division algorithm. Reciprocate all those roots
I used a variant of Hector Lemeli's great solution that can be done by hand without much computation:
*p(x) = x^3 - 3x^2 + 1 = (x - a) (x - b) (x - c)* and *s_n := a^n + b^n + c^n*
With *p(0) = 1* we know none of the three roots can be zero, so we calculate:
*n in Z: 0 = a^{n-2} * p(a) + b^{n-2} * p(b) + c^{n-2} * p(c) = s_{n+1} - 3s_n + s_{n-2}*
Reordering yields the recursive relation called "Newton's Identity". We get the initial conditions by comparing coefficients of *p(n)* , just as Michael Penn did at 13:16 :
*s_{n+1} = 3s_n - s_{n-2}, s_{-1} = 0, s_0 = 3, s_1 = 3*
We try to find a period within " *s_n mod 17* ", so we use the recursion above to calculate the first few terms. We stop as soon as we notice a repetition of three consecutive terms (we need three, because the recursion order is three):
*s_n mod 17: 0, 3, 3, 9, 7, 1, 11, 9, 9, 16, 5, 6, 2, 1, 14, 6, 0, 3, 3, ...*
The period length is *16* . With *1988 = 142 * 16 + 4* we have
*floor(a^{1988}) = s_{1988} - 1 = s_4 - 1 = 1 - 1 = 0 mod 17*
Well, I have question proffessor and that is this: we have a cubic equation, so we can transform it and use the cardono method and then proceed from there?? Can we do this proffessor??
When Michael said, "I think it's a pretty hard problem" I thought, how hard could it be? But then I watched the video
I have trouble with "combining the 2 approaches".
You say straight away that alpha^2n + beta^2n + gamma^2n is congruent to 4^2n + 5^2n + 11^2n mod 17
Could you justify that a lil bit better?
I think the fact about expressing sym. polynomials (SP) by elementary sym. polynomials (ESP) is useful here.
Expressions for "α^(2n) + β^(2n) + γ^(2n)" in R and F17 in terms of ESP's ("p,q,r" in the beginning of video) are same.
Values of ESP's are integers, "p,q,r" in R and in F17 are congruent mod 17 (they're even the same because they're just the coefficients of polynomial) => "α^(2n) + β^(2n) + γ^(2n)" in R and in F17 are congruent mod 17, even though "α,β,γ" are different in R and in F17.
This implies that α^(2n) + β^(2n) + γ^(2n) Ξ 4^(2n) + 5^(2n) + 11^(2n) (mod 17), where "α,β,γ" are real roots
13:47 How he conclude the values for alpha, beta and gama composts?
If I had the tool at 3:28 it would have help me back in time I was a student. Yet today it would be useful 😁
I thought IMO was for high schoolers. I didn’t learn about symmetric polynomials until I had Galois theory and certainly not in high school
No, the IMO is for some of the best students in the country (I believe the US only sends 7).
I think the problems are meant to be solvable with no more than a high school education, but that’s probably why this problem wasn’t put on the exam
@@JM-us3fr look at the #6 problems, things used in them are never taught in high school. I believe that now a days no problem in the IMO can be solved with purely high school knowledge
@@donaldbiden7927 it is theoretically possible to solve most of the problems using only high school math (calculus not included), but for some problems almost no human being can come up with the astounding ideas needed, if you're trying to not use at least some specialized knowledge.
@@donaldbiden7927 #6 of 2020 uses very elementary tools that are known by any high school students (mainly pythagorean theorem). But the problem was very difficult because it required a lot ingenuity to put everything together.
Hm, I proceeded slightly differently, in a way that avoids the "sheer luck" that your polynomial splits over F_{17} (which I hadn't noticed). Let r1, r2, r3 be the roots in ascending order. Then for i = 1, 2, 3, we have that the sequence (ri)^n satisfies the recurrence x_{n+3} = 3x_{n+2} - x_n, as does any linear combination of such sequences. We are interested in the sequence x_n = r1^n + r2^n + r3^n, computed mod 17. We have x_0 = 3, x_1 = 3, x_2 = 9 (the square power sum in terms of elementary symmetric polynomials being e1^2 - 2e_2). So the initial terms of the sequence are 3, 3, 9, with further terms determined by the recurrence, and we watch what happens mod 17. Actually I used 1, 1, 3 and then multiplied by 3 at the end; for that, the repeating block mod 17 is of length 16 and is 1, 1, 3, 8, 6, 15, 3, 3, 11, 13, 2, 12, 6, 16, 2, 0. Now 1988 mod 16 is 4, and the entries where n = 4 mod 16 yield 6 mod 17, which when multiplied by 3 results in 1 mod 17. Because r1^{1988} + r2^{1988} is small and positive (note |r1| < |r2| because r1 + r2 > 0), definitely in (0, 1), the floor of r3^1988 must be 0 mod 17.
Get ranges of roots to
I had to re-read carefully to see that it was f(x)=0, not f'(x)=0 (the comma from the line above appears right where the apostrophe in f'(x) would be).
You are big! From Argentina!
I know another (more algebra) problem with the same polynomial and it's biggest root. Show that ceil(alpha^n) is divisible by 3, for every natural number n.
My fav on ur channel sir
Very nice video but it is not easier to count that a^4 + b^4 + c^4 = 69 using vieta's formulas, without using polynomial congruence. saying a, b, c I mean zeros of that polynomial
In such cubic problems, all roots (real or complex) are computable. For example - IF { x^3 + 3mx = 2n } THEN { x = [ n + √(n^2 + m^3) ] ^ (1/3) + [ n - √(n^2 + m^3) ] ^ (1/3) }. Therefore, 1/x = 2 cos(120°/3 = 40°) since n = -1/2 and n^2 + m^3 = -3/4. So, α and γ are quadratic roots computable from β = sec(40°)/2. Simplify and the 3 roots are (α = 2.879385241571817, β = 0.6527036446661393, γ = -0.532088886237956). Note that the theorem is true for all 3 roots of the equation (and not just the largest root α ).
How can we factor x^3 - 3x^2 + 1 as (x-4)(x-5)(x-11) (mod 17) without having to try all 17 numbers?
As there can be only 3 factors, we can only check until 11 :)
In fact, once you find 4 and 5, we know the sum of roots is 3, so you can determine that the last root is 3-4-5=-6=11 mod 17
Guess and check is the best solution. Once you find two of them the third is immediate.
What does factorizing a polynomial under mod really mean? What is the relation between (4,5,11) and the real roots (alpha,beta,gamma)?
I don't think there's a strong relationship between the roots themselves but rather between the symmetric polynomials of those roots. For instance, look at alpha^2+beta^2+gamma^2. It turns out that you can rewrite this as (alpha+beta+gamma)^2 - 2(alpha*beta + alpha*gamma + beta*gamma) = (-p)^2 - 2q (where -p = alpha + beta + gamma and q = alpha*beta + alpha*gamma + beta*gamma, as seen in the video). Thus, alpha^2 + beta^2 + gamma^2 = (3)^2 - 2(0) = 9. Similarly, modulo 17, 4^2 + 5^2 + 11^2 = (4+5+11)^2 - 2(4*5+4*11+5*11) = 3^2 - 2*0 = 9. In general, any symmetric polynomial of f(alpha,beta,gamma) can be written as a polynomial of -p, q, and -r = alpha*beta*gamma. (This fact is known as the fundamental theorem of symmetric polynomials on Wikipedia.) But since modulo 17, -p, q, and -r have the same values as 4+5+11, 4*5+4*11+5*11, and 4*5*11, respectively, it follows that every symmetric polynomial of alpha, beta, and gamma is congruent modulo 17 to its 4-5-11 form. In particular, alpha^1988 + beta^1988 + gamma^1988 = 4^1988 + 5^1988 + 11^1988 mod 17.
@@CauchyIntegralFormula Thanks
If we see the two polynomials as functions, let's say f(x)=x^3-3x^2+1 and g(x)=(x-4)(x-5)(x-11), then in the domain (0,1,2,...,16) which contains all the possible residues if we divide a number with 17, we have f(x)=g(x) (mod17)
Wait, so if the coefficients of ANY cubic are all integers, then the sum of any nth-power of the three roots is also an integer? And will this work on polynomials of degree 4 or higher?
yes, any symmetric function of the roots of a polynomial can be written as a function of the coefficients of the polynomial with integer coefficients.
That's because the coefficients themselves are integer functions of the roots and the specific functions that give the coefficients of a polynomial are a basis of the space of all symmetric functions in that many variables
can be also done by finding the sequence mod 17 has a period of 16
Can someone please explain to me at 20:00 how he made the jump to saying that “alpha^{2n} + ... = 4^{2n} = ... (mod 17)”? been staring at this for 10 straight minutes i have no idea why that follows
@@angelmendez-rivera351 i think i understand. can you tell me if this explanation is correct?:
Let S(a,b,c)=a^{2n}+b^{2n}+c^{2n}”, which is a symmetric polynomials and can thus be expressed as a polynomial *in the* elementary symmetric polynomials.
Also, (x-alpha)(x-beta)(x-gamma) or (x-4)(x-5)(x-11) when expanded is a polynomial in x whose coefficients are *all of the elementary symmetric polynomials of degree
Glad you wrote that. I got that far too.
@@danmarino900 I stumbled upon the same, so very thankful for your question and Angel's answer. What helped me to grasp it a little bit better, when I realized that due to the polynomials being the same, thus:
alpha*beta*gamma == 4*5*11 mod 17 ;
alpha*beta + alpha*gamma + beta*gamma == 4*5 + 4*11 + 5*11 mod 17
alpha + beta + gamma == 4 + 5 + 11 mod 17
and thus alpha^2n + beta^2n + gamma^2n will be written in the respective equivalent terms mod 17 like 4^2n + 5^2n + 11^2n and as each for the terms is the same mod 17, so must their result.
I was thinking you could rewrite a^1998 as a linear combination of 1,a,a^2 using the fact that every power of 'a' can be written as a linear combination of these. Not sure if you get a desirable answer that way though.
Can anyone help me out with why symettric polynomial can be written in terms of apha + beta + gamma , alpha beta + beta gamma + aloha gamma , alpha beta gamma ? Thanks in advance
What about doing this: let s_n = a^n + b^n +c^n (im using a,b,c instead of alfa,beta,gamma for simplicity). Notice that s_n = (a+b+c)*s_(n-1) - (ab + bc + ca)*s_(n-2) + abc*s_(n-3) = 3*s_(n-1) - s_(n-3) and s_1 = -3, s_2 = 9, s_3 = -30. As we know, b^n + c^n for very big and even n becomes very small number, definitely smaller than 1. So that means that the value we are trying to find is just s_1998 - 1. We can calculate it by finding the general formula for s_n. You can use for instance Michael favourite technic - generating functions. I think that this will work here
you mean generating function for aₙ=3aₙ₋₁-aₙ₋₃ ?
I don't get it, why symmetrical polynomial of real roots is equal to that of roots in F17
AT 6:05 f'(x) = 3x^2 - 6x >0 for x>3
I suspect that IMO problems are not written under the assumption that high school students know anything about rings and generating symmetric polynomials. (Just trying to answer the question in the title of the video.)
IMO participants definitely know stuff about generating symmetric polynomials.... this actually is not that “hard” for the IMO imo(no pun intended)....
This might be subjective as I haven't been to IMO, but in Japan from what I've seen, most of the IMO students have a deep knowledge in university math for algebra, number theory etc. Some have just finished university math (first 4 years) completely. They do really do a lot of training.
@@boraolmez6622 nah it's definitely pretty hard even by IMO standards, probably could be a hard Problem 2/4 although not a 3/6 monster
@@l1mbo69 agreed, but I was trying to claim that it’s not “too hard” for the imo (i would probably say 2/5 as well)
Why pqr are integers imply alpha beta and gamma are also integers?
Great! I love IMO problems
Too hard for me
Can someone explain the equation at 20:00?
How You Can Get [ α^2 ] = α^2n + β^2n + y^2n - 1 ?
There is a famous problem about elementary symmetric polynomials:
x+y+z=1
x^2+y^2+z^2=2
x^3+y^3+z^3=3
Find x^4+y^4+z^4 which turns out to be 25/6; so not an integer. So why is that integer argument apparently only valid if the symmetric polynomials are taken as the coefficients from a cubic (or generally polynomials)?
In video case coefficients are all integer, in your case they aren't.
x^3 - 3x^2 +1 = 0
y^3 - 3y^2 + 1 = 0
z^3 - 3z^2 + 1 = 0, so
x^n + z ^ n + y ^ n = 3(x^n-1 + y^n-1 + z^n-1) - z^n-3 - x^n-3 - y ^n-3
@@krzysztofkujawa5506 Sorry, maybe I don't get it, but I don't see how what you say has anything to do with what I'm asking. In the case of the video the 3 equations are
x+y+z=3
xy+xz+yz=0
xyz=-1
So different defining equations for the three roots x,y,z. I see that in my case a linear combination with integer coefficients for the three elementary symmetric polynomials would lead to the coefficient of x^4+y^4+z^4 to be greater than 1, because (x+y+z)^4 gives one contribution, but e.g. also (x^2+y^2+z^2)^2 so apparently integers doesn't work, whereas in the other case there is only 1 elementary symmetric polynomial - namely (x+y+z)^n - which gives rise to the unique x^n+y^n+z^n, but any other combination, say (x+y+z)^{n-2}*(xy+xz+yz) will never give a term x^n+y^n+z^n, but how do I know the other coefficients will not be rational numbers.
So what does your example show?
@@digxx maybe I didn not understand your question, but it is about how we may know that x^n + y^n + z^n is integer?
@@krzysztofkujawa5506 Basically yes. But why is my case not an integer?
In your case it is not itneger because coeficients of polynomial which has roots x, y, z are not all integeres but in the video case the coeficients of polynomial which roots are x, y, z X^3 - 3X^2 + 1 are integers.
crazy !
That was a very entertaining video. However, you should have explained how you factored the cubic (mod 17); it's appearance was a bit "deus ex machina".
He explained, where it came from he brute forced it as there was only 17 values to check
Los vídeos, the vídeos, los haces improvisados? It would be cool.
9:01 ootch? Well there’s a new word. I might have said scootch
Love From Nepal 😊❤
Is your finger alright
We learn something new everyday. No reason to feel embarrassed by not knowing this. We use some of this in physics, but don't really care about this type of solution, so we hardly think about it.
Can somebody explain step started on 19:37 in more detail?
All symmetric polynomials are generated by the elementary symmetric polynomials e1, e2 and e3 (look up in wikipedia). We know e1(α, β,γ) = e1(4,5,11) mod 11, e2(α, β,γ) = e2(4,5,11) mod 11, and e3(α, β,γ) = e3(4,5,11) mod 11 because these are just the coefficients of the polynomial x^3 - 3x^2 + 1. Therefore F[e1,e2,e3](α, β,γ) = F[e1,e2,e3](4,5,11) mod 11 for any multinomial expression F.
That one was hard!!
Are shortlist problems the ones who didn’t make it into the exams?
Nicely done 👍🏻
Just ignore 20:35
absolutely beautiful :-)
Phew!
Lost me when he got to the powers of n.
I was understanding most of the video but the part that really confused me for a moment was the fact that 68 is divisible by 17!
Good
When he said I think this is a hard problem. Then I got heart attack
essa é boa
ClearAll["Global`*"];
sol = NSolve[x^3 - 3 x^2 + 1 == 0, x, WorkingPrecision -> 5000]
x = sol[[3]][[1]][[2]];
s = Floor[x^1988]
Mod[s, 17]
This gives 0 in Mathematica, so problem checks out, good job.
Bisection method.
*NOICE*
Another way to show alpha^n+beta^n+gamma^n is an integer is to define f(x)=alpha^x+beta^x+gamma^x.
We then have f(x)=3f(x-1)-f(x-3) (because alpha,beta,gamma, are solutions to x^3=3x^2-1) and that f(-1)=0, f(0)=3, f(1)=3
(f(-1)=(alpha*beta+beta*gamma+gamma*alpha)/(alpha*beta*gamma)=0).
We can then show f(x) is an integer, when x is an integer, using induction.
And to show that this integer is congruent to 4^x+5^x+11^x mod 17, we can define g(x)=4^x+5^x+11^x mod 17, and because 4,5 and 11 are solution to x^3=3x^2-1 mod 17, we must have g(x)=3g(x-1)-g(x-3). g(0)=3, g(1)=4+5+11=3 and g(-1)=4^-1+5^-1+11^-1=13+7+14=0, because 13,7,14 are the multiplicative inverses of 4,5,11 respectively (ie 4*13=1 mod 17, so 13=4^-1)
So f(x) must be congruent to g(x) mod 17, because they are defined by the same initial values and recurrence relationship mod 17.
Can you tell me how to prove that f(x) is an integer, using induction? Or give me a hint?
@@bangstar719f(0), f(1), and f(2) are easy to find and are all integers, then proceed by induction
I'm a simple man, I like "simple facts"
alpha^n + beta^n + gamma^n = integer is not clear to me.
It was a new result to me as well, so I had to go back and listen to what he said. As far as I understand it is because the roots satsify a set of symmetric equations all of which have integer value. Now any other symmetric equation can be built up using those existing equations and so must also be integers. I think that is what he said and it makes sense to me though it was not somethimg I knew before.
If you don't want to use fields, you can also show that fact with a recurrence relation. You can prove that that expression is a_n where a_k = 3 a_{k-1} - a_{k-3} and a_0 = 3, a_1 = 3, a_2 = 9. The recurrence came from the polynomial how we typically try to solve recurrence relations like that. The initial conditions came from evaluating a_k directly (using the facts we learned from Vieta). Hence a_k is always an integer.
latexbase.com/d/d2047e4d-e4a9-4778-adc5-2d5e29069295
@@angelmendez-rivera351 but how do you know that it would be an integer? For example it can also be: (a+b+c)/(abc) which is also symmetric but not integer
f(x) = x^2(x - 3) + 1, so if x > 3 all terms are positive; no need to be obscure about that.
18:59 "how would we figure out this fact?" Magic. We would need magic.
ok great, I must study
5 is not mod 17 root
ওয়াও! very nice
👌👌👍
There will be a day when someone dislikes this and he will say this problem is too hard. I however loved every single moment of this video.
All through that I was wanting to know what alpha is
The first thing I figured out was that alpha = 1 + 2*cos(pi/9). I verified it with a calculator, and was quite proud of myself! But I didn't know where to go from there and finally gave up today :-(
@@ericvonl How did you find alpha?
@@sriramgorur4810 Knowing a little bit about complex numbers helped. I substituted y=x-1 to get a new equation, y^3 -3y -1 =0, which is a depressed cubic. Then Cardano's formula can be used, giving y as the sum of the cube roots of two complex numbers. I recognized those numbers as points on the unit circle in the complex plane; specifically, the points at angles pi/3 and -pi/3. So, finding the cube roots simply meant dividing the angle by 3. When adding the roots, the real parts are equal and the nonreal parts cancel out, so y=2cos(pi/9). (And then I had to remember that y=x-1.)
(Also, because a cubic equation has 3 roots, I had to find the other two roots and verify that they were smaller, because the problem defines alpha as the largest)
>Just factor mod 17 by checking every integer mod 17 bro
WTF no wonder it wasn't included
I like you bro
F(1)= -3
ok but when am i ever gonna use this in real life
Saxndi!
진짜 Imo 스럽다
Show it by graph 😀😃😃😃👽👽😃😃😀😃
This equation can easily by solved without numerical methods
(x-1)^3=x^3-3x^2+3x-1
(x-1)^3-3(x-1)=x^3-3x^2+3x-1-3x+3
(x-1)^3-3(x-1)=x^3-3x^2+2
(x-1)^3-3(x-1)-1=-x^3-3x^2+1
x-1=ucos(theta)
(3u/u^3)=3/4
3/u^2=3/4
u=2
x-1=2cos(theta)
8cos^3(theta)-6cos(theta)-1=0
8cos^3(theta)-6cos(theta)=1
4cos^3(theta)-3cos(theta)=1/2
cos(3theta)=1/2
3theta=π/3
3theta=7π/3
3theta=13π/3
x_{1}=1+2cos(π/9)
x_{2}=1+2cos(7π/9)
x_{3}=1+2cos(13π/9)
And here I thought solving the cubic would help me:
x³-3x²+1 = 0
Let t = x - 1
(t+1)³ - 3(t+1)² + 1 = 0
t³+3t²+3t+1 - 3t²-6t-3 + 1 = 0
t³-3t-1 = 0
Let u+v = t
I. u³ + v³ = 1
II. 3uv = 3 -> uv = 1 -> v = 1/u
u⁶ - u³ + 1 = 0
u³ = 1/2 + √(1/4 - 1)
= 1/2 (1 + i√3)
= 1/2 (2 exp(i π/3))
= exp(i π/3)
Recall that ³√1 = {1; exp(2iπ/3); exp(-2iπ/3)}
With that in mind:
u₁ = exp(iπ/9)
u₂ = exp(7iπ/9)
u₃ = exp(-5iπ/9)
v₁ = exp(-iπ/9)
v₂ = exp(-7iπ/9)
v₃ = exp(5iπ/9)
Unfortunately, we must add them up. So Cartesian form would be great right about now.
u₁ = cos π/9 + i sin π/9
u₂ = cos 7π/9 + i sin 7π/9
u₃ = cos 5π/9 - i sin 5π/9
v₁ = cos π/9 - i sin π/9
v₂ = cos 7π/9 - i sin 7π/9
v₃ = cos 5π/9 + i sin 5π/9
t₁ = u₁ + v₁ = 2 cos π/9
t₂ = 2 cos 7π/9
t₃ = 2 cos 5π/9
Noticing that the cosine is a falling function in [0;π], the smallest argument yields the largest result. So t₁ must be the greatest of these.
α = 2 cos π/9 + 1
Except that doesn't tell me anything about [α¹⁹⁸⁸].
at least you conveyed it so others could learn