You, me, and my first International Math Olympiad problem
HTML-код
- Опубликовано: 19 авг 2024
- My first international math olympiad (IMO) question. We will find the sum of the digits of the sum of the digits of the sum of the digits of 4444^4444. This is a pretty famous number theory problem.
Check out more fun math competition problems: • A circle tangents to a...
----------------------------------------
🛍 Shop my math t-shirt & hoodies: amzn.to/3qBeuw6
💪 Get my math notes by becoming a patron: / blackpenredpen
#blackpenredpen #math #calculus #apcalculus
So most of you guys focused on the math, which I appreciate, so thank you. But how are you doing?
Quite good. As long as i dont die through engineering homework ill be fine XD
Just keeping busy but doing well! Hope this storm of the virus ends sooner than later though... Anyways, thank you for this video, it was great (and funny)! I'm sure videos like these allow people to distract themselves from the current situation :)
4444*4444=16*10^7+16*10^6+16*10^5+16*10^4
16*10^6+16*10^5+... +16*10^3
... +16*10^2
+16*10^1
... +16
16(1234321)
4444*4444*4444=64*10^10+2*64*10^9+3*64*10^8+4*64*10^7+3*64*10^6+2*64*10^5+ 64*10^4
+1*64*10^9+2*... +3*64*10^7+4*64*10^6+3*64+... +2* +64*10^3
+1 2 ... + 3 +4*64*10^5+3* +64*10^2
.... 1 2 +3
... ...+ +64
64(136(10)(12)(12)(10)6 31) is so nice that pattern no?
need to calculate 4^4444 and to find he patern note 4^4=c
4444^4=c*10^13+3 ...+6..+10+12+12 +10+10+6+3+1
1 3 6+10 12 12 10 6 3 1
1 3 6 10 12 12 10 6 3 1
... c(14(10)(20)(32)(44)...)
that is what I think but I dont complete because is hardcore
and needet to know 4 ^4444 and all digits so impossible
Big fan of yours
BPRP: “I don’t look at the IMO problems because I’m just not that smart”
Damn.
DavidAde and here i think he's smarter than the majority of us
Leart Ajvazaj 😂😂😂absolutely the same case with me
tbh p1 and 4 are easy if you win ur country's nationals.
Going to IMO requires a lot of practice, that's all. (and ofc a bit of luck)
@@tacticalcaptain8279 ya you right.
awesome vid! 🤩
It's always nice to find out that two youtubers you watch know about each other
Ayee tibees!
Yo tobi👌
I like you tibees... And you are amazing..
You are a great teacher.
I wish if i could get u as a teacher ..
@@tanmayjain2198 she kinda cute too ngl
For the segment starting at 18:00 (finding 4444^4444 mod 9), you can also do the following: 4444 == 7 (mod 9), 4444^2 == 4 (mod 9), 4444^3 == 1 (mod 9). Therefore, 4444^3n == 1 (mod 9) for all n. Since 4443 is divisible by 3, 4444^4444 = 4444^4443 * 4444 == 1 * 7 (mod 9). Saves you the repeated squaring.
Very elegant, I love it! I'd like to specify that this is all *integer* n thougb
Exactly omg
By euler's theorem, a^phi(n) = 1 mod n if a and n are coprime,
in this case 4444 is coprime with 9 and phi(9)=6 so 4444^4444 = 4444^4 = (-2)^4 = 7 mod 9
oooh yeah always do that
At 10:09, you could have written d((10^17777) - 1)
"Four four four four to the fofofofo power" 😂
Vitor Trivilin lol 😂😂😂
I don't understand why did he replace with nine
@@darkkyne6261 To get maximum value so that he can use the inequalities.
@@darkkyne6261 if he didn't the inequality could not be true, for example: 39 < 40 but
d (39) > d (40)
In order not to happen this situation, the added 9 instead, because even if the smaller number has the same quantity of 9's , the first digit of the bigger one is obviously bigger than the smaller's first digit
It sounded like he was saying wolf.
I feel like his pens are quantum entangled into another dimension, where it supplies an infinite amount of ink into his pens through teleportation.
XD!!
Now prove it
read your comment differently the 1st time not gonna lie
@@sonpham3438 ew
That doesn't even make any sense. As soon as you start talking about extra-dimensional entanglement. You must not really know how quantum entanglement works.
This question was in my practice book of PRMO(first level of imo in india) and my teacher tried this question for about 45 minutes . Then he left saying that he had other classes.
So thank you for providing this beautiful solution
lmao
😂
Beta would be disappointed 😞
Why do they ask such ridiculous questions? Why not ask questions which have real life applications?
@@jkifgjf2173 because people want to flex how smart they are, like personally me I don’t care if you know the hardest partial differential equations 😂. You can live your life and do math forever and flex on people and I’ll live an actually fun one 🥱
“Of course I never participated in the IMO because I was just never that smart.” This is why people love watching your videos. You’re a really humble and bright and cool guy.
I had basically this same problem in 1989. The question was the sum of digits of sum of digits, etc of 1989^1989. I saw off the top that the final value is congruent with 0 mod 9, and did a little work to conclude that the next-to-last sum was a maximum of 40 or so, so the final sum could be at most 3+9=12.
Somehow I didn't get past this point, and gave my final answer as "either 9 or 0" being the only values congruent with 0 that are less than 12.
I'd lost sight of the original question asking for a sum of digits, and that the sum of digits could only be 0 if the number being summed itself is 0 which it clearly wasn't.
How many points did u get?
Ouch
Can you guide me
Luns Tee your big brain lead to wrong answer. I’ve been there dude.
I too am haunted by math questions past! Lol
Here's a fun a game:
Take a shot each time he says 4
I'll be dead 4 times over
Yoav Mor 🧐
this video but the speed increases every time he says 4
@@ssdd9911
Matt Parker from Numberphile actually made a video like that of an old Numberphile video a couple years ago, which he named "The Four 4s - but every time they say '4' it gets 4% faster".
He even got a speed increase that was approximately 10⁴% faster at the end of the video and drew attention to the 4-exponent, while a kickass heavy metal riff was playing in the background.
@@Peter_1986 it would be harder for this video since it's longer
First minutes: i feel smart
thirteen minutes in: i feel stupid
No need to feel stupid; everything requires hard work. With practice, you'll get better. Keep practicing :)
This doesn't often happen to me with maths lectures, but 5 minutes in I felt stupid, but after 20 minutes I felt smart. Bit staggered at the end to discover that he can, after all, get the digit sum of 4444^4444 on his freakin' calculator!
"Well actually I don't understand the question 99,99999% of the time"
Me: You gotta pump those numbers up. Those are rookie numbers
Lol. About 99.99999999999999999999999% of the time, I don’t understand the last question on the Putnams.
how does 100% sound?
Who is Srinivasa Ramanujan
100-dx%?
@@study5133 A very popular Indian mathematician basically
10:54 me checking if 1+1=2
😂😂😂.
Loll
Rewrites 1+1 as a summation that diverges and therefore states that 1+1=2 is no solution since the Diveegence theorem of a series claims that a series diverges if it does not go to zero. 😂😂😂
Also 30:35
@@blackpenredpen lol
I never enjoyed someone saying four so much, until this video came out.
Svetozar Delchev lol!!
This is 4 you!
@@blackpenredpen 1600>16 likes>dislikes, but if we use the same technique in the video for the d(n) sum, we get the same number, which is obviously a cheat from RUclips. :)
@@blackpenredpen lol
nice solution!
for those interested in the mod 9 trick, its called "casting out nines" and theres a well written wikipedia page for it
For a quick link:
en.m.wikipedia.org/wiki/Casting_out_nines
@@jofx4051 you're a good man
@@benjaminsvoboda2046 yes :D
Read it -- thank you!
The amount of joy at the end!
Too much time in quarantine, hah?
Thanks for keeping me sane in this period of craziness.
Right?😂. He's a savior
16:55 "please don't ask me to prove this."
YOU KNOW WHAT TO DO, EVERYONE.
It's just induction on the number of digits tho.
For one digit it's trivial, and for a number k-1 of digits if you put a new digit d on the left it's the same as adding 10^k * d, which is (999...9 + 1)*d, which is congruent to d mod 9.
@@Martykun36 Yeah it's actually a really short proof. 10^k is congruent to 1 (mod 9), so then sum of 10^k * d is congruent to sum of d (mod 9).
Everyone : Yes, but actually no.
Blackpenredpen : No, but actually yes
me: Bruh..
🤣🤣🤣😂😂😂
159984... No... Yes
Wow! That was a really cool approach that I wouldn’t have thought of.
For calculating the value of 4444^4444 mod 9, the method that was used in this is known as binary exponentiation. It's used by computers for finding the values of (large number)^(another large number) (mod a large prime), because it's probably the best way when the mod thing is really large. In this case though, since 9 is quite a small number, there are some sneaky theorems and tricks you can use to calculate it a bit faster. In fact using this method you can keep all the numbers small enough that you can do all of it in your head if you've had some practise at mental arithmetic and solving problems in your head.
First, you spot that 4444 gives remainder 7 when divided by 9 (by doing the digit sum in your head, d(4444) = 16, 16 gives remainder 7), so then you are trying to work out 7^4444 mod 9. Then by euler's totient theorem (this is one of the op sneaky bits lol), 7^(totient(9)) is equivalent to 1 mod 9. (if you haven't heard of it, I recommend looking it up on wikipedia. it's a generalised version of fermat's little theorem, and fermat's little theorem is useful load in imo, and euler's totient theorem is also often useful.) Then you can work out totient(9) in your head is 6. Then you can rewrite 7^4444 as 7^6n times 7^k, where k is the remainder when 4444 is divided by 6, and n is (4444 - k) / 6, but we know 7^6 is equivalent to 1 by euler's totient theorem, so 7^4444 is equivalent to 7^k mod 9. You can work out k in your head using normal division I guess, but there's actually another op sneaky trick to work it out in your head, which is called chinese remainder theorem (again if you've not heard of it, try looking it up on wikipedia). This states that you only have to work out what the remainder of 4444 is when divided by 3 and then the remainder when divided by 2, and then you can find out what the remainder is when divided by 6. Working out the remainder when divided by 3 is simple, because you can use the digit sum trick like when doing it with 9, and then we find 4444 gives remainder 1 when divided by 3 (because d(4444) = 16, d(16) = 7, 7 gives remainder 1 when divided by 3). The remainder when divided by 2 is obviously 0 since 4444 is even, and by the chinese remainder theorem, 4444 gives remainder 4 when divided by 6. So therefore 7^4444 is equivalent to 7^4 mod 9, which you can do in your head as (7^2)^2 mod 9, which gives 49^2 mod 9, which gives 4^2 mod 9, which gives 16 mod 9, which gives 7 mod 9. Not that it would make sense to do it in your head, but I'm just trying to show that it's possible to keep all the numbers small enough that you could if you wanted to, which means you could do the working on paper faster since the numbers are smaller, and you'd be less likely to make an arithmetic error.
In fact, when it comes to number theory in the IMO, chinese remainder theorem (CRT for short), fermat's little theorem (which is a specific case of euler's totient theorem) (FLT for short) and unique prime factorisation (UPF for short) are the main theorems that are useful in the beginner IMO questions (questions 1 and 4 from each paper are considered beginner questions, and this one is a q4, q2 and q5 are medium, and q3 and q6 are hard), so if you don't happen to know CRT and FLT, it definitely makes it harder to do these kinds of questions. In general in the IMO, they try to make questions not rely too heavily on knowing lots of theorems, so even though it may sound like they do actually use lots of theorems, it's not the case really, since you can learn CRT, FLT and UPF quite quickly, and then you would find that you know pretty much all the theory for beginner number theory at IMO, but you still need to practise doing the questions, because the challenge lies in using the theorems. Anyway, what I'm trying to say is that just because you struggle with IMO questions doesn't make you not smart, because it's actually just a matter of whether you've practised specifically for IMO. It's rare for anyone to be good at IMO without practising, and there are plenty of great mathematicians who aren't good at IMO questions.
Hi, I just wanted to say thank you for the suggestions and imparting your advice.
shortest math explanation
I like how he said, "99.99999% of the time i dont even understand what the IMO questions are asking." Sums up my constant state of confusion in doing my best to fully understand his lessons (i did learn a lot from your vids just to clarify thanks!) :")
Please do more IMO number theory problems! This was great!
7:02 "we can bring the power to the front but please do not minus one because we're not doing calculus am I right" that is officially the nerdiest joke Ive ever understood.
As an IMO contestant I can tell you pretty good job!! You nailed it.
Still, I think that the binary 4444 wasn't necessary because of:
4444=7
4444^2=4
4444^3=1
4444^4=7
So you get the pattern:
4444^3n=1
4444^(3n+1)=7
4444^(3n+2)=4
And it's easy to check that 4444 is a 3n+1 kind of number!
I hope you keep on solving high school olympiad problems, they really open your mind, and I would suggest checking some of the Iberoamerican olympiad problems, usually a little easier than the imo ones but really challenging as well!
Rule of thumb: Whenever you see an IMO digit problem always take (mod 9)!!
Next video: IMO 2017 , Problem 3.
Check out the Individual results on the official site of IMO :)
Ur in the 2017 team of Azerbaijan?
I'm partial to IMO 1996 P5. All you have to do is generalise the Erdos-Mordell inequality, something that itself took two years to solve when it was first proposed.
Wow, really? They love to test the bounds of these kid geniuses, don't they.
@@keithmasumoto9698 Yeah in one of the years, I forgot which one, the actual judges put a problem into the test that they themselves could not solve in... it was either 6 or 9 hours.
@@sheppsu7353 the question 6
Man i am so much happy that i was able to understand the whole explanation and you are so funny, i laughed a lot during the video. Have a good day!
Gabriel, Brazil
I am glad to hear!! Thank you.
Eae, tmb sou do Brasil. Se preparando para o teste de seleção da IMO?
@@jonathasdavid9902 não sou do nível da imo não mano kkkk eu to estudando pro ita só, comecei tem pouco tempo
@@djvalentedochp Atá, boa sorte no ITA, que tbm é desafiador, eu particularmente não consigo fazer a prova do ITA
Imagine this being a million dollar problem and you knew the answer has to be a single digit number, so you just guessed 7 because it is your favorite number😂😂🤣🤣
I cried on solving my first IMO question tough it was a easy one.
Qestion no 1 of first IMO.
Still it made me happy.
Very innovative solution, but there was a slight mathematical error with the first part:
When calculating the maximum possible value of d(x), when x
Only three iterations of d(n) are taken so it’s just 12
@namanpushp5364
Appreciate this correction as I was thinking about this very error while watching the video but wasn't sure if it was just me. Well, now I know. Nonetheless, there's another slight mathematical error in your correction. (I'm loving the recursive error correction, which is in tune with the question and solution lol!). I completely agree with your reasoning for calculating the smallest upper bound but it seems that you have forgotten to apply it yourself during the first "iteration" of d(n). Also, writing d(n) = 17776 would be incorrect as 'd(n)' had been defined as the sum of all digits in the number "n", whereas here, '17776' is the *number of digits* 4444⁴⁴⁴⁴ contains rather than the *sum of all the digits in 4444⁴⁴⁴⁴ itself.* Another major blunder is writing "d(n) = ...". Since we're only concerned with finding an upper bound, the inequality sign that must be followed by d(n) is a *"strictly less than" (
Error at 17:45. Should be 493. 4*9 = 36! :) Fortunately, you were only interested in the remainder.
Since when is 4*9 equal to 36 factorial? Wow, I really should study the multiplication tables
@@byronvega8298 rewrite it as a Jacobian Matrix lolol
I'm not convinced 4*9 = 371993326789901217467999448150835200000000
4444 = 7 mod 9 ; 4444^2 = 4 mod 9 ; multiplying both of them,
4444 * 4444^2 = 4*7 mod 9 = 1 mod 9
((4444^3)^1481) = 1^1481 mod 9 = 1 mod 9
4444^4443 = 1 mod 9
4444^4444 = (1*7) mod 9 = 7 mod 9
Optimal! I like the efficiency.
The best solution in the comment, I guess
Yo bro
Yeah, the order of 7 mod 9 is 3, so you can just take the power mod 3, so 4444 = 1 mod 3, that makes the entire squaring part unnecessary. 4444^4444= 7^4444 = 7^1× 7^(3×481) = 7 mod 9
Great
What’s funny is that I was recently doing a programming challenge for finding digit sums of digit sums of really large numbers. We had to find an algorithm, and I knew that it would involve modulus/modulo but wasn’t sure where to even start!
A naive approach using modulo on Python 3 ran out of memory real fast. Since only the digits themselves mattered, I used a string...
Use integer division by 10, then take new number mod 10 to extract first digit, then divide by 10 then use mod 10 to get second digit, and so on? A simple approach but I don’t think mod 10 gives issues?
imagine the meme value if the answer was 4
It's really cool to see IMO problems here!
Great video.
Euler-Phi is a useful theorem for dealing with exponents in modular arithmetic:
phi(9) = 6 (the amount of naturals relatively prime to 9 less than or equal to 9) where phi is euler's totient function.
Hence 4444^6 = 1 (mod 9)
=> 4444^(6*740) = 1^740 = 1 (mod 9)
=> 4444^4440 = 1 (mod 9)
=> 4444^4444 = 4444^4 = 7^4 = 49^2 = 4^2 = 7 (mod 9)
It's a bit faster but the powers of 2 method is really cool and intuitive for viewers unfamiliar with the theorem.
7:06 that sudden joke had me dying lmao
Hey dude. Can you explain that "do not -1" to me?
@@arnavagarwal2914 he is making fun of the power rule when taking derivative
@@arnavagarwal2914 when you find the derivative using power rule, you take power of the variable you are w.r.t and then reduce the power by 1
in the last step, i see
that 4444 ^3 congruent with 1 mod 9 ==> (4444^3)^1481 congruent with 1 mod 9 ==> 4444^4444 = (4444^3)^1481 x 4444 congruent with (1x7)=7 mod 9
in my opinion, i think it's a little bit faster , but your solution is really cool too. I really like your video. Thanks
Amazing observation! I didn’t see it!
What if we kissed by the whiteboard where you did your first IMO problem.....Haha, just kidding..... Unless.......😳😳
This was delightful to watch. My peers consider me good at maths but I'm nowhere near IMO level. But felt good to be able to clearly understand the entire procedure!
What a coincidence!!!
I saw this question in a book I was using to practice Olympiad problems but I couldn't solve it.
To my surprise you made a video about the solution!
Thanks!
It is pretty hard stuff though.
what book were you using?
@@cheesywiz9443 it was an Indian publication
@@tanmaybarik2822 oh :(
is there any pdf version online?
I had seen this problem in a book called senior high school mathematics competition lecture published by china
@@cheesywiz9443 no chance. Sorry !
It's amazing the crazy stuff you can do with mod mathematics if you know what you are doing. I went down this rabbit hole about a year ago and it blew my mind the large numbers you can handle. I have an actual degree in Mathematics, studied this at university, but I don't think I truly grasp the powers of it. It really should be taught far more in highschool
Man this problem is so funny and you solved it so beautifully. Congratulations.
Thanks for the video! The first IMO problem I solved was surprisingly easy I think - 1961 Problem 3 "Solve the equation cos^n (x) - sin^n (x) = 1 where n is a given positive integer."
It was quite simple when I came across it since I learned about phase shifting already, but I would definitely love to tackle more of the questions!
You don't need to use the powers of two. 7^3 = 1 (mod 9), so that means that we can just get 4444 by modulo 3 so 7^4444 = 7^16 = 7 ^ 1 = 7 (mod 9).
Yes that part was painful to watch
Very good! Your hard work paid off.
14:46
My heart stopped right there..............
18:26 -> 25:13, you could make 4444 at the power 3 so 4444 is congru to 1 mod9 . Then 4444^3n=1^n=1 mod 9 . Now 4444=3*1481+1 . 4444=3n+1 (where n=1481) . 4444^3n+1=1*7=7 mod 9 . It’s faster! ( sorry for my English Im french)
Shoot!!
Awesome video blackpenredpen
Here is a shorter method to do that modulo congruency
4444 = 7 mod 9
4444²=4 mod 9
Multiplying both
4444³= 1 mod 9
(4444³)^1481= 1¹⁴⁸¹ mod 9
4444⁴⁴⁴³ = 1 mod 9
Multiplying by 4444
4444⁴⁴⁴⁴ = 7 mod 9
I really enjoyed the video!
There is actually a much easier way of computing 4444^4444 mod 9. You already showed that this is congruent to 7^4444, and 7^2 ≡ 4. After multiplying once more, you notice that 7^3 ≡ 7*4 ≡ 28 ≡ 1 mod 9. So 7^4444 ≡ 7 * 7^4443 ≡ 7 * 7^(3*1481) ≡ 7 * (7^3)^1481 ≡ 7 * 1^1481 ≡ 7.
WHY THIS WORKS: The trick was finding an exponent b so that 7^b ≡ 1 mod 9. This is always possible when you base (7) and module (9) are coprime, because of the Euler-Fermat theorem: for any a, c that are coprime, a^(phi(c)) ≡ 1 mod c, where phi is Euler's phi function. So the first exponent that gives you the result 1 is always a divisor of phi(c).
In the special case, phi(9) = 6, so we know that 7^6 ≡ 1 mod 9, and it happens to also work with an exponent of 3.
Did anyone else feel the computer scientist inside you scream "this is binary!!!!!" when he was adding those powers to 4096 to get 4444😇
doesn't that only work because 4444 is an even power in this case?
@@carlosrosales1712 he also knew 4444^1 was congruent to 7 so if it was an odd power he could have just added that on.
Completely, and it’s so awesome too see that in “normal” math. It’s like when I first saw Russian multiplication.
@@carlosrosales1712 Actually, any number can be written as a sum of integer powers of two.
I really dont know, no shit, that’s why computer can do it
4:08 that smile is precious! Nice work!!!
😁
I remember when I was 14 and my friend, who was also into math, took some IMO problem to school and showed me. We were both able to solve it, which really boosted our confidence back then. Later the friend won a gold medal at IMO (1,5 year later) and I also did have decent results on the national stage. It is good to have some easier tasks at IMO, just to give kids joy and a feeling they can work hard to reach for their dreams.
Please post more on IMO problems because they are at a level of mathematics that most reasonable high schoolers (and above) can grasp in terms of theory, but would still appreciate a logical method of solving them, as it is usually the logical pathway into these rather simple problems that is difficult.
I'm just 1 year out of high school, and here is my opinion on IMO. I never did or even see its past papers during my school time, but I knew it existed. However, I did great in my high school mathematics subject. And this year, during quarantine, I decided to give it a try just for fun. I found that it is actually quite doable, because, I could solve quite a few of the problems alone, with no prep, reviews, etc.
One key point is that IMO is a problem-solving exam with mathematics as the topic, which means it heavily relies not on your "mathematical intuition" (which could be of help nevertheless) or high school mentality of reading a situation and using formulae, but on your deductive abilities. Also, it can be helpful to see a difficult problem from an angle such that the problem is equivalent, but much easier to solve. This is what I would say is the creativity in logic that can be helpful. Overall, I don't intend to do mathematics as a course; this exam is still doable for me, mostly the algebra questions. I also tested a few people on it who are not doing any mathematical subjects in university, and they could also solve a few of the problems.
Edit: my inquiry to the reader: Is it just me, or is it true that the algebraic questions are easier in IMO than the geometric ones ? (I know geometric questions can be expressed in algebra and solved that way; but any question that primarily deals with geometry I have found was rather difficult to approach / understand.)
Why do you think one may be bad at geometry ? Is it perhaps that geometry is like a science and one needs know the theorems to deduce results so as to solve the problem, or does it have to do with one's spatial awareness and _imagining_ the solution setting ?
I'll be humbly thankful to anyone who reads this post and replies to my queries. I happen to be fascinated by mathematics as a subject of abstractions.
Mr. Anonymous I have the same question about geometry
@@artka250 yeah but its a shame this comment got little attention. Regardless what i think may be the case is this: you need to learn and know the theory of geometry as knowledge base exercise and then be comfortable enough with it and have a strong intuition for spatial imaging to be able to deduce relevamt results easily as your image processing cuts the logical pathway into the problem...
But i could be wrong.
Edit this video such that every time you say “4”, the video speed increases by 4%.
It will only take 7 milliseconds🤣🤣
the video will then be four minutes long
LOL
@@drewviz5102 7 LIKES AND 7 MONTHS AGO OMG
I’m French and I’m actually in a kind of college named « prepa ». This is a place where we discover the most hard mathematics lessons and our lectures are overgraduated in mathematics. We’ve already done this exercice for an evaluation and we’ve solve it really differently and most simply. We’ve stratEd like you by watch that 4444^4444=7[9] then just by framing of this by 1000^4444 and 10000^4444 we are arrived to the result without big difficulty.:) Edit: sorry for my bad English 🙏😅j’apprends l’anglais même si je ne suis pas très bon
Ah, la prépa. Pas trop dur? Je veux aller dans de grandes prépas l'année prochaine, et je stresse pas mal. Tu supportes?
Augustin Tinon pour le moment je m’en sort deuxième de ma promo donc ça va 😆 c’est dur , tu vas fournir énormément d’efforts et t’auras jamais l’impression de comprendre tout mais une fois que tu t’y fais tu t’en sort( le but en prepa c’est d’être meilleur que les autres et non pas d’être excellent comme au lycée, raison pour laquelle on note généralement pr majoration). Si t’aime bien te casser la tête sur des bizarreries mathématiques et que la compétition entre élèves te fait pas peur c’est pour toi 😁
It would be great if you could upload more IMO problems
I really enjoy your videos Bprp
Drinking game (warning: potentially life-threatening); take a drink every time he says "four"
You could have saved so much ink by introducing x = 4444. :D Also, a nice trick for exp mod is to do it in binary (which is what you really did). 4444 = 0b1000101011100. The powers of 2 are 1, 2, 4, 8, 7, 5, 1 mod 9.. As soon as you get a repeat, you're done, so it really is [1, 2, 4, 8, 7, 5], [1, 2, 4, 8, 7, 5], .. . Multiplying those remainders by 4 (a factor of 4444) you get the Boeing pattern. Even powers of 2 in x contribute a 4, odd a 7, mod 9.
I loved your honest confession about the fact of not even understanding what the IMO questions ask. I can so much relate to you. I often think they get the questions from some other planet. Hats off to the guys who manufacture the problems.
I have never encountered a more exciting SEVEN in all my life! Thank you and well done!
That's really awesome, but an easier way of thinking about the powers of two sequence is as the binary expansion of 4444.
Im a math enthusiast, in one of my problem books, they had given an IMO problem as a 'level 1 exercise'
That book was crazy
which book?
We gotta know. Which book?
You gotta say the name now!
1 year later, I call bullshit
Maybe you're referring to a book from Art of Problem Solving or Titu Andreescu
Little shortcut sparing a lot of calculations :
4444 is congruent to 7 mod 9, so 4444^3 is congruent to 7^3 mod 9, same as 1 mod 9 (because 7^3 = 343 = 37*9+1).
Notice that 4443 is divisible by 3 because d(4443) = 15 is divisible by 3. Say 4443 = 3k for some integer k.
Thus 4444^4443 = (4444^3)^k is congruent to 1 mod 9, then multiply by 4444 and conclude that 4444^4444 is congruent to 4444 mod 9, which is 7 mod 9.
Dude, you are awesome. The way you solved and explained the problem, is genius.
When I first saw the fours, I thought they were all psi's 😂
Bryan Lamb lolllll
ha me too
0:41
I have never participated in the IMO contest Because I'm just never that smart...
If you are 'not that smart' what ranks do i belong in?😅😅
If you remember high school, well above average American
The top 600 students do the IMO. If someone doesn't get in doesn't mean they're bad.
You're an excellent teacher. Entertaining and educating. Thank you
Really quite a tough problem. I have a PhD in maths but had no idea how to tackle this problem. Think this was a very elegant, clear solution and presented with great enthusiasm. Think you need slight larger whiteboards!
Me : reads the title.
Also me: clicks on the video and reads the question
*Brain.exe has stopped working*
Pour les français, fun fact: c'était aussi une question posée à l'oral de centrale.
qu'est ce "l'oral de centrale"?
30:37 I can understand the feeling of that 😂😂, casually doing insanely difficult problems but tripped on basic addition
Him: 2 happy happy to finish the question
me: 2 happy cuz i didnt fall asleep while thinking about the question
Take a shot every time he says four
Not sure if you really want to do that 😆
Dude, you're amazing
You are too! Thank you.
The idea of combining the reduced value space with the exact modulo 9 digit sum calculation is astonishing. When he started to speak about divisibility by 9 i first thought: What the heck is he thinking to approach with that stuff? It has all but nothing to do with the task at hand, does it?! But when he ended up applying this principle to the digitsum of digitsum recursively, the realization suddenly flared up.
I found out that the number 4444^4444 is larger than number of my brain cells.
7:05 the amount of times you must've seen that done in exams must be traumatising. Great video and thank you! Did you come up with all of this yourself?
Hey dude can you explain that "do not -1" to me?
@@arnavagarwal2914 sure! Because when you take the derivative of a power function you bring down the power and minus one. I guess some people get it muddled up with the logarithmic properties. Hope this helps!
Teaching higher levels, sometimes i forget arithmetic too :p....
it's funny how arithmetic can be the most tedious and frustrating of maths, even in higher levels. sure, we have cheats for 1+2+3+...+99+100, but what if we had to add 100 non-consistent numbers? Of course we'd have to add them up one at a time..
The key observation is that d(n) acts as log. Once you got that it just comes down to the routine of estimation and finding some invariant.
He multiplying in his head gives me the chills
Bro you deserve a nice large white board, I felt bad for u having to keep wiping your intellectual work.
Sorry, not enough space. Hopefully everything will be fine soon and I can return to my classroom : )
17:28 lol you could just have used the identity you showed and added all the 4s
It seems he is not familiar with properties of congruences. So, it means he deserves more credit for solving the problem without the proper tools.
He could have also saved himself a lot of time later by noticing that:
1) 4444^1 ≡ 7 (mod 9), 4444^2 ≡ 4 (mod 9), 4444^3 ≡ 1 (mod 9) and then they start repeating.
2) the period length is 3, therefore check that 4444 ≡ 1 (mod 3).
Taken together, this implies that 4444^4444 ≡ 4444^1 ≡ 7 (mod 9).
But it’s actually more impressive that he managed to get to the end of it without knowing these “tricks”.
Numbers coprime with 9 are closed under multiplication, so they form a group. Modulo 9 there are six such number 1,2,4,5,7,8. This means x^6 is congruent to 1 modulo 9 for all x coprime with 9 (cosets, generators form a group etc). We must find 4444 modulo 6. 2 divides 4444. There is a remainder of 1 modulo 3. So 4444 is congruent to 4 module six. So 4444 ^ 4444 is congruen to 4444 ^ 4 modulo 9, which is congruen to -2 ^ 4 which is congruent to 16 which is congruent to seven.
Fermat's little theorm makes this much easier, it states that
a^p = a (mod p) if a and p are coprime
4444 and 9 are coprime (verifiable by checking that 3 doesn't divide 4444, which can be done by verifiying that sum of digits of 4 doesn't isn't divisable by 3)
This means that:
4444^4444 =
7^4444 (by normal modulo rules)
= 7^7 by little theorem
= 823543
= 7
All mod 9
16:54 lol maybe for the next video? Doesn’t sound too hard :P
The last Vsauce video is about that (or the second to last D!NG video.. I don't remember) and indeed, it's very easy to prove
Try by induction and prove p(k) => p(k+9).
Another way is to write the numbers as sum of powers of 10s:
123= 1*10^2 + 2*10 + 3 and observe that 10^X mod 9 is 1, so Y*X^10 mod 9 is Y. So (XYZ) is congruent with X+Y+Z mod 9.
You can find more methods.
(a + 1)^n = ak + 1 , n and k are natural numbers
So you can write the number as a sum of bases of 10 and make 10 = 9 + 1
x (9 + 1)^n = 9xk + x
Do this for all digits of the original number
This number will only be congruent 0 mod 9 if the sum of the digits are congruent to 0 mod 9 as well
Hope i was good while explaining, i am brazilian and it's quite difficult to express myself in english while talking about math
DJ VALENTE DO CHP Thanks for the comment, I was thinking of something similar but your answer is super elegant!^^
12:25 why can you keep the first digit to be the same?
I understood nevermind 😅
If 159984 is the upper bound, the highest digit sum wil be d(99999)=45.
@@louiswouters71 no that's not it, it's d(199999)=46 because the first digit is a 1 at max, so we can keep a 1. For the others, it could be any digit, so the max is having 9 for all of them, hense 199999. 99999 isn't wrong, but it wouldn't be strictly bigger than the actual number. In the video they keep strict inequalities.
That was amazing BPRP! Congrats on 1M Subs!
You're one of the mathematicians who inspired me to also make math youtube content :D
Thank you for teaching me and the world math!
Do the legendary
1988 IMO Question 6 next plz :)
ruclips.net/video/Y30VF3cSIYQ/видео.html
and there is also another )linked video) with the solution.... boy this is some mythical stuff
10:54 hahaha
Wonderful content!!!! I watch it nearly every night before I go to sleep
Those nights I sleep amazing
I love your introduction!, Vey good problem, I was rechecking a lot of times. It's good to see you use the modp again :)
I love this video and I love even more that I actually understood everything (I'm 14)
Geralt of Rivia wow that’s really awesome!!
Geralt😂😂. So you're a witcher
Same for me!
Unfortunately IMO might not happen this year :(
Aren't they trying to postpone to September?
@@frank-ek4cy They're trying but there's no guarantee it will work. The CORONAVIRUS situation isn't going to be over by then.
@@anticorncob6 that's sad man,anyways hope the situation becomes normal as soon as possible.
Thank you, I love and appreciate this problem and your solution, very much.
>>> import sys
>>> 4444**4444
Traceback (most recent call last):
File "", line 1, in
ValueError: Exceeds the limit (4300 digits) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit
>>> sys.set_int_max_str_digits(9999999)
>>> def digitsum(x):
... s = 0
... for a in str(x):
... s += int(a)
... return s
...
>>> print(digitsum(digitsum(digitsum(4444**4444))))
7
I guess you're right. I feel just calculating it is much simpler though.
What is imo?
International mathematics Olympiad
Also the place where you realise most Maths in primary/secondary school is extremely unequipped to tackle the creative beauty in Mathematics. A whole list of every IMO dating from 1959 to the current year can be found on the Art of Problem Solving website. (literally google AOPS and you'll find it)
4:09 WTF I SAID 7 AT THE EXACT SAME TIME AS YOU
Finally he starts something different than solving integrals. I love it 😁😁😁
I often keep visiting this video just to see his enthusiasm and happiness solving the problem.