At 6:15 Can someone explains how he can just not take care of the terms in brackets for the equality ? I understand that it is important to prove that the Power of twos are equal, but for the equality to hold you can't juste skip the terms in brackets, non ? I would really appreciate an enlightement.
@@phinix4912 The G.I.F of K/2^m will always be less than the actual value as we take the nearest integer that is *less* than the value hence the product of lesser values will be lesser , thats what he meant
Same here, even though there is a simpler solution for this case (as if k is even then k! is divided by 2, (k/2)(k/2 - 1) / 2 times, and the RHS is divided by 2 exaclty 2^(n-2) times, so k/2 has to be no more than 2 (otherwise, k/2 or k/2 - 1 will be odd and this equality wont hold for sure) and then its easy to check for all k up to 5 (since 5/2 = 2 in integer division) )
Not sure why he shortened the formula making the pattern unclear, in the actual competition the third term (2^n-4) was written disambiguating the formula.
Hi Michael, I am a viewer from China and I would like to suggest a problem, taken from the 2008 National College Entrance Exam (NCEE). This is the last question (hardest) on the exam. It is said that 99.9% of the students got a score of 0, and only 3 students (out of 300,000 who took this version of math exam) scored above 50% on this question with 9 out of 14 being the highest. This question was criticized for being too difficult. Many math professors said that this question should be given to a math competition, not the NCEE, which is designed for regular grade 12 students applying for colleges. Here’s the questions: f(x) = 1/sqrt(1+x) + 1/sqrt(1+a) + sqrt[ax/(ax+8)], x is a positive real number Prove that, for any positive real number a, 1 < f(x) < 2
Ohh! The problem-setter gained widespread notoriety due to that problem as well as the difficulty of the entire exam. Also, even outside China, the NCEE is more widely known as the Gaokao.
I don’t know if I’m not rigorous enough but can’t we prove that it’s a monotonically decreasing function and since it’s a positive real number the bounds for x is 0 to infinity. Then evaluate the function at 0 and infinity by taking limits. At 0 it would be 2 and at infinity 1. So proved? Idk
@@lucas29476 the question seems too easy unless there was other things i didn't see. Proposing this to imo will be terrible idea. Students may fail due to pressure and timing.
BMO2 2011 P2 is nice If you do geometry I'd recommend BMO2 2019 P1 or IMO 2007 P1/4 (can't remember which one is the geo) Also the first 3 from BMO2 1995 or BMO2 2001 and 2003 P1 are nice Loving the videos btw I'm working towards making IMO next year and this is helpful
please try this geometry question here: take a trapezoid of sides and height being integers. Prove that the perimeter of this trapezoid is even and its area is integer
Oh, that's from Olimpíada Cearense de Matemática, isn't it? If I recall correctly, thinking about the how the sides' parities relate should be enough. Not sure though.
Seems like shooting a fly with a rifle. If we consider all the possible factors of Π (2^n - 2^(n-i)) we can just take out the powers of two and notice that the only possible odd numbers in our factorization must be one less than a power of 2. Since 5 is the first odd number which is not a power of 2, and all k! for k ≥ 5 must contain a factor of 5, the only possible solutions are for k less or eqaul to 4.
Following your proof is not hard, but coming up with what intermediate useful claim to prove is really hard. It would be much more helpful if you spend the majority of time on the thinking process that leads you to come up with 2 most important claim in this problem: 1. How do you come up with the angle of power 2 of the two sides of the equality, and what makes you believe that turning an equlity into an inequality will help solve an algebra question before digging into the calculation (typically inequality is helpful for solving analysis problems)? 2. What makes you believe that the last claim holds for n >= 6 before proving it, what makes you tackle it through this angle? For instance if it were me, after checking a few small n where there is a solution, I would not guess that for larger n it will suddenly fail. These are the important insights. The algebra that you carried out, I think most people with decent math background can follow. But I am not sure how much we can learn from it. I hope I can learn insights, not just algebra derivation.
I would never have got that. Jumping in with n=6 wasn't elegant although the induction that followed was neat. Would love these problems to have solutions outside the 0-3 range. Rarely happens.
Hi Michael, your vids are really great - thanks a lot for it! I never tried those exam questions a lot, maybe because I thought they are untouchable for me. But - thanks to your explanations - step by step I realise that's not true. I also very much like your hand writing.
Great video! You should do this problem that I thought up a few days ago: If it exists, find the limit as n -> infinity of k sub n where k sub n is equal to the recursive equation of (sum from a=0 to n-1 of (k sub n-1)^a)^(1/n) where k sub 0 is defined as equalling 1.
I just found that the square root is the unique non-constant continuous solution over the positive real numbers, that was pretty interesting to do, thank you :)
Great problem and nice solution, but how does one get so good at seeing inequalities and applying them in a really smart and clever manner? Is it just a lot of exercise? Do you have any resources?
Sometimes it's the only thing you can do. If you're going to solve the problem, you need some kind of constraint on the variables to either solve for the explicitly or test cases or something, and you can always summon inequalities as one such constraint.
Seeing the GIF one would immediately think of inequalities, and the one in which we replace factorial terms with 2^n is kind of similar to the proof for the divergence of the harmonic mean.
Good evening! We have n factors for k!=(2^n-1)(2^n-2^1)(2^n-2^2)...(2^n-2^(n-1)) It is easy to see that 2^0||(2^n-1); 2|^1||(2^n-2^1); 2^2||(2^n-2^2)...2^(n-1)||(2^n-2^(n-1)) We have a AP. 2^a||k! ==> a=n(n-1)/2 By counting a= [k/2]+[k/4]+[k/8]+... < k/2+k/4+k/8+....(I)as [k/2^i]=0 kor i>= j where 2^j>k [x] means floor function of x. It is so likely that we have only trivial solutions. for n=1 1!=1 good n=2 3!=6 good n=3 k!= 168 As 5! = 120 and 6!= 720 it does not work. n=4 k!= 20.160 As 7!= 5040 and 8!=40.320 it does not work. By (i) we have that a < k so k>=a+1 as k,a are integers. Then k!>=(a+1)! We will prove by induction that for n>=5 (a+1)!>k! so we will have a contradiction k a+1=11 ==> (a=1)!=11!=39.916.800 so (a+1)!> k! If (a+1)1>k! for n let prove that (a+1)! > k! for n+1 k!=(2^n-1)(2^n-2^1)(2^n-2^2)...(2^n-2^(n-1)) for n k'!=(2^(n+1)-1)*2K! for n a+1=(n-1)n/2+1 and for n+1 a’+1=(n+1)n/2+1 As (a´+1)-(a+1)=n So (a’+1)!= (a’+1)*(a1)*...(a’-n+1)*(a+1)!>(a+2)^n*(a+1)!>12^n*(a+1)!>2^(n+2)k! >k’!=(2^(n+1)-1)*2k! Then (a+1)>k n>=5. And we Only have the solutions (k,n); (1,1); (3,2). I guess
Can't you just do it like this: (2^n - 2^(n-1)) = 2^(n-1) If k! has on odd factor then that odd factor must be when 2^n is odd or when term you're subtracting is odd. Since n>0 all 2^n > 1 and are therefore even. Therefore the term you're subtracting must be odd which is only true for the first term where you are subtracting 1, since all other subtracting terms are 2^m, m>0 If k! has an odd factor then that factor is 2^n - 1, and the only odd factor it could have must be the first odd factor, which is 3 --> 2^n - 1 = 3 --> n = 2 Therefore, if k! has an odd factor then k! = (2^2 - 1)(2^2 - 2) = 3 * 2 = 6 = 3! We can simply check for k! = 1, and k! = 2 which are the two remaining possibilities: If k! = 2: 2 = 2 * 1 --> 2^n - 1 = 1 or 2, but since 2^n -1 is odd then it must mean that 2^n - 1 = 1 and that n = 1, but that completely contradicts our given information since if n = 1 then we have k! = 1, but k! was 2 and 2 does not equal one, so therefore k! can't be equal to two. As stated before if n = 1 then we have k! = 1 which simply gives us another pair. The final pairs for (n,k) are; (1,1) and (2,3)
9:57 Should not be the inequality reversed? He substituted something bigger for the RHS, which was already bigger than the LHS, making it still greater than the LHS.
Please continue the Olympiad geometry problem sereis and please try to take geometry lectures also for preparation purpose,it will be very helpful.thank you😁
I have a slightly shorter answer which is not sufficiently rigid but I think it's worth posting anyways: 1.Suppose K! = m*(m-1)*(m-2)...*3*2*1 2. now 2^n-1 must equal m AND (2^n - 2^(n-1) = 2 OR 2^n - 2^(n-1) = 1) and when you solve m = 2^n-1 with 2^n - 2^(n-1) = 2 OR 2^n - 2^(n-1) = 1 you get that n = 1 or n = 2 P.S. - I love your videos! Thank you
I have a question : at 10:40 how can you be sure that the left term of the inequality isn't just between the middle and the right term when n is higher or equal to 6 ?
You really can't, the motivation is that is hard to work with the 2^n-2^a terms, so maybe you should try to work with 2^n because it is easier. With respect to how to know if n greater than 5 works, I think at moment you can't know, but it's something you prove and then when you explain it, it seems that you know that just because it's obvious, but no, you prove it before you explain it. At IMO, all the problems are like this, you work a lot with the problem and when you solve it you just explain the part that solves the problem.
Interestingly, if you ask the question how many RHS is multiple of a factorial, then the answer is (n-2) and they are all have gcd=6. Example for n=10, there are 8 RHS numbers multiple of a factorial [6, 168, 20160, 9999360, 20158709760, ...]. Actually any of the numbers in this set are divisible by multiple factorials. Example: 20160 is divisible by 3!, 4!, 5!, 6!, 7!
This has a nice geometric illustration: the RHS is the size of GL(n,2) (the group of invertible matrices over F_2, the field with 2 elements). This group acts (faithfully & transitively) on the space (F_2)^n and therefore GL(n,2) is isomorphic to a subgroup of S_{2^n-1}, the symmetric group with 2^n-1 elements that permutes all non-zero vectors in (F_2)^n. I _think_ a transitive subgroup of a symmetric group can never be isomorphic to a full symmetric group of lesser order (certainly not where 2^n-1 is prime, but it often isn't...). Assuming that, the question becomes: When is GL(n,2) isomorphic to S_{2^n-1}, i.e. *every* permutation of points representable by a linear transformation? So in other words, k=2^n-1. At this point, it is intuitively clear that the dimension n must not be too large: take the 2^(n-1) vertices of a face of the n-cube (imagine n=3 for illustration). If their position vectors are linearly dependent (they are iff n>2), a (2^(n-1)+1)-cyclic permutation of those points with another point not on the face will map the face to a non-planar image, i.e. the permutation was not linear. With the example of n=3, this explains geometrically why 5 = 2^2+1 does not divide the RHS.
This was the first IMO problem I solved successfully while being in high school. But I used Bertrand-Chebyshev's theorem instead. It took a little bit more analysis that way....
picking six is actually super interesting, because 6 is 1+2+3 which is equal to 1*2*3 = 3! and this does not hold for any number greater than 6. If the inequality was just 1+2+...+n < n! then it won't hold for n greater than 6.
Is there a solution usin the fact that (2^n-1)(2^n-2)...(2^n-2^(n-1)) = |GLn(Z/2Z)| ? That's the first thing that came to my mind (but I'm not used at all of solving this type of problems, so maybe it's a bad idea)
Here's one that the German national mathematic competition had (tho I don't know the year), it's rumored to be the hardest question they ever did: Let a(n) be a recursive sequence where a(0)=0, a(n)=n-a(a(n-1)). Find an explicit representation of this sequence.
I wrote a python program that convinced me that the number of times 2 divides the RHS is the n:th triangular number. That's as far as I got. :D pastebin.com/evDinQe6
2^n - 2^(n-1) = 2^(n-1), so I simply thought 2^(n-1) should be 1 or 2, since k! = k*(k-1)*...*3*2*1, although I could not prove there is no other solution... :)
Was this question a part of the "overkill series"? k! is obviously a multiple of 5 for k>4, while the RHS is never a multiple of 5; therefore, we only need to check for k
I'd say you are mistaken - the odd part of the RHS contains factors of the form *a_i := 2^i - 1* . Make a small table of the first few values of *a_i mod 5* : *i >= 0: a_i = (0; 1; 3; 2; 0; ...) mod 5* Notice for every *i = 0 mod 4* the factor *a_i* is divisible by *5* , so the RHS eventually contains arbitrary powers of *5* ! *Rem.:* You could also use _Fermat's Little Theorem_ or _Euler's Theorem_ to get that info^^
Can u make a series of tutorials(explaining theory)for olympiad preparation pls?(it would have huge number of views as hardly no one does it and there is a huge demand for it)
i solve this problem with different ways , correct me if i am wrong,, K! = (2^n - 1)(2^n -2)........(2^n - 2^n-1) That means K! = 2*(2^2)*(2^3).....(2^n-1)*(2^n -1)....(2^2 -1)(2 - 1) We know that impossible 2^x -1 = 5 for all natural number x , But for k>4, k! Must be divisible by 5 , so imposible for k>4 By trial for k= 1 ,2 , 3, and 4 We can get (k,n) = (1,1); ( 3,2)
I'd say you are mistaken - as you say, the odd part of the RHS contains factors of the form *a_x := 2^x - 1* with *x in N* . Make a small table of the first few values of *a_x mod 5* : *x >= 1: a_x = (1; 3; 2; 0; 1; ...) mod 5* Notice for every " *x = 0 mod 4* " the factor *a_x* is divisible by *5* , so the RHS eventually contains arbitrary powers of *5* !
This is a very natutal-feeling solution, the kind you would come across on the test. I'd be interested to see some ultrawoke Papa Flammy-esque Gamma function solution here though.
I did come up with the right answer but I'm not sure if my proof is "rigorous" enough. Started up just the same way, that is k!= (2-1)(4-1)(8-1)....*2^(n*(n-1)/2) which can be rewrote as k!=1*3*7*....*2^(n*(n-1)/2) Now, for k! to hold, the term 2^(n*(n-1)/2) must "fill in the gaps", but since it's a power of two it will never be able to be equal to a multiple of five to fill in the gap from 3 to 7 i.e. k! can't be bigger than k!=1*2*3*4. For that to be true we have that 2^(n*(n-1)/2) must be equal to 2^3 which ends up as n=3. if we solve all cases up to n=3 we have that for n=1 k!=1! for n=2 k!=3! but for n=3 k!≠5! therefore the only solutions are k=1,3
That argument doesn't work, as the odd factors are not all prime and could, potentially, fill the gaps. Consider the n=4 case. Once you pull out the ten factors of 2 you're left with 1*3*7*15. Or, in other words, the remaining prime factors are a 7, a 5, and two 3s. But, these are exactly the odd prime factors of 7! and 8!. The n=4 case fails because it has too many factors of 2 to be either of these, not because of the lack of a 5.
I would like to suggest an easier solution. The reduced RHS side can be used to deduce that we can't have a factor of 5. Hence k has to be less than 5 and there are only four possible values to check for
By guessing f(x)=cx^a, we see that c=1/2, a=1 works. Now let g(x) = f(x) - x/2. Then the integral of xg(x) is 0 and the integral of g(x)^2 + xg(x) is 0, so the integral of g(x)^2 is 0. If f is continuous, this implies g is, hence g=0 and f(1/2) = 1/4. But if we do not assume f is continuous, then we can let f(x)=x/2 for x≠1/2 and f(1/2)=a for any a, so there is no answer.
"obvious": right side is 2^something * (2^1-1)*(2^2-1)*(2^3-1)*(2^4-1)*... Since 5 is not 2^x-1, the factorial cannot go up to 5. So you only have to consider factorials up to 4!. After that I am not wondering what the solution is. I am wondering why this is on the International Olympiads. I guess it helps to just "know" that 2^x-1 is 11111.... in binary (all 1's). And 5 isn't.
That expression counts the number of invertible n×n matrices over the finite field with 2 elements (or by thinking about the columns of such a square matrix, it counts the number of bases of n-dimensional space over the finite field with 2 elements), i.e. |GL(n, 𝔽₂)|
manipulating the product I arrived at (2^n -1)*prod(i=1 to n-1 of (2^i)*(2^i -1)) and then I notice that you can't get 5 from it, so in particular it can't be a factorial for some k>=5. Furthermore even if 2^i-1 is divisible by 5 for some i, for the whole product to be a factorial of something, you should be able to reduce this number to 1 by dividing it by every number after until certain point, in particular until 2^i-1, but if you do that you can't reduce it by 5 and 2^i-1 and the same time. This reduce the search of n to just 1-3, and those can be check by hand.
@@igml1145 I don't know how to explain it that well, but I'm looking at how it is constructed, the size of the number, how that compare to factorials, and noticing that there are odd number that do not appear by construction, and thus as you extract factor from it you will never get to 1
So for the Olympiad, would a valid answer have to show everything you did or an equivalent to prove the answer, or is it just satisfactory to find the solutions? In other words, how rigorous of a solution would they want?
I happen to know!! I was at the IMO 1985, check my record@ imo-official dot org (my name is real). I scored 6 of 7 possible points for a question there, because I failed to mention some self-explanatory silly detail. And I missed the medal by 1 point because of that. Well, they're strict I'd say. Unless they changed policy in the last 35 years, dunno :-)
Suppose you have a coin that has 1 and 2 on its faces seperately. You are standing on the point 0 on the number line and the numbers on the coin tells how much point you have to move after you flip the coin . For example if you got 1 you have to move 1 point if you got 2 you have to move 2 point (positive direction). p_n: probability of reaching n where n is a natural number. Find p_n.
I assume you have a fair coin, but the same method will give an expression when the coin is not fair. Just notice that you have p_0 = 1, p_1 = 1/2 and in general, if you condition on the last step before getting to n you obtain the following recursion: p_n = 1/2 p_{n-1} + 1/2 p_{n-2}. Then, it is just a matter of solving this recursion by your favorite method (generating functions, characteristic polynomial, you should check the wikipedia page on recurrence relations). The solution turns out to be p_n = 1/3 *(2 + (-1/2)^n)
More than fields of math, there are specific, math 'elements' and techniques to be familiar with. You'd need: - a mathematics background roughly equivalent to 9th-10th grade level, including basic mathematical logic - a good grasp of what a 'mathematical proof' is, with specific focus on 'proof by contradiction', and 'proof by induction', - the arithmetic of powers, - the definition and arithmetic of factorials, - a basic grasp of what prime numbers are, - the fundamental theorem of arithmetic, stating that any natural number has a unique factorization to primes. There is a considerable distance between being familiar with the above, and acknowledging the exact combining of those elements, in that manner, when you see such a question in real time. The 'hints' given at the beginning are some intuition/experience gathered by solving many of these questions, keeping in mind that different such questions obviously require familiarity with many additional math elements.
There is one trivial solution to this question: product from i=0 to i=n-1 (2^n-2^i) has >exactly one odd< number, not and we can always multiply by 1, so k < 5, because k! would have two odd numbers excluding 1. So we just can check manually for k = {1,2,3,4}
Me: *Ends a final algebraic topology test*
Me: Enough maths for today!
Michael Penn: *Uploads a new video*
And here we are
What a great explanation you gave. I would love to see more contest math question, like IMO, AMC etc ! Keep it up !
At 6:15 Can someone explains how he can just not take care of the terms in brackets for the equality ? I understand that it is important to prove that the Power of twos are equal, but for the equality to hold you can't juste skip the terms in brackets, non ? I would really appreciate an enlightement.
@@phinix4912 its just the inequality. He can. He didnt skip any step
@@phinix4912 The G.I.F of K/2^m will always be less than the actual value as we take the nearest integer that is *less* than the value hence the product of lesser values will be lesser , thats what he meant
Never expected to find you here :v and why am I late to the party
@@factsverse9957 :)
I think when 2020 came this guy just said "This is a good place to stop"
I was just confused: I thought the question meant: (2^n -1)(2^n-2)(2^n-3)... while it seems that it meant: : (2^n -1)(2^n-2)(2^n-4)...
Same here, even though there is a simpler solution for this case (as if k is even then k! is divided by 2, (k/2)(k/2 - 1) / 2 times, and the RHS is divided by 2 exaclty 2^(n-2) times, so k/2 has to be no more than 2 (otherwise, k/2 or k/2 - 1 will be odd and this equality wont hold for sure) and then its easy to check for all k up to 5 (since 5/2 = 2 in integer division) )
Not sure why he shortened the formula making the pattern unclear, in the actual competition the third term (2^n-4) was written disambiguating the formula.
Yeah, that's what I thought at first. Made the problem a lot harder.
Me too, till the last part when I saw what he was doing.
Hi Michael, I am a viewer from China and I would like to suggest a problem, taken from the 2008 National College Entrance Exam (NCEE). This is the last question (hardest) on the exam. It is said that 99.9% of the students got a score of 0, and only 3 students (out of 300,000 who took this version of math exam) scored above 50% on this question with 9 out of 14 being the highest. This question was criticized for being too difficult. Many math professors said that this question should be given to a math competition, not the NCEE, which is designed for regular grade 12 students applying for colleges.
Here’s the questions:
f(x) = 1/sqrt(1+x) + 1/sqrt(1+a) + sqrt[ax/(ax+8)], x is a positive real number
Prove that, for any positive real number a, 1 < f(x) < 2
Ohh! The problem-setter gained widespread notoriety due to that problem as well as the difficulty of the entire exam. Also, even outside China, the NCEE is more widely known as the Gaokao.
I don’t know if I’m not rigorous enough but can’t we prove that it’s a monotonically decreasing function and since it’s a positive real number the bounds for x is 0 to infinity. Then evaluate the function at 0 and infinity by taking limits. At 0 it would be 2 and at infinity 1. So proved? Idk
The function is increasing at very small values of x. Also the maximum approaches 2 as A goes to infinity.
@@lucas29476 the question seems too easy unless there was other things i didn't see. Proposing this to imo will be terrible idea. Students may fail due to pressure and timing.
@@dcmst2011 you are fast. I wonder if the guy really gave us the right problem question. Because this is terribly easy.
Awesome! Maybe need to emphasize a little bit when you pull out all the factors of 2, the remaining factor is odd.
Halo pak
Yes, it's the product of a whole load of odd numbers.
BMO2 2011 P2 is nice
If you do geometry I'd recommend BMO2 2019 P1 or IMO 2007 P1/4 (can't remember which one is the geo)
Also the first 3 from BMO2 1995 or BMO2 2001 and 2003 P1 are nice
Loving the videos btw I'm working towards making IMO next year and this is helpful
Without the third term, the question is ambiguous in that, it could be interpreted the RHS as (2^n -1)(2^n -2)(2^n -3)...(2^n -2^n-1)
Yeah that's exactly how I interpreted it. Hope the original problem statement actually contained the third term to clear this up
Well done. Many of these competition math problems are so elementary, but they require a creative sight.
Thank you.
Carzy induction proof, love it.
Thanks for the neat explanation! Do you plan to do some sessions on combinatorial problems? really appreciate it!
Great work, but then everyone always forgets about 0!=1
but 0 did not belong to the set of Natural number (N)
please try this geometry question here:
take a trapezoid of sides and height being integers. Prove that the perimeter of this trapezoid is even and its area is integer
area is easy and for the perimeter part just analyse different cases
Oh, that's from Olimpíada Cearense de Matemática, isn't it? If I recall correctly, thinking about the how the sides' parities relate should be enough. Not sure though.
The bulk of the problem is just showing two lengths are integers. Then everything follows from there.
Seems like shooting a fly with a rifle. If we consider all the possible factors of Π (2^n - 2^(n-i)) we can just take out the powers of two and notice that the only possible odd numbers in our factorization must be one less than a power of 2. Since 5 is the first odd number which is not a power of 2, and all k! for k ≥ 5 must contain a factor of 5, the only possible solutions are for k less or eqaul to 4.
Thank you very much for the very good and clear explanation solution!
Following your proof is not hard, but coming up with what intermediate useful claim to prove is really hard. It would be much more helpful if you spend the majority of time on the thinking process that leads you to come up with 2 most important claim in this problem: 1. How do you come up with the angle of power 2 of the two sides of the equality, and what makes you believe that turning an equlity into an inequality will help solve an algebra question before digging into the calculation (typically inequality is helpful for solving analysis problems)? 2. What makes you believe that the last claim holds for n >= 6 before proving it, what makes you tackle it through this angle? For instance if it were me, after checking a few small n where there is a solution, I would not guess that for larger n it will suddenly fail. These are the important insights. The algebra that you carried out, I think most people with decent math background can follow. But I am not sure how much we can learn from it. I hope I can learn insights, not just algebra derivation.
3:37 here you can notice that all the 2^n-1 factors are never divisible by 6 so you can try for all n and k < 6.
I would never have got that.
Jumping in with n=6 wasn't elegant although the induction that followed was neat.
Would love these problems to have solutions outside the 0-3 range. Rarely happens.
Hi Michael, your vids are really great - thanks a lot for it! I never tried those exam questions a lot, maybe because I thought they are untouchable for me. But - thanks to your explanations - step by step I realise that's not true.
I also very much like your hand writing.
Please do IMO 2006 problem 5. And Thx for your great work
You are the best teacher who teaches big things in such a simple way. Keep it up Sir!
Greetings From India
Great video! You should do this problem that I thought up a few days ago: If it exists, find the limit as n -> infinity of k sub n where k sub n is equal to the recursive equation of (sum from a=0 to n-1 of (k sub n-1)^a)^(1/n) where k sub 0 is defined as equalling 1.
I just found that the square root is the unique non-constant continuous solution over the positive real numbers, that was pretty interesting to do, thank you :)
Great problem and nice solution, but how does one get so good at seeing inequalities and applying them in a really smart and clever manner? Is it just a lot of exercise? Do you have any resources?
Sometimes it's the only thing you can do. If you're going to solve the problem, you need some kind of constraint on the variables to either solve for the explicitly or test cases or something, and you can always summon inequalities as one such constraint.
Seeing the GIF one would immediately think of inequalities, and the one in which we replace factorial terms with 2^n is kind of similar to the proof for the divergence of the harmonic mean.
Since 0!=1, (n=1,k=0) would also be a solution, right?
0 isnt a natural number
My guess is there ought to be a simpler solution than this one.
It becomes quite simple if u bound it with v_2 and v_3
Good evening!
We have n factors for k!=(2^n-1)(2^n-2^1)(2^n-2^2)...(2^n-2^(n-1))
It is easy to see that 2^0||(2^n-1); 2|^1||(2^n-2^1); 2^2||(2^n-2^2)...2^(n-1)||(2^n-2^(n-1))
We have a AP. 2^a||k! ==> a=n(n-1)/2
By counting a= [k/2]+[k/4]+[k/8]+... < k/2+k/4+k/8+....(I)as [k/2^i]=0 kor i>= j where 2^j>k
[x] means floor function of x.
It is so likely that we have only trivial solutions.
for n=1 1!=1 good
n=2 3!=6 good
n=3 k!= 168 As 5! = 120 and 6!= 720 it does not work.
n=4 k!= 20.160 As 7!= 5040 and 8!=40.320 it does not work.
By (i) we have that a < k so k>=a+1 as k,a are integers. Then k!>=(a+1)!
We will prove by induction that for n>=5 (a+1)!>k! so we will have a contradiction k a+1=11 ==> (a=1)!=11!=39.916.800
so (a+1)!> k!
If (a+1)1>k! for n let prove that (a+1)! > k! for n+1
k!=(2^n-1)(2^n-2^1)(2^n-2^2)...(2^n-2^(n-1)) for n
k'!=(2^(n+1)-1)*2K!
for n a+1=(n-1)n/2+1 and for n+1 a’+1=(n+1)n/2+1
As (a´+1)-(a+1)=n
So (a’+1)!= (a’+1)*(a1)*...(a’-n+1)*(a+1)!>(a+2)^n*(a+1)!>12^n*(a+1)!>2^(n+2)k! >k’!=(2^(n+1)-1)*2k!
Then (a+1)>k n>=5. And we Only have the solutions (k,n); (1,1); (3,2).
I guess
Can't you just do it like this:
(2^n - 2^(n-1)) = 2^(n-1)
If k! has on odd factor then that odd factor must be when 2^n is odd or when term you're subtracting is odd. Since n>0 all 2^n > 1 and are therefore even.
Therefore the term you're subtracting must be odd which is only true for the first term where you are subtracting 1, since all other subtracting terms are 2^m, m>0
If k! has an odd factor then that factor is 2^n - 1, and the only odd factor it could have must be the first odd factor, which is 3 --> 2^n - 1 = 3 --> n = 2
Therefore, if k! has an odd factor then k! = (2^2 - 1)(2^2 - 2) = 3 * 2 = 6 = 3!
We can simply check for k! = 1, and k! = 2 which are the two remaining possibilities:
If k! = 2: 2 = 2 * 1 --> 2^n - 1 = 1 or 2, but since 2^n -1 is odd then it must mean that 2^n - 1 = 1 and that n = 1, but that completely contradicts our given information since
if n = 1 then we have k! = 1, but k! was 2 and 2 does not equal one, so therefore k! can't be equal to two.
As stated before if n = 1 then we have k! = 1 which simply gives us another pair.
The final pairs for (n,k) are; (1,1) and (2,3)
9:57 Should not be the inequality reversed? He substituted something bigger for the RHS, which was already bigger than the LHS, making it still greater than the LHS.
What about 5 never divides RHS so you only have to check k = 1,2,3,4? Valid solution?
I quess there is also the solution (1,0)
If 0 were a natural number probably yes but thats not true
me who got the answer by manually substituting natural numbers in k and n and giving up past 4:
If you're french then n=1, k=0 is also a solution 😅
Great , don't ever use a blackboard ! Seriously , it's cooler with a chalk
If c=0 and b=2 any a works.... Wasn't that missed in the response ?
I really do not know if my solution is right. But I thougut a lot of things like the master. I am happy!
Please continue the Olympiad geometry problem sereis and please try to take geometry lectures also for preparation purpose,it will be very helpful.thank you😁
import math
for k in range(1, 1000):
for n in range(1, 1000):
z=1
for m in range(0, n):
x = (pow(2,n) - pow(2,m))
z = z*x
if (math.factorial(k) == z):
print(k,n)
*Python code*
Nice
4.46 what does [k/2] means
the starting question was unclear. Next time please write an extra term in the "dot dot dot"
Thank you, this is a nice problem.
Thank you for these videos professor.
This is so beautiful solution.Thank you so much.I'm from Uzbekistan
I have a slightly shorter answer which is not sufficiently rigid but I think it's worth posting anyways:
1.Suppose K! = m*(m-1)*(m-2)...*3*2*1
2. now 2^n-1 must equal m AND (2^n - 2^(n-1) = 2 OR 2^n - 2^(n-1) = 1)
and when you solve m = 2^n-1 with 2^n - 2^(n-1) = 2 OR 2^n - 2^(n-1) = 1 you get that n = 1 or n = 2
P.S. - I love your videos! Thank you
this was way to easy for IMO.
I have a question : at 10:40 how can you be sure that the left term of the inequality isn't just between the middle and the right term when n is higher or equal to 6 ?
You really can't, the motivation is that is hard to work with the 2^n-2^a terms, so maybe you should try to work with 2^n because it is easier.
With respect to how to know if n greater than 5 works, I think at moment you can't know, but it's something you prove and then when you explain it, it seems that you know that just because it's obvious, but no, you prove it before you explain it. At IMO, all the problems are like this, you work a lot with the problem and when you solve it you just explain the part that solves the problem.
@@brunogutierrezchavez1989 Thanks a lot !
Interestingly, if you ask the question how many RHS is multiple of a factorial, then the answer is (n-2) and they are all have gcd=6. Example for n=10, there are 8 RHS numbers multiple of a factorial [6, 168, 20160, 9999360, 20158709760, ...]. Actually any of the numbers in this set are divisible by multiple factorials. Example: 20160 is divisible by 3!, 4!, 5!, 6!, 7!
This has a nice geometric illustration: the RHS is the size of GL(n,2) (the group of invertible matrices over F_2, the field with 2 elements). This group acts (faithfully & transitively) on the space (F_2)^n and therefore GL(n,2) is isomorphic to a subgroup of S_{2^n-1}, the symmetric group with 2^n-1 elements that permutes all non-zero vectors in (F_2)^n. I _think_ a transitive subgroup of a symmetric group can never be isomorphic to a full symmetric group of lesser order (certainly not where 2^n-1 is prime, but it often isn't...). Assuming that, the question becomes: When is GL(n,2) isomorphic to S_{2^n-1}, i.e. *every* permutation of points representable by a linear transformation? So in other words, k=2^n-1. At this point, it is intuitively clear that the dimension n must not be too large: take the 2^(n-1) vertices of a face of the n-cube (imagine n=3 for illustration). If their position vectors are linearly dependent (they are iff n>2), a (2^(n-1)+1)-cyclic permutation of those points with another point not on the face will map the face to a non-planar image, i.e. the permutation was not linear. With the example of n=3, this explains geometrically why 5 = 2^2+1 does not divide the RHS.
This was the first IMO problem I solved successfully while being in high school. But I used Bertrand-Chebyshev's theorem instead. It took a little bit more analysis that way....
Problem:
Find all positive integers m and n bigger than 1 such that
1!3!5!...(2n-1)!=m!
Thanks !
picking six is actually super interesting, because 6 is 1+2+3 which is equal to 1*2*3 = 3! and this does not hold for any number greater than 6. If the inequality was just 1+2+...+n < n! then it won't hold for n greater than 6.
2:50 shouldn’t that be 2^(0+1+2+3+...+n-1)
I know that’s the same solution but it explains how you were able to bring ([2^n) -1], 1st term. Into play
one could count the powers of three to get that nn(n-1)/2 -> 4k > 2(n-1)*n
so 3> 2*(n-1) hence n
But there is stronger inequality that if n>=5 the inequality won't hold. Because with n=5 (n^2-n+2)/2 > 8 as well.
Is there a solution usin the fact that (2^n-1)(2^n-2)...(2^n-2^(n-1)) = |GLn(Z/2Z)| ? That's the first thing that came to my mind (but I'm not used at all of solving this type of problems, so maybe it's a bad idea)
imo, 2012, number 6
Can you show that the only solution of p^p+2=q , where p and q are primes is p=3 and q= 29 ?
Here's one that the German national mathematic competition had (tho I don't know the year), it's rumored to be the hardest question they ever did: Let a(n) be a recursive sequence where a(0)=0, a(n)=n-a(a(n-1)). Find an explicit representation of this sequence.
Is there any python code to solve this
I'm trying this.. just for fun guys😅😅😅
@Bigblrman75 Surya evara ella prashnegalu chennagiruttave.. explanation kooda sakkathagi madthare😁😁
I wrote a python program that convinced me that the number of times 2 divides the RHS is the n:th triangular number. That's as far as I got. :D pastebin.com/evDinQe6
@@emanuellandeholm5657 cool brother.. I also got that.. my code is as follows
import math
for k in range(1, 1000):
for n in range(1, 1000):
z=1
for m in range(0, n):
x = (pow(2,n) - pow(2,m))
z = z*x
if (math.factorial(k) == z):
print(k,n)
Your codes don't seem to prove that no n>6 can be a solution. Without that, even if your loop runs to a trillion, it is very hardly a solution
@@podir47 That's what even I'm trying to optimize.. thanks for the feedbaclk
2^n - 2^(n-1) = 2^(n-1), so I simply thought 2^(n-1) should be 1 or 2, since k! = k*(k-1)*...*3*2*1, although I could not prove there is no other solution... :)
Floor(x/10)=floor(x/11)+1. The positive solns of the equation. Its a good problem
Like you proceed with inequality for your work through at around 6:49. Seems to be a similar problem from last time
fuck off ur videos are good af
Can u plz solve 2016 IMO, problem 4.
I suggest the legendary question 6. Of an old mathematics Olympics.
Was this question a part of the "overkill series"? k! is obviously a multiple of 5 for k>4, while the RHS is never a multiple of 5; therefore, we only need to check for k
I'd say you are mistaken - the odd part of the RHS contains factors of the form *a_i := 2^i - 1* . Make a small table of the first few values of *a_i mod 5* :
*i >= 0: a_i = (0; 1; 3; 2; 0; ...) mod 5*
Notice for every *i = 0 mod 4* the factor *a_i* is divisible by *5* , so the RHS eventually contains arbitrary powers of *5* !
*Rem.:* You could also use _Fermat's Little Theorem_ or _Euler's Theorem_ to get that info^^
I don't understand how I made that mistake! 16 - 1 =15 is an obvious counter example!
Can u make a series of tutorials(explaining theory)for olympiad preparation pls?(it would have huge number of views as hardly no one does it and there is a huge demand for it)
i solve this problem with different ways , correct me if i am wrong,,
K! = (2^n - 1)(2^n -2)........(2^n - 2^n-1)
That means
K! = 2*(2^2)*(2^3).....(2^n-1)*(2^n -1)....(2^2 -1)(2 - 1)
We know that impossible 2^x -1 = 5 for all natural number x ,
But for k>4, k! Must be divisible by 5 , so imposible for k>4
By trial for k= 1 ,2 , 3, and 4
We can get
(k,n) = (1,1); ( 3,2)
I'd say you are mistaken - as you say, the odd part of the RHS contains factors of the form *a_x := 2^x - 1* with *x in N* . Make a small table of the first few values of *a_x mod 5* :
*x >= 1: a_x = (1; 3; 2; 0; 1; ...) mod 5*
Notice for every " *x = 0 mod 4* " the factor *a_x* is divisible by *5* , so the RHS eventually contains arbitrary powers of *5* !
You're right,,, I didn't realize that point,,
Thanks for correcting me,,
@@Merhu657 You are welcome! I noticed a lot of people made the same mistake in the comment section^^
integral from 1 to infinity of f(x) = sum from 1 to infinity of f(x)
Can you do a video about the burnside’s lemma and possibly its applications to olympiad math?
This is a very natutal-feeling solution, the kind you would come across on the test. I'd be interested to see some ultrawoke Papa Flammy-esque Gamma function solution here though.
I did come up with the right answer but I'm not sure if my proof is "rigorous" enough.
Started up just the same way, that is k!= (2-1)(4-1)(8-1)....*2^(n*(n-1)/2)
which can be rewrote as
k!=1*3*7*....*2^(n*(n-1)/2)
Now, for k! to hold, the term 2^(n*(n-1)/2) must "fill in the gaps", but since it's a power of two it will never be able to be equal to a multiple of five to fill in the gap from 3 to 7 i.e. k! can't be bigger than k!=1*2*3*4.
For that to be true we have that 2^(n*(n-1)/2) must be equal to 2^3 which ends up as n=3.
if we solve all cases up to n=3 we have that
for n=1 k!=1!
for n=2 k!=3!
but for n=3 k!≠5!
therefore the only solutions are k=1,3
That argument doesn't work, as the odd factors are not all prime and could, potentially, fill the gaps. Consider the n=4 case. Once you pull out the ten factors of 2 you're left with 1*3*7*15. Or, in other words, the remaining prime factors are a 7, a 5, and two 3s. But, these are exactly the odd prime factors of 7! and 8!. The n=4 case fails because it has too many factors of 2 to be either of these, not because of the lack of a 5.
I'm sure a plenty of us are waiting for that "JOIN" button... Keep up the good work!!
loose inequality, I like how many potential options that gives
Thank you so much. I find this solutions of problem.
I would like to suggest an easier solution. The reduced RHS side can be used to deduce that we can't have a factor of 5. Hence k has to be less than 5 and there are only four possible values to check for
For n=6 there is 15 (2^5 - 1) which is factor of 5
Sir i have a question:
If integral from limit 0 to 1 of xf(x) is 1/6
and integral from limit 0 to 1 of [f(x)]^2 is 1/12 .Then we have to find f(1/2)=?
By guessing f(x)=cx^a, we see that c=1/2, a=1 works. Now let g(x) = f(x) - x/2. Then the integral of xg(x) is 0 and the integral of g(x)^2 + xg(x) is 0, so the integral of g(x)^2 is 0. If f is continuous, this implies g is, hence g=0 and f(1/2) = 1/4. But if we do not assume f is continuous, then we can let f(x)=x/2 for x≠1/2 and f(1/2)=a for any a, so there is no answer.
for a prime p, n! has p as a factor if and only if n >= p. So 7 * 6 * 4
Are you mad
"obvious": right side is 2^something * (2^1-1)*(2^2-1)*(2^3-1)*(2^4-1)*... Since 5 is not 2^x-1, the factorial cannot go up to 5. So you only have to consider factorials up to 4!. After that I am not wondering what the solution is. I am wondering why this is on the International Olympiads. I guess it helps to just "know" that 2^x-1 is 11111.... in binary (all 1's). And 5 isn't.
5 divides 2⁴-1, so this will take a bit more work.
@@andrewkepert923 aha! there it is. now it's a problem.
Could anyone have solved this problem at the Olympics?
www.imo-official.org/year_individual_r.aspx?year=2019
Clear and Concise. Salute!
Seeing this expression in the thumbnail made me think about counting the number of vector subspaces of a 2^n-dimensional vector space
I mean it’s not exactly the same but I can’t help the PTSD
That expression counts the number of invertible n×n matrices over the finite field with 2 elements (or by thinking about the columns of such a square matrix, it counts the number of bases of n-dimensional space over the finite field with 2 elements), i.e. |GL(n, 𝔽₂)|
manipulating the product I arrived at (2^n -1)*prod(i=1 to n-1 of (2^i)*(2^i -1)) and then I notice that you can't get 5 from it, so in particular it can't be a factorial for some k>=5.
Furthermore even if 2^i-1 is divisible by 5 for some i, for the whole product to be a factorial of something, you should be able to reduce this number to 1 by dividing it by every number after until certain point, in particular until 2^i-1, but if you do that you can't reduce it by 5 and 2^i-1 and the same time.
This reduce the search of n to just 1-3, and those can be check by hand.
You dont need 2^i-1 to be exactly 5, you need it to be divisible by 5... for example u get a factor of 5 from 2^4-1=15. This problem is not THAT easy
@@igml1145 I don't know how to explain it that well, but I'm looking at how it is constructed, the size of the number, how that compare to factorials, and noticing that there are odd number that do not appear by construction, and thus as you extract factor from it you will never get to 1
This is magic of mathematics
Good
so good... keep it up¡¡¡¡
What an awesome beauty
You forgot the solution (1,0)
Is zero a natural number?
Yes
@@angelmendez-rivera351 and (0,1) as well! :P
Although I definitely grew up with 0 being a "whole number" rather than a "natural number"
cool!
So for the Olympiad, would a valid answer have to show everything you did or an equivalent to prove the answer, or is it just satisfactory to find the solutions? In other words, how rigorous of a solution would they want?
I happen to know!! I was at the IMO 1985, check my record@ imo-official dot org (my name is real). I scored 6 of 7 possible points for a question there, because I failed to mention some self-explanatory silly detail. And I missed the medal by 1 point because of that. Well, they're strict I'd say. Unless they changed policy in the last 35 years, dunno :-)
Proof is required.
Yes and I sympathise, @Raz - in 1983q5 I made an inconsequential error in calculating 3¹⁰. So 6/7.
great video!
Крутое решение, моё почтение
Suppose you have a coin that has 1 and 2 on its faces seperately. You are standing on the point 0 on the number line and the numbers on the coin tells how much point you have to move after you flip the coin . For example if you got 1 you have to move 1 point if you got 2 you have to move 2 point (positive direction). p_n: probability of reaching n where n is a natural number. Find p_n.
Probability of reaching n after how many tosses?
I assume you have a fair coin, but the same method will give an expression when the coin is not fair. Just notice that you have p_0 = 1, p_1 = 1/2 and in general, if you condition on the last step before getting to n you obtain the following recursion: p_n = 1/2 p_{n-1} + 1/2 p_{n-2}. Then, it is just a matter of solving this recursion by your favorite method (generating functions, characteristic polynomial, you should check the wikipedia page on recurrence relations). The solution turns out to be p_n = 1/3 *(2 + (-1/2)^n)
@@danielungaretti4468 coin is fair and thanks for your solution
@@Ooopsi yeah i guess
second
IMO 2012 P5
Can someone clarify the fields of math you must know to be able to properly solve this?
we are just comparing the number of certain prime factors in these two numbers in this case we choose 2
Some basics of number theory
Look up titu andreescu diophantine equations book, it got tricks involving inequalities etc
More than fields of math, there are specific, math 'elements' and techniques to be familiar with. You'd need:
- a mathematics background roughly equivalent to 9th-10th grade level, including basic mathematical logic
- a good grasp of what a 'mathematical proof' is, with specific focus on 'proof by contradiction', and 'proof by induction',
- the arithmetic of powers,
- the definition and arithmetic of factorials,
- a basic grasp of what prime numbers are,
- the fundamental theorem of arithmetic, stating that any natural number has a unique factorization to primes.
There is a considerable distance between being familiar with the above, and acknowledging the exact combining of those elements, in that manner, when you see such a question in real time. The 'hints' given at the beginning are some intuition/experience gathered by solving many of these questions, keeping in mind that different such questions obviously require familiarity with many additional math elements.
There is actually a third solution: n=1, k=0.
But k is natural number?
@@petrusdeonpranoto4456 indeed. en.m.wikipedia.org/wiki/Natural_number. Natural numbers usually start from 0 in mathematics
There is one trivial solution to this question:
product from i=0 to i=n-1 (2^n-2^i)
has >exactly one odd< number, not and we can always multiply by 1, so k < 5, because k! would have two odd numbers excluding 1.
So we just can check manually for k = {1,2,3,4}
You forgot n=1 k=0.
We're looking for natural k
@@36sufchan 0 is natural.
@@angelmendez-rivera351 Oh wow, I forgot n=0.