writing this as the sum of a few cubes.

We look at a problem from the IMO shotlist.
Suggest a problem: forms.gle/ea7P...
Please Subscribe: www.youtube.co...
Merch: teespring.com/...
Personal Website: www.michael-pen...
Randolph College Math: www.randolphcol...
Randolph College Math and Science on Facebook: / randolph.science
Research Gate profile: www.researchga...
Google Scholar profile: scholar.google...
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...
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/s...
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

[@theunknown4834]

Thumbnail: shorlist Description: shotlist Video: shortlist At *list* one of them is correct (like my answers)

[@goodplacetostop2973]

No misteak here, just happy little accidents

[@advaykumar9726]

@@goodplacetostop2973 Black pen red pen

[@trogdor20X6]

He’s a math professor not an English one.

[@Debg91]

A very insightful exercise. It's not only about number theory, but also about problem solving and the logic of this kind of contests to tackle the problems more efficiently

[@darreljones8645]

It has been proven that, for all integers n, n is the sum of not more than nine cubes. A proof similar to the one seen in the video showing that four is necessary for this value of n shows that infinitely many numbers require four cubes.

[@iang0th]

Has an example of a number requiring nine cubes been found?

[@renerpho]

@@iang0th Yes. 23 and 239 are the only such numbers. See www.ams.org/journals/bull/1939-45-08/S0002-9904-1939-07041-9/S0002-9904-1939-07041-9.pdf for the first proof (Dickson, 1939).

[@renerpho]

