Too hard for the IMO? Too easy?

Рет қаралды 96,852

3 жыл бұрын

We look at a problem that was shortlisted for the 1988 International Mathematical Olympiad.
Please Subscribe: kzfaq.info...
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

Пікірлер: 288

@jerrysstories711 3 жыл бұрын

This problem reminds me why I'm a mathematically competent scientist and not a real mathematician.

@prithujsarkar2010 3 жыл бұрын

lol

@leif1075 3 жыл бұрын

Why do you say that? And doesn't it make you feel bad?

@kidzbop38isstraightfire92 3 жыл бұрын

Agreed. My engineering background did not show me how to solve this problem lol.

@jbtechcon7434 3 жыл бұрын

Wow, yes do check out his channel! Very cool! I've been binging! Thanks for the recommendation.

@jerrysstories711 3 жыл бұрын

@@jbtechcon7434 Thanks! Glad you enjoyed! :-)

@videolome 3 жыл бұрын

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.

@MichaelPennMath 3 жыл бұрын

This is a very nice approach!!

@Risu0chan 3 жыл бұрын

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.

@videolome 3 жыл бұрын

@@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;

@Risu0chan 3 жыл бұрын

@@videolome Ah, interesting and useful.Thank you :)

@toomanyhobbies2011 3 жыл бұрын

Sweet.

@debayuchakraborti1963 3 жыл бұрын

I love how problem-solvers say "easy to see" even if it is very hard to notice

@numbers93 3 жыл бұрын

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).

@NickiRusin 3 жыл бұрын

well yeah, it's really hard to notice, but after that it's easy to see!

@prithujsarkar2010 3 жыл бұрын

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

@jkid1134 3 жыл бұрын

Pretty easy to see x^3 outgrows 3x^2 past 3 lol

@kristianwichmann9996 3 жыл бұрын

@@jkid1134 Since we later find there's two other real roots, this is not really needed.

@christopherrice4360 3 жыл бұрын

I love seeing extremely difficult math problems get solved.

@tomatrix7525 3 жыл бұрын

Another really great problem. Amazing content at the moment from you Michael!

@conovan5081 3 жыл бұрын

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!

@goodplacetostop2973 3 жыл бұрын

24:18 Loading 98.2%... So close! Have a lovely Sunday, Michael and you all!

@vaibhavnanchahal4173 3 жыл бұрын

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.

@goodplacetostop2973 3 жыл бұрын

@@vaibhavnanchahal4173 Loading 98.4%... Please have a look at the number of Michael Penn’s subscribers.

@vaibhavnanchahal4173 3 жыл бұрын

Of course! 😅

@Aramil4 2 ай бұрын

Can someone explain what this is about? Just curious

@charlesbrowne9590 3 жыл бұрын

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.

@michael169chapman 3 жыл бұрын

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

@Stelios2711 3 жыл бұрын

The observation of the congruence between the sum of the roots and the roots in the finite field F_(17) was pure gold!

@williammauriciogiraldomuri9855 3 жыл бұрын

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?

@An-ht8so 3 жыл бұрын

@@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.

@numbers93 3 жыл бұрын

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.

@numbers93 3 жыл бұрын

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

@ireallydontknow3299 3 жыл бұрын

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.

@avz1865 3 жыл бұрын

Yeah, it isn't necessarily a complicated justification, but I wouldn't call it obvious.

@CauchyIntegralFormula 3 жыл бұрын

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

@speedsterh 3 жыл бұрын

This is the part of the vid I have the most trouble with

@vinc17fr 3 жыл бұрын

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.

@b0redguy329 Жыл бұрын

How Is this familiar?🤔

@andy_in_colorado7060 3 жыл бұрын

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.

@monikaherath7505 3 жыл бұрын

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.

@raffaelevalente7811 3 жыл бұрын

It's like watching Bolt running 100 m. in 9"58, while normal people usually take their cars to ride more than 10 meters... :)

@andreasraab5294 3 жыл бұрын

Nein, bloß nicht wortless fühlen!

@MyOneFiftiethOfADollar 2 жыл бұрын

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.

@pikkutonttu2697 3 жыл бұрын

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!

@s4623 3 жыл бұрын

20:38 Question says 1988! and then they magically changed at the next board.

@danrain12345 3 жыл бұрын

Great as always

@wolo0048 3 жыл бұрын

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.

@nathanisbored 3 жыл бұрын

i feel like i learned a lot from this one problem O.O

@limerent 3 жыл бұрын

that was really cool

@JB-ym4up 3 жыл бұрын

Mathematician: 3/8 Engineer: 9.5 mm

@anonymous-in5fp 3 жыл бұрын

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

@kubatrcka5570 6 ай бұрын

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.

@JamesLewis2 3 жыл бұрын

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.

@HagenvonEitzen 3 жыл бұрын

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)

@Chalisque 3 жыл бұрын

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).

@adandap 3 жыл бұрын

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). )

@spiderjerusalem4009 7 ай бұрын

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

@moregirl4585 3 жыл бұрын

Get ranges of roots to

@laszloliptak611 3 жыл бұрын

For 5:48: x^3-3x^2+1=x^2(x-3)+1, so if x>3, then both terms are positive.

@larsdahl5528 3 жыл бұрын

Yes, I saw that one too. (That was the easy part of this!)

@niuhaihui 10 ай бұрын

can be also done by finding the sequence mod 17 has a period of 16

@sebastiengross7849 3 жыл бұрын

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 😁

@l1mbo69 3 жыл бұрын

When Michael said, "I think it's a pretty hard problem" I thought, how hard could it be? But then I watched the video

@Michael-es4fg 3 жыл бұрын

Congrats on 100k subs!

@toddtrimble2555 2 жыл бұрын

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.

@vishalmishra3046 3 жыл бұрын

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 α ).

@jasongros6688 3 жыл бұрын

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.

@krzysztofkujawa5506 3 жыл бұрын

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

@l.lawliet164 3 жыл бұрын

13:47 How he conclude the values for alpha, beta and gama composts?

@asklar 3 жыл бұрын

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! :)

@emilianomaccaroni2424 3 жыл бұрын

You are big! From Argentina!

@rbnn 3 жыл бұрын

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

@KingstonCzajkowski 3 жыл бұрын

No, the IMO is for some of the best students in the country (I believe the US only sends 7).

@JM-us3fr 3 жыл бұрын

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

@donaldbiden7927 3 жыл бұрын

@@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

@zafarb4219 3 жыл бұрын

@@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.

@taopaille-paille4992 3 жыл бұрын

@@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.

@wannabeactuary01 2 жыл бұрын

AT 6:05 f'(x) = 3x^2 - 6x >0 for x>3

@carstenmeyer7786 2 жыл бұрын

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*

@ronritekinamatigai 3 жыл бұрын

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

@d.o.584 3 жыл бұрын

Now, if we can show that the period must be 16 (some extension of Fermat's theorem) that would be really cool.

@ronritekinamatigai 3 жыл бұрын

@@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

@primenumberbuster404 2 жыл бұрын

@@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.

@vladthemagnificent9052 3 жыл бұрын

I don't get it, why symmetrical polynomial of real roots is equal to that of roots in F17

@debjitkunduscience11a93 Жыл бұрын

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

@yashvardhan6521 3 жыл бұрын

My fav on ur channel sir

@knowledgekong4970 3 жыл бұрын

Why pqr are integers imply alpha beta and gamma are also integers?

@hshsshsjsjns8074 2 жыл бұрын

How You Can Get [ α^2 ] = α^2n + β^2n + y^2n - 1 ?

@jamirimaj6880 3 жыл бұрын

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?

@OOobstkuchenOO 3 жыл бұрын

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

@wojteksocha2002 3 жыл бұрын

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

@spiderjerusalem4009 7 ай бұрын

you mean generating function for aₙ=3aₙ₋₁-aₙ₋₃ ?

@mohamedfarouk9654 3 жыл бұрын

What does factorizing a polynomial under mod really mean? What is the relation between (4,5,11) and the real roots (alpha,beta,gamma)?

@CauchyIntegralFormula 3 жыл бұрын

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.

@OuroborosVengeance 3 жыл бұрын

@@CauchyIntegralFormula Thanks

@kostaspapadopoulos1480 3 жыл бұрын

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)

@maydavidr 3 жыл бұрын

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".

@charlesbarrow803 Жыл бұрын

He explained, where it came from he brute forced it as there was only 17 values to check

@jacemandt 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.)

@boraolmez6622 3 жыл бұрын

IMO participants definitely know stuff about generating symmetric polynomials.... this actually is not that “hard” for the IMO imo(no pun intended)....

@zafarb4219 3 жыл бұрын

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.

@l1mbo69 3 жыл бұрын

@@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

@boraolmez6622 3 жыл бұрын

@@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)

@GreenMeansGOF 3 жыл бұрын

Can someone explain the equation at 20:00?

@erinc.8633 3 жыл бұрын

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?

@GiornoYoshikage 2 жыл бұрын

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

@warmpianist 3 жыл бұрын

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?

@alexgan3219 3 жыл бұрын

As there can be only 3 factors, we can only check until 11 :)

@CauchyIntegralFormula 3 жыл бұрын

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

@sirgog 3 жыл бұрын

Guess and check is the best solution. Once you find two of them the third is immediate.

@danmarino900 3 жыл бұрын

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

@danmarino900 3 жыл бұрын

@@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

@mcwulf25 3 жыл бұрын

Glad you wrote that. I got that far too.

@petersievert6830 3 жыл бұрын

@@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.

@oliver_ai 3 жыл бұрын

Great! I love IMO problems

@andreasraab5294 3 жыл бұрын

Too hard for me

@cristofer2794 2 жыл бұрын

Los vídeos, the vídeos, los haces improvisados? It would be cool.

@JM-us3fr 3 жыл бұрын

9:01 ootch? Well there’s a new word. I might have said scootch

@digxx 3 жыл бұрын

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)?

@krzysztofkujawa5506 3 жыл бұрын

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

@digxx 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?

@krzysztofkujawa5506 3 жыл бұрын

@@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?

@digxx 3 жыл бұрын

@@krzysztofkujawa5506 Basically yes. But why is my case not an integer?

@krzysztofkujawa5506 3 жыл бұрын

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.

@eduardokuri1983 2 жыл бұрын

Are shortlist problems the ones who didn’t make it into the exams?

@pooydragon5398 2 жыл бұрын

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!

@markregev1651 3 жыл бұрын

Is your finger alright

@toomanyhobbies2011 3 жыл бұрын

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.

@fredfrancium 3 жыл бұрын

When he said I think this is a hard problem. Then I got heart attack

@user-sk4kg4hr3k 3 жыл бұрын

Can somebody explain step started on 19:37 in more detail?

@erikr007 3 жыл бұрын

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.

@jchaskar 3 жыл бұрын

Nicely done 👍🏻 Just ignore 20:35

@sea34101 3 жыл бұрын

That one was hard!!

@mcwulf25 3 жыл бұрын

Phew! Lost me when he got to the powers of n.

@aupen4402 6 ай бұрын

5 is not mod 17 root

@amirb715 3 жыл бұрын

absolutely beautiful :-)

@prabhatsharma5751 3 жыл бұрын

Love From Nepal 😊❤

@pmcate2 3 жыл бұрын

alpha^n + beta^n + gamma^n = integer is not clear to me.

@tomasstride9590 3 жыл бұрын

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.

@erickross5868 3 жыл бұрын

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.

@asklar 3 жыл бұрын

latexbase.com/d/d2047e4d-e4a9-4778-adc5-2d5e29069295

@bangstar719 2 жыл бұрын

@@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

@bharatpakkha7787 2 жыл бұрын

Bisection method.

@Qoow8e1deDgikQ9m3ZG 3 жыл бұрын

crazy !

@johnloony68 3 жыл бұрын

All through that I was wanting to know what alpha is

@ericvonl 3 жыл бұрын

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 :-(

@sriramgorur4810 3 жыл бұрын

@@ericvonl How did you find alpha?

@ericvonl 3 жыл бұрын

@@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)

@peterhiggins5131 3 жыл бұрын

f(x) = x^2(x - 3) + 1, so if x > 3 all terms are positive; no need to be obscure about that.

@psioniC_MS 3 жыл бұрын

I'm a simple man, I like "simple facts"

@henry8777 3 жыл бұрын

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.

@bangstar719 2 жыл бұрын

Can you tell me how to prove that f(x) is an integer, using induction? Or give me a hint?

@spiderjerusalem4009 7 ай бұрын

@@bangstar719f(0), f(1), and f(2) are easy to find and are all integers, then proceed by induction

@thesecretkey9845 2 жыл бұрын

>Just factor mod 17 by checking every integer mod 17 bro WTF no wonder it wasn't included

@verystablegenius4720 2 жыл бұрын

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.

@djvalentedochp 3 жыл бұрын

ok great, I must study

@user-A168 3 жыл бұрын

Good

@joshuamason2227 3 жыл бұрын

ok but when am i ever gonna use this in real life

@CTJ2619 9 ай бұрын

F(1)= -3

@dOncRiMe616 3 жыл бұрын

In like ~10 minutes of the video there was 4 times a 19 second advertisement. Thats completely bullshit.

@asklar 3 жыл бұрын

18:59 "how would we figure out this fact?" Magic. We would need magic.

@guibaroleo 3 жыл бұрын

essa é boa

@user-kp1ci5jj8q 6 ай бұрын

I like you bro

@kmlhll2656 11 ай бұрын

It's a very hard problem, really I can't solve it.

@ameerunbegum7525 3 жыл бұрын

*NOICE*

@andreasraab5294 3 жыл бұрын

Saxndi!

@anilsharma-ev2my 3 жыл бұрын

Show it by graph 😀😃😃😃👽👽😃😃😀😃

@JXS63J 3 жыл бұрын

The moment at 18:30 is just pulled out of the air. Then you quote some other stuff that's not germaine. Then you say "Great". Not really MATHEMATICS.

@fmakofmako 3 жыл бұрын

I'm guessing that knowing cardano's formula makes this problem too easy.

@igml1145 3 жыл бұрын

Not at all... estimating a nasty irrational number raised to the power of 1998 sounds painful

@fmakofmako 3 жыл бұрын

@@igml1145 The largest root is of the form 1+z+w where w is the conjugate of z. The multinomial expansion of this has a bunch of powers of z that I'm not sure what to do with. It does seem a bit ugly, but I haven't worked it out myself. If anyone wants to try z is the cube root of 1/2(1+rad3 i).

@pmcate2 3 жыл бұрын

Just so I can feel better about myself, are the competitors in the IMO's told what formula they might need?

@exarchoustathees7623 3 жыл бұрын

No, obviously. They test critical thinking, obviously they wont tell you what to use

@debayuchakraborti1963 3 жыл бұрын

Yeah Mann...that comes with some hardcore practice

@vindex7 3 жыл бұрын

Of course they're not. But why could it possibly make you feel better or worse about yourself?

@pmcate2 3 жыл бұрын

@@exarchoustathees7623I shouldn't have said formula. Yes, I don't think they would be given specific formula. What I should have said is are they even told what subject the questions will cover? Aren't alot of the competitors on teams? So the coaches must have some sort of practice/strategy regiment. Like telling them what formulas are most likely to show up. Or is it just brute force through so many problems so that hopefully the ones on the exam will be like ones you have seen in the past?

@pmcate2 3 жыл бұрын

@@vindex7 I was half joking. Because if they were given some type of help it would mean they are not as genius at it seems and it makes one feel better about their own mental capabilities lol.