Note that 23=2³+2³+1³+1³+1³+1³+1³+1³+1³. All of those are needed, since there is no integer between 1 and 2, and 2³+2³+2³=24 is too big. Note also that 2³+2³+2³+(-1)³=23, so it is strictly necessarily to ask for NON-NEGATIVE cubes (something omitted in Darrel Jones' comment above).

[@Bodyknock]

3:20 Writing out cubes mod 9 is slightly simpler if, instead of looking at 0 through 8, you consider that 5,6,7 and 8 are -4, -3, -2 and -1 respectively so their cubes are just negative the cubes of 4,3,2 and 1.

[@jimschneider799]

I noticed that, too. I've removed my original comment as redundant.

[@robertgerbicz]

Even an easier method, from Euler-Fermat if gcd(x,3)=1 then x^6==1 mod 9 hence 9|x^6-1=(x^3-1)*(x^3+1) so x^3==+-1 mod 9.

[@stevenmellemans7215]

Ok, this was impressive.

[@leif1075]

Why the fuck would anyone think of mod at all..how is it impressive..just random really to me..

[@stewartzayat7526]

@@leif1075 Taking a modulo is a very common technique in these types of problems. The part I found random is, how do you know that mod 9 would yield something useful. I guess it's just a lot of practice and good intuition.

[@leif1075]

@@stewartzayat7526 but i don't think mod is common for everyone.well actuallyI know it'snit...why not factorize 2002..cant you solve like that? Breaking it into 2 times 7 times 11 times 13 and see what works??

[@anthonypham7563]

@everyone squares -> take modulo 8 cubes -> take modulo 9 fourth powers -> take modulo 16 Yes, this is from experience.

[@juyifan7933]

@@leif1075 These IMO problems are "real" problems in the sense that they require a lot of exploration, you dont come up with a method just by looking, you have to try out several things before finding the right approach. Thats the nature of contest math, is not about knowing super technical stuff, it is about exploring possibilities and being imaginative. If you look at research math this feeling of "htf would anyone think of this" is quite common. The point is that, in the paper you see, all those failed attempts are cleaned up and you look only at the final product. The process of arriving at that involved a lot of trial and error attempting the problem from different angles and making small ajustments.

[@samhui7478]

Actually the key is to find a number such that phi(n) = 6, then any number a**6 = 1, and a**3 = 1 or -1 mod n. Possible n = 7 or 9. But 2002**2002 = 0 mod 7 and 2002**2002 = 4 mod 9. So smallest solution is 4 = 1+1+1+1.

[@cameront4729]

I'm not very well-versed when it comes to mod and whatnot but your explanations make it super easy to understand!

[@jokubaszitkevicius8243]

That moment when you realise that 2020^2020 would have same remainder mod9

[@xyzx1234]

Impressive, as usual. I really enjoy your videos. I know you like to send your videos with "and this is a good place to stop", but in many of your videos I would actually love to see a bit of discussion of the problem after that point. For example in this video: (1) why did you choose to work mod 9? What would have happened if you'd chosen to work mod some other number? What would have gone wrong? What is so special about 9 in this context? (2) Is the repetition of 0, 1, -1 in the cubes mod 9 a coincidence? Could be a homework question. (3) What would have happened if the question used 2001 or 2003 instead of 2002? Would the same technique work, or is there something special about the number 2002? (4) What would have happened if the question asked for squares or fourth powers instead of cubes? To what extent does the argument hinge on being asked for sums of cubes?

[@z01t4n]

If the question asked for 2001^2001, the number would have been a cube (since the exponent, 2001 is obviously divisible by 3, since that's the sum of its digits), which immediately yields the simple solution 2001^2001 = (2001^667)^3 => m=1 (trivial)

[@SlidellRobotics]

5:58: Even quicker: 4⁴ = 4³ 4¹ ≡ 1*4 = 4(mod 9), as we already have 4³ = 1(mod 9) on the board.

[@psymar]

yes -- and even can skip the figuring out anything mod 6, because 4^3 is 1 mod 9, we immediately have that 4^2001 = (4^3)^667 is also 1 mod 9, so 4^2002 is 4 times that

[@goodplacetostop2973]

9:38 Happy July 4th to the people at The Overlook Hotel 😉

[@goodplacetostop2973]

@Parthsarthi Singh I’m not Michael bro 😂 Use the form in the video description to submit the problem

[@noahtaul]

@Parthsarthi Singh hello sir, it’s easy… if the equality is div by 2, then u can let a=2m+n and b=n, and c=r-s and d=2s, then u can divide by 2 and get r^2+5s^2=2m^2+2mn+3n^2… Then we can repeat until it’s not div by 2… Then if the eq is div by 5, we can let a=5s and b=r, and (since 2c^2+2cd+3d^2=2(c-2d)^2 mod 5) let c=2n-m and d=n+2m, then u can divide by 5 and get r^2+5s^2=2m^2+2mn+3n^2… Then we can repeat until it’s not div by 5… But then u can show that the LHS is only 1 or 9 mod 20, while the RHS is only 3 or 7 mod 20… so the only possibility is a=b=c=d=0… correct…?

[@noahtaul]

@Parthsarthi Singh ok u knew the answer but u want Michael to answer? I understand

[@hameedamathtuber]

That was another interesting problem. Thank you

[@xCorvus7x]

With 0, -1, and 1 we can also get 6, 7, and 8, if m is smaller than 4.

[@davidgould9431]

6:00 (ish) Wouldn't it be even quicker to consider 4⁴ = 4³∙4 ≡ 1∙4 (mod 9) ≡ 4 (mod 9)?

[@ramaprasadghosh717]

2002 = 2*7*11*13 = a*b*c*d,say So the given problem is reduced to partitioning (abcd)^(abcd) into smallest number of cubes

[@GeekProdigyGuy]

without knowing the trick for reducing the exponent to phi, it's still not too bad! since we know 4^3~1 mod 9, so finding 2002=3*667+1 gets you 2002^2002~4^2002=4^(3*667+1)~4

[@Sharpgamingvideos]

This problem definitely required some Olympic level leaps. Super cool though!

[@SilviuBurceaDev]

My lucky guess: 2002^2002 = 2002 * 2002 ^ 2001 = 2002 * (2002 ^ 667) ^ 3 so if x1, x2, ... xn are all equal to 2002^667, then we have 2002 terms :) Looking at the video, I guess I only missed that 2002 can be split into 4 cubes. Nice problem anyway.

[@psymar]

An easier way to calculate 2002^2002 mod 9: it's 4^2002 mod 9, but that's 4*4^2001 mod 9, or 4*(4^3)^667 mod 9, but as already established, 4^3 is 1 mod 9, so we have 4*1^667 = 4 mod 9.

[@kajdronm.8887]

Easy to understand solution, but how does one get there?

[@GeorgeFoot]

Can it be done with distinct cubes? How many of them are needed?

[@CRGreathouse]

Almost surely. Deshouillers, Hennecart, & Landreau conjecture that every number greater than 7373170279850 can be written as the sum of four distinct cubes (the amusing title of their paper is 7373170279850).

[@renerpho]

@@CRGreathouse Are you sure they conjectured distinct cubes? There is no mention of this in their paper, compare citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.2850&rep=rep1&type=pdf

[@renerpho]

They also clearly don't make the distinction in the introduction, giving the example of 23 that requires 9 cubes (one of only two numbers that does, as shown in 1939). The representation is 23=2³+2³+1³+1³+1³+1³+1³+1³+1³. Note also they ask about non-negative cubes specifically, as 23=2³+2³+2³+(-1)³, which is more strict than what is asked in the video.

[@CRGreathouse]

@@renerpho No, sorry, you're right. But you can still get the finiteness result (if not the explicit bound) from the general conjectures on the growth of the number of representations as the sum of four cubes.

[@renerpho]

@@CRGreathouse It is almost certainly possible to do it with distinct cubes, for all numbers above some point. Notice that the sum of all cubes up to a number n grows as a fourth power, while the number of subsets of a set with n elements is 2^n. 2^n grows much faster than n^4 even for small n, and n=2002^2002 is a very large number. That's not a proof, of course, and putting a bound on how many distinct primes you need is a different question. My guess is that it can probably be done with four.

[@Maxmuetze]

What a great problem! A little off the beaten track because cubes so rarely feature in contest maths.

[@viktoryehorov4314]

I suppose if you had other equation with x^x = 5 mod 9, you would claim m >= 5, but it’s possible to use 4 cubes (= -1 mod 9) with the sum of them = 5 mod 9 However, that doesn’t matter for the original problem 2002^2002 :)

[@sc0utop547]

impressive question

[@goodplacetostop2973]

HOMEWORK : A certain high school has exactly 1000 lockers, numbered from 1 to 1000, all initially closed. Mark first opens every locker whose number has exactly 3 factors, starting with locker 4. Matt then opens every locker whose number is a power of 2, starting with locker 1. If Matt encounters a locker that Mark has already opened, he leaves it open. Compute the number of lockers that will be open when both Mark and Matt finish. SOURCE : Rice Math Tournament 2015

[@arundhatimukherjee]

20

[@TreeCube]

20?

[@arundhatimukherjee]

None of the powers of 2 except 4 has 3 factors, so only locker no 4 is the only common case between mark and matt. Numbers with 3 factors are perfect squares of a prime number.🙂

[@36sufchan]

20 There are 10 powers of 2 less than a 1000 (including 1), so that's easy to check Next, if a number has exactly 3 factors, it must pe the square of a prime. The largest prime whose square is less than 1000 is 31 (32²=1024) and there are 11 such primes. Out of these, 2² has already been counted. So 20.

[@goodplacetostop2973]

SOLUTION *20* Numbers with exactly three factors must be squares of primes (so the factors are 1, p, and p²). Between 1 and 1000 there are 11 such numbers: 2², 3², 5², 7², 11², 13², 17², 19², 23², 29², 31². Furthermore, there are 10 powers of 2 between 1 and 1000: 2^0, 2^1, ... 2^9. The number 4 is in each list, so there are a total of 20 distinct lockers that Mark and Matt will open.

[@mcwulf25]

I could have jumped to the answer but love the proof that 4 was the least number.

[@anustupbiswas1448]

How did you think it out to take the modulo of 9?

[@Fred-yq3fs]

He told us: play cubes mod n with different values of n, so you get a "nice" set of values = a small set. He thought of 9 and contestants would too because they're used to playing with mod, so it comes naturally to them. Even this idea of reducing mod 9 to a small set of numbers is hard: You have to know that a small set will help you. That's where Olympiad contestants are not your average Joe. They've built intuition and get insights easily because they're are familiar with the subject. It does not come cheap.

[@prithujsarkar2010]

Great!

[@stkhan1945]

..u may add that x_i need not be distinct ..very impressive again..

[@stewartzayat7526]

You may, but there's nothing saying that they can't repeat, so it's redundant. Although, it would probably make it a little bit clearer.

[@daguilara9]

This video messed me up on Christmas night.

[@TIENTI0000]

I solved this) damn, I'm so happy

[@davidgillies620]

Isn't it strictly speaking the Carmichael totient function?

[@kemalkayraergin5655]

How we ensure that there are no solution for m

[@warmpianist]

If m < 4, the left hand side will never be congruent to 4 mod 9.

[@kemalkayraergin5655]

@@warmpianist thanks

[@kemalkayraergin5655]

@@warmpianist im kinda idiot, im always stucking in these easy things

[@warmpianist]

@@kemalkayraergin5655 no worries. Anyone can encounter things like this at some point.

[@aleratz]

Very nice

[@neilprabhu629]

Haha I understood but would never be able to come up with any of that

[@AlexBesogonov]

Why all the number theory problems always require working in mod N?..

[@warot359]

Are you sure this wasn´t easier and faster using calculus?

[@alainrogez8485]

Quite elegant and beautiful. What is why I like arithmetics.

[@DyegoRubio]

That's a good place...

[@tahafahim5011]

(ln(x)-ln(0.036))/(x-0.036)=5 Find x by two different solution

[@gilmonat]

Doesn't Fermat's Last Theorem shows that m>=4?

[@bellumthirio139]

no because 2002^2002 isnt a cube

[@kemalkayraergin5655]

How fermats last theorem can demonstrate it

[@gilmonat]

@@bellumthirio139 that seems right

[@riadsouissi]

Well, Fermat only tells us n cannot be 7,13 or 11. Not 3 because 2002 is not multiple of 3.

[@stkhan1945]

....it should be mentioned not necessarily distinct cubes...

[@norvias957]

Could you explain the part 2002^2002≡4^4(mod 9) again? Thank you so much!

[@henryandreaswidagdo3077]

I would do something like this: Since 2002 = 4 mod 9, then 2002^2002 = 4^2002 mod 9 And since 4^3 = 1 mod 9 4^2002 = (4)(4^3)^667 = (4)(1) mod 9 = 4 mod 9

[@Bodyknock]

When you are looking at a^b (mod n), there's a theorem that it equals (a mod n) ^ (b mod φ(n)) (mod n) where φ is the Euler Totient Function which is the number of positive integers less than n which are relatively prime to it. So for instance, 1, 2, 4, 5, 7, and 8 are the positive integers less than 9 that are relatively prime to it, so φ(9) = 6. Therefore 2002^2002 (mod 9) = (2002 mod 9) ^ (2002 mod φ(9)) (mod 9) = (2002 mod 9) ^ (2002 mod 6) (mod 9) = 4 ^ 4 (mod 9) = 4 (mod 9)

[@stewartzayat7526]

For the 2002 in the base he used the curious fact (which I didn't realize until today) that n has the same residue mod 9 as the digit sum of n (i.e. 2564 (mod 9) = 2+5+6+4 (mod 9)). For the 2002 in the exponent he used Euler's generalization of the Fermat's Little Theorem, which states that a^b (mod n) = a^(b (mod phi(n))) (mod n), where phi is Euler's totient function.

[@Bodyknock]

​@@stewartzayat7526 On a tangent an old accounting trick is "casting out nines", which is basically taking advantage of the fact that the sum of the digits of a number is its residue mod 9. When you want to quickly spot check adding or multiplying a bunch of numbers you can "cast out" all the 9s and any digits that sum to 9 and total up the rest. If the totals add up (mod 9) then that's a decent sanity check you got the right result (if there's an error it's only a 1/10 chance it'll slip through). en.wikipedia.org/wiki/Casting_out_nines

[@xCorvus7x]

@@Bodyknock Does he prove/explain this theorem in one of his videos?

[@purplerpenguin]

"Fee"? never in a million years. Nice video though, and instructive.

[@leif1075]

Why would anyone think of using mod at all though? Surely you can solve it another way.

[@anthonypham7563]

If you have dealt with a lot of cubes in number theory problems, you'll almost certainly consider modulo 9. Similarly, for squares you think of modulo 8 and for fourth powers you think of modulo 16.

[@billh17]

I think the key insight is that 2002 = 3 * 667 + 1 and thus 2002^2002 = (2002^667)^3 * (2002) which leads one to hope that one can express 2002 as a sum of a few cubes (in this case a sum of four cubes). Now that we have 2002^2002 expressed as a sum of 4 cubes, it is required only to show that it cannot be expressed with 3 or less cubes. Allowing 0^3 as a possibility, we want to rule out 2002^2002 = a^3 +b^3 + c^3. At this point, using mod is a standard technique to show that such an equation is impossible.

[@leif1075]

@@billh17 So are you agreeing mmy method of factoring 2002 works or not? I broke itndown into its prime factors none of which is 3..doesnt this way work.seeing if you cam break the terms into 2,7, 11,13, since those are the factors of 2002.i don't see why the fuck anyone would think of 3..unless because they are all cubed..

[@billh17]

​@@leif1075 I don't think factoring of 2002 will lead to m

[@billh17]

​@@leif1075 I also wish to mention that there is no guarantee that considering 2002^2002 = 2002 * (2002^667)^3 will lead to the smallest value of m since this approach implies that all the x's are divisible by (2002^667)^3 which need not be true. However, it does lead to a significant decrease in the maximum value of m since we only need to consider how to express 2002 as a sum of m cubes (seeking m to be minimum). But that minimum may not be the minimum for the proposed question.

[@ourgoalisto6737]

0:10

[@juarezmazzucajunior9529]

Maravilha

[@cernejr]

I would start with 2002^2002==2002*(2002^667^3) (last minute of the video) . Then to decompose 2002 into sum of cubes can be done by trial and error. One would obviously start with 10^3, the largest cube that fits into 2002. Now one just needs to prove that no 2 or 3 cubes sum up to 2002, minimum is 4. Proof for 2 is easy: cuberoot of 2002 is 12.6..., so one needs to only worry about 11 and 12. It can be easily checked that neither works. Proof for 3 is a little more work, but it can also be proven by listing and eliminating all the possible candidates. Since 2002/3=667.333..., at least one of members of the sum must be >=668 (otherwise we come up short). Only cubes of 9, 10, 11 and 12 are >=668. They can be all tried one at a time. A clever child with no knowledge of Euler or Fermat could solve this nice problem.

[@SylvainBerube]

In your approach, you suggest that all number of the sum have a factor of 2002^(667*3), but nothing tell us that it has to be the case. So you still have to proof that the minimum is indeed 4. That being said, I think that the initial exploration of the problem would look like what you propose for many people. And after having found that a sum of 4 cubes works, the work with modulo start to proof that it is indeed the smallest number of cubes possible.

[@cernejr]

@@SylvainBerube I am saying that the cases 1, 2 and 3 can be proved as impossible by evaluating all possible combinations. There are not that many, it is doable, by hand.

[@SylvainBerube]

@@cernejr Yes I understand that it is possible to prove "by hand" that 2002 cannot be expressed as the sum of 1, 2 or 3 cubes, I agree with you on that. But this is not the same thing as proving that 2002^2002 cannot be expressed as the sum of 1, 2 or 3 cubes. For example, 3 cannot be expressed as the sum of 1 or 2 cubes, but 3^3 clearly can. Something similar could occur for 2002^2002 (it turns out that it is not the case, but we have to prove it).

[@cernejr]

@@SylvainBerube Yes, you are correct. Now I got your point.

[@bobh6728]

@@SylvainBerube I think the point made in the video is that no matter what number you cube mod 9 has only -1, 0, or 1 as residues . So adding these together you need at least 4 to get to 4.

[@muhammedmrtkn]

My Birthyear!!!

[@johnurga275]

when i see the strategy based on 'because that's how math contests are set up,' i start to think math contests are kinda silly

[@TJStellmach]

Regardless, once you know m>=4 it's sensible to look for a solution where m=4 just because it's a high potential reward for little effort.

[@johnurga275]

@@TJStellmach yes, this is true but outside of math contests you don't reason that it'll pbl work

[@pronaybiswas7524]

Wow man!

[@natepolidoro4565]

2002 was the year i was born

[@gianmarcolettieri6150]

Wouldn't it be enough to show that, mod9, the smallest m is 4? I mean, you showed that m>/=4. But isn't that a proof that the shortest m=4?

[@TJStellmach]

Why would it be?

[@stewartzayat7526]

No, that's like saying "there are more than 10 people on the Earth (which is true), therefore there are 10 people on the Earth (which is false)". Your implication is incorrect.

[@bobh6728]

It only shows that they are congruent mod 9, not that they are equal. 9 is congruent to 27 mod 9, but they aren’t equal. But to have equality, you have to have congruence. So he was just showing to have congruence you have to have m be at least 4. From there he had to prove equality.

[@marcrenard515]

We can stop to m>=4 if the question was : find a lower bound for m, but here we need the smallest m, in fact it's equivalent to find the highest lower bound. So when we have m>=4 we need to check if it is the highest lower bound by finding 4 numbers such that the sum of their cube is 2002^2002

[@gianmarcolettieri6150]

Thank you all for the answers! What I was thinking is that, when you show that x1+x2...+xm must be congruent to 4 mod 9, and you show that x1,x2...,xm€{-1,0,1} mod9, doesn't that imply m=4? Because the smallest m such that if you add numbers in that set you get 4 is exactly 4.

[@UltraMaXAtAXX]

Oh, another ridiculous number theory problem.

[@Jon60987]

Ok, this was impressive.