10:47 I think we used the hypothesis when we multiplied 2*(n/2), because for that to be true, we need both 2 and (n/2) in the product, and for that, we need n/2 to be different than 2, since they come from the factorial, and therefore n>4, which implies n\geq 5.
@Adam Romanov You can find the pdf of it online, I got a pdf from a website fadjarp3g, plug in SMO Round 2 2008 fadjarp3g in the Google search bar and I think you should find it, hope this helps
I wasn't aware of Wilson's Theorem, but it's not too hard to see that n+1 has to be a prime in this problem, this is the easy part of Wilson's Theorem. If n+1 has a factor, which is smaller than it, then it appears in n! as well as (n+1)^k, so the two can not be just 1 apart (they are not coprime)
First thing I thought when I saw the thumbnail: "Hey, that looks like Wilson's Theorem! . . Oh wait, not quite." Wilson's Theorem says that p | [(p-1)! + 1], iff p is prime. Here we would make n = p-1 and this becomes (n+1) | (n! + 1), iff (n+1) is prime; vs our problem: (n+1)ᵏ = n! + 1 which is a stronger condition on (n! + 1) than mere divisibility by (n+1). k & n are restricted to the +ve integers, so start with k=1: N+1 - 1 - n = n! Works for n = 1 and 2; no others. Solutions: (n,k) = (1,1), (2,1) k=2: n! + 1 will have to be a square. I think the only cases of that are n = 4, 5, and 7. n = 4 works for this equation; 5 and 7 do not: 4! + 1 = 25 = 5² 5! + 1 = 121 = 11² 7! + 1 = 5041 = 71² So: (4+1)² - 1 = 4! . . 24 = 24 Solution: (n,k) = (4,2) I suspect there are no others, but I don't see a way to prove that. Let's see what Michael has... ... Very nicely done! So my suspicion was borne out. Thanks to Michael for the proof. Fred
If it isn't too much of a hastle can you please put the video link in the description for theorems you used and proved in another video (like wilsons theorem here)
You don"t need Wilson Theorem. (n+1)^k = n! + 1 n! + 1 is odd for n > 1, then n + 1 must be odd, then n must be even. (we don't need n + 1 prime, just the fact n is even to get k = 0[n])
Vp(x!) >= 2*Vp(x) for all non prime x such that x> 4, then you can see that if n>4 and it is not prime( which is the case for n >4) k would have to be at least n, but (n + 1)^n - 1 > n! for n > 4. This is just an alternative solution:)
n=1,2 imply k=1. Now for n>2 we must have n+1=p is a prime, otherwise n+1 would have a proper divisor 1 < d =< (n+1)/2 < n which yields a contradiction modulo d: 0=n!=(n+1)^k-1=-1 and hence we can rewrite p^k-1=(p-1)! with p>=5 or 1+p+...+p^(k-1)=(p-2)! Note that gcd(1+p+...+p^(k-1),p-1)=gcd(k,p-1) Since (p-1)/2 < p-2 we must have k = t (p-1)/2 for some t. Since p^(p-1)-1= = (1+(p-1))^(p-1)-1>(p-1)^(p-1) we must have t=1, i.e. p^((p-1)/2)-1=(p-1)! For p=5 we get a solution corresponding to n=4, k=2 and for p>5 we get p^((p-1)/2)-1= =prod_(i=1)^((p-1)/2) [i(p-i)]> >[p^2+(p-3)^2-5]p^[(p-1)/2)-2]> >p^((p-1)/2), a contradiction. Note, that we have split the product into two factors, one for i=1,2 given by (p-1)2 (p-2) and the other for i=3,..., (p-1)/2
A nice little problem from INMO 2014 , problem 2 Prove that [n] + [n/2] + [n/3] ....+ [n/n] + [√n] is even , where [n] is the floor of n Plz see it . Thank you
Proof sketch: Notice that f(n) - f(n-1), the increase from n-1 to n, is the number of factors of n, except if n is a square number, then it is 1 more. Now use that a number has an odd number of factors if and only if it is a square.
Let f(n) be the above expression f(n-1) =Σⁿ⁻¹ₖ₌₁ ⌊ⁿ⁻¹/ₖ⌋ + ⌊√(n-1)⌋ = Σⁿ⁻¹ₖ₌₁ (⌈ⁿ/ₖ⌉-1) + ⌊√(n-1)⌋ (Here, we used the fact that ⌈ⁿ/ₖ⌉=⌊ⁿ⁻¹/ₖ⌋+1 for any n,k∈ℕ) f(n)-f(n-1) = n-Σⁿₖ₌₁ (⌈ⁿ/ₖ⌉-⌊ⁿ/ₖ⌋) +⌊√n⌋-⌊√(n-1)⌋ Let Δ(k,n)=1 if k|n, 0 otherwise hence ⌈ⁿ/ₖ⌉-⌊ⁿ/ₖ⌋=1-Δ(k,n) summing from k=1 to n, it equals Σⁿₖ₌₁ (1-Δ(k,n)) = n-Σₖₗₙ 1 = n-τ(n) Thus f(n)-f(n-1)=τ(n)+⌊√n⌋-⌊√(n-1)⌋ •》Case 1: n is perfect square implying ⌊√n⌋=1+⌊√(n-1)⌋ hence f(n)-f(n-1)=τ(n)+1, which is even since τ(n) is odd if and only if n is a perfect square •》n is not perfect square implying ⌊√n⌋=⌊√(n-1)⌋ hence f(n)-f(n-1)=τ(n), which ia even in either case, f(n)-f(n-1)=k for some even k summing from 2 to n f(n)=(n-1)k+f(1) = (n-1)k+2 = 2((n-1)(k/2)+1) which is even for any n∈ℕ, as desired.
@@WhisperofAntiquityquite the opposite. Lots of calc stuffs are straight-up chug-in-plug-in dumb play, whilst number theory and combinatorics are whole different unpredictable beast
Let s(n) denote the sum of the digits of a positive integer n in base 10. If s(m) = 20 and s(33m) = 120, what is the value of s(3m)? Can someone please help me with this? It came in India. PRMO 2019 25th August Paper
A way to skip Wilson's Theorem: Add 1 to both sides, to get (n+1)^k = n! + 1 Well, we know that n! + 1 is coprime to any number less than or equal to n, so any primes dividing (n+1)^k must be greater than or equal to n+1. However, by the very form of it, any primes dividing (n+1)^k must be less than or equal to n+1. Therefore the ONLY prime dividing (n+1)^k must be n+1.
@@factsverse9957 Continue the argument in the video, after the point where Wilson's Theorem was used; this argument above shows that WT is unnecessary. So, continue from 6:56 (edited to find time reference).
No Wilsons Theorem is needed. When n>4, i) (n+1)^k= 1+n!= 1 mod (2). This imples that n is even ii) n even implies that (n-1)! = 0 mod (n) iii) k = ((n+1)^k-1)/n mod(n) = (n-1)! mod (n) = 0 mod(n) (iva) k=0, no (ivb) k>=n, Then (n+1)^k > n^n -1> n!-1. No solution, Hence, when n>4, there is no solution.
just a suggestion, can you open a new channel? one channel focuses on math question especially the Olympic question, one channel focus math theory such as analysis algebra number theory, etc.
@@ruairigarrett6834 You only need them mod p+1, so at least you're not dealing with numbers more than about p², but you're still doing p multiplications and might as well just try dividing p by everything less than p.
Once we know k is a multiple of n, you look at the original equation again. You realize the exponent on the left hand side is at least n. Also note n^n > n!, so the left hand side is growing more rapidly than the right. The rest is details and being rigorous.
@@oussemabouaneni992 but if we get n!>nⁿ then this will be contradiction, because this never holds for these rules. But he got nⁿ>n! which is clearly true. He should be write n!>nⁿ (he got it at the end but wrote it wrongly i think, but i understood his proof method clear)
@@rustemtehmezov9494 No no he wrote it perfectly correctly. He proved that (n+1)^k - 1 > n^n > n! which means that (n+1)^k - 1 is never equal to n! for n >= 5 which is what he set out to prove.
TNT ≡ is read “is congruent to.” -1 mod p means if you divide a number n by a prime p, the remainder is -1. In other words, it satisfies the expression: apm - 1; for any integer a. The reason why ≡ is used instead of =, is because any multiple of p satisfies the expression.
No Wilson's Theorem is needed. When n>4, i) (n+1)^k= 1+n!= 1 mod (2). This implies that n is even ii) n even and n>4 imply that (n-1)! = 0 mod (n) iii) k = ((n+1)^k-1)/n mod(n) = (n-1)! mod (n) = 0 mod(n) (iva) k=0, no (ivb) k>=n, Then (n+1)^k-1 >=( n+1)^n -1>=n^n>n!. No solution, Hence, when n>4, there is no solution.
Mod gives remainder. Some examples: 5 mod 3 = 2 because 5/3 has remainder 2. 4 mod 2 = 0 because 4 is divisible by 2 (i.e. no remainder). Once again, 7 mod 2 = 1 because 7/2 has a remainder of 1. It's important to remember when doing elementary number theory, we work in the integers and naturals. Hence all the whole number concerns.
I had to rewatch to understand it but if you reduce (n+1)^k-1=n! (mod n+1) you get 0-1=n! (mod n+1) then you rearrange to get the form from Wilson's theorem and that n+1 is prime. The zero in the above equation come from the fact that (n+1)^k is divisible by (n+1)
Wilson + inequality + bionomial + basic congruence = amazing problem
10:47 I think we used the hypothesis when we multiplied 2*(n/2), because for that to be true, we need both 2 and (n/2) in the product, and for that, we need n/2 to be different than 2, since they come from the factorial, and therefore n>4, which implies n\geq 5.
12:03
14:23
Something very important happened at 12:03 - u must check it out
Caesar Cipher Indeed! Thanks 👍
In general, in this video we have a "that's a good place to stop", quantity squared
Good place to start at 0:00
@@R0M4ur0 along with "let's go head and do that","all the way {up|down} to","and so on and so forth"....
It appeared on the SMO (Singapore Mathematical Olympiad), Open Round 2 on the year 2008, as problem number 1. Hope it helps!
@Adam Romanov You can find the pdf of it online, I got a pdf from a website fadjarp3g, plug in SMO Round 2 2008 fadjarp3g in the Google search bar and I think you should find it, hope this helps
14:00 he said "that's true for n≥5" but 4^4 > 4!, why is it
I'm sorry if it's a dumb questions
@qu-ack oh okay thanks
I was trying that exact problem, it was in an LTE article. Thanks
Training for maths olympiad?
I wasn't aware of Wilson's Theorem, but it's not too hard to see that n+1 has to be a prime in this problem, this is the easy part of Wilson's Theorem. If n+1 has a factor, which is smaller than it, then it appears in n! as well as (n+1)^k, so the two can not be just 1 apart (they are not coprime)
First thing I thought when I saw the thumbnail: "Hey, that looks like Wilson's Theorem! . . Oh wait, not quite." Wilson's Theorem says that
p | [(p-1)! + 1], iff p is prime. Here we would make n = p-1 and this becomes
(n+1) | (n! + 1), iff (n+1) is prime; vs our problem:
(n+1)ᵏ = n! + 1
which is a stronger condition on (n! + 1) than mere divisibility by (n+1).
k & n are restricted to the +ve integers, so start with k=1:
N+1 - 1 - n = n!
Works for n = 1 and 2; no others.
Solutions: (n,k) = (1,1), (2,1)
k=2:
n! + 1 will have to be a square. I think the only cases of that are n = 4, 5, and 7. n = 4 works for this equation; 5 and 7 do not:
4! + 1 = 25 = 5²
5! + 1 = 121 = 11²
7! + 1 = 5041 = 71²
So:
(4+1)² - 1 = 4! . . 24 = 24
Solution: (n,k) = (4,2)
I suspect there are no others, but I don't see a way to prove that. Let's see what Michael has...
... Very nicely done! So my suspicion was borne out. Thanks to Michael for the proof.
Fred
10:47 im guessing n>5 because you assume that there exists an n/2 >= 3, meaning n>=6
Correct, and since n+1 has to be prime, the case n=5 can be ruled out because 6 obviously isn't prime.
3:25 Not a big mistake but the left hand side is even and the right hand side is odd.
If it isn't too much of a hastle can you please put the video link in the description for theorems you used and proved in another video (like wilsons theorem here)
I would love to see you working on inequality problems.
Le Family Patriarch
Bao Quoc Le
Clever solution. Especially noticing n/2 and 2 are factors of n! when n even.
You don"t need Wilson Theorem.
(n+1)^k = n! + 1
n! + 1 is odd for n > 1, then n + 1 must be odd, then n must be even. (we don't need n + 1 prime, just the fact n is even to get k = 0[n])
Woo, that's slick
"just the fact that n is even to get k=0" how?
Vp(x!) >= 2*Vp(x) for all non prime x such that x> 4, then you can see that if n>4 and it is not prime( which is the case for n >4) k would have to be at least n, but (n + 1)^n - 1 > n! for n > 4. This is just an alternative solution:)
n=1,2 imply k=1. Now for n>2 we must have n+1=p is a prime, otherwise n+1 would have a proper divisor 1 < d =< (n+1)/2 < n which yields a contradiction modulo d:
0=n!=(n+1)^k-1=-1 and hence we can rewrite p^k-1=(p-1)! with p>=5 or
1+p+...+p^(k-1)=(p-2)! Note that gcd(1+p+...+p^(k-1),p-1)=gcd(k,p-1)
Since (p-1)/2 < p-2 we must have
k = t (p-1)/2 for some t. Since p^(p-1)-1=
= (1+(p-1))^(p-1)-1>(p-1)^(p-1)
we must have t=1, i.e.
p^((p-1)/2)-1=(p-1)!
For p=5 we get a solution corresponding to n=4, k=2 and for p>5 we get p^((p-1)/2)-1=
=prod_(i=1)^((p-1)/2) [i(p-i)]>
>[p^2+(p-3)^2-5]p^[(p-1)/2)-2]>
>p^((p-1)/2), a contradiction. Note, that we have split the product into two factors, one for i=1,2 given by (p-1)2 (p-2) and the other for i=3,..., (p-1)/2
Very nice solution... Nailed it👏👏
A nice little problem from INMO 2014 , problem 2
Prove that [n] + [n/2] + [n/3] ....+ [n/n] + [√n] is even , where [n] is the floor of n
Plz see it . Thank you
Proof sketch: Notice that f(n) - f(n-1), the increase from n-1 to n, is the number of factors of n, except if n is a square number, then it is 1 more. Now use that a number has an odd number of factors if and only if it is a square.
Hello 😂
@@TechToppers hmmmm
Let f(n) be the above expression
f(n-1)
=Σⁿ⁻¹ₖ₌₁ ⌊ⁿ⁻¹/ₖ⌋ + ⌊√(n-1)⌋
= Σⁿ⁻¹ₖ₌₁ (⌈ⁿ/ₖ⌉-1) + ⌊√(n-1)⌋
(Here, we used the fact that ⌈ⁿ/ₖ⌉=⌊ⁿ⁻¹/ₖ⌋+1 for any n,k∈ℕ)
f(n)-f(n-1)
= n-Σⁿₖ₌₁ (⌈ⁿ/ₖ⌉-⌊ⁿ/ₖ⌋)
+⌊√n⌋-⌊√(n-1)⌋
Let Δ(k,n)=1 if k|n, 0 otherwise
hence ⌈ⁿ/ₖ⌉-⌊ⁿ/ₖ⌋=1-Δ(k,n)
summing from k=1 to n, it equals
Σⁿₖ₌₁ (1-Δ(k,n))
= n-Σₖₗₙ 1 = n-τ(n)
Thus
f(n)-f(n-1)=τ(n)+⌊√n⌋-⌊√(n-1)⌋
•》Case 1: n is perfect square
implying ⌊√n⌋=1+⌊√(n-1)⌋
hence f(n)-f(n-1)=τ(n)+1, which is even since τ(n) is odd if and only if n is a perfect square
•》n is not perfect square
implying ⌊√n⌋=⌊√(n-1)⌋
hence f(n)-f(n-1)=τ(n), which ia even
in either case, f(n)-f(n-1)=k
for some even k
summing from 2 to n
f(n)=(n-1)k+f(1)
= (n-1)k+2
= 2((n-1)(k/2)+1)
which is even for any n∈ℕ, as desired.
I love those videos.
Greetings from Spain :D
Woow dope explanation.... Can u please try Putnam 2014 a5 , the official solution is unbearable 😭
Just got out of Calc 3 thinking that I had gotten pretty good at math. Then I watched this and my brain melted.
This is mere child's play compared with calc 3
@@WhisperofAntiquityquite the opposite. Lots of calc stuffs are straight-up chug-in-plug-in dumb play, whilst number theory and combinatorics are whole different unpredictable beast
Una equació meravellosa. Genial
Thanks sir
Seeing your proofs is making me smarter. :)
Please do Putnam 2006 B2
Let s(n) denote the sum of the digits of a positive integer n in base 10. If s(m) = 20 and s(33m) = 120,
what is the value of s(3m)?
Can someone please help me with this?
It came in India. PRMO 2019 25th August Paper
A way to skip Wilson's Theorem:
Add 1 to both sides, to get
(n+1)^k = n! + 1
Well, we know that n! + 1 is coprime to any number less than or equal to n, so any primes dividing (n+1)^k must be greater than or equal to n+1. However, by the very form of it, any primes dividing (n+1)^k must be less than or equal to n+1.
Therefore the ONLY prime dividing (n+1)^k must be n+1.
Then? How can we proceed, it's unclear for me
@@factsverse9957 Continue the argument in the video, after the point where Wilson's Theorem was used; this argument above shows that WT is unnecessary.
So, continue from 6:56 (edited to find time reference).
LTE Lemma
but... that is just a rephrase of the converse of wilson's theorem which was applied in the vid....
This problem is beautiful
Nice problem, but at 3:28 (someone else may have already pointed this out...), you mixed up "left-hand" and "right-hand"... 😊
1 year later , 200k more subs
Video idea: Prove the Hardy-Ramanajan Series for partitions of n :)
He has a playlist of partitions and I think he was going to do that, or did it already. Check that out
Good question
Fantastic
That was brain storming!
Uff
Will see again...
No Wilsons Theorem is needed. When n>4,
i) (n+1)^k= 1+n!= 1 mod (2). This imples that n is even
ii) n even implies that (n-1)! = 0 mod (n)
iii) k = ((n+1)^k-1)/n mod(n) = (n-1)! mod (n) = 0 mod(n)
(iva) k=0, no
(ivb) k>=n, Then (n+1)^k > n^n -1> n!-1. No solution,
Hence, when n>4, there is no solution.
Obviously.
just a suggestion, can you open a new channel? one channel focuses on math question especially the Olympic question, one channel focus math theory such as analysis algebra number theory, etc.
Good
The form of the numbers is similar to the brown numbers
6:53 why is n + 1 a prime? Does this cover cases where n + 1 is not prime?
Reverse wilson
Where is guy says everytime "answer=1"?
By applying Wilson 's theorem, can we find the rest of prime numbers that are >100 (theoretically speaking)
Good luck calculating those factorials lol
@@ruairigarrett6834 You only need them mod p+1, so at least you're not dealing with numbers more than about p², but you're still doing p multiplications and might as well just try dividing p by everything less than p.
Count Olaf
Beautiful solution ! Kindly tell the motivation for the inequality.
Once we know k is a multiple of n, you look at the original equation again. You realize the exponent on the left hand side is at least n. Also note n^n > n!, so the left hand side is growing more rapidly than the right. The rest is details and being rigorous.
You get (n+1)^mn-1>nⁿ>n! but isn't it was (n+1)^mn-1=n! and this means n!>nⁿ? İ think it was typo
That's the contradiction. He supposed that such an n exists and proved that its existence is impossible.
@@oussemabouaneni992 but if we get n!>nⁿ then this will be contradiction, because this never holds for these rules. But he got nⁿ>n! which is clearly true. He should be write n!>nⁿ (he got it at the end but wrote it wrongly i think, but i understood his proof method clear)
@@rustemtehmezov9494 No no he wrote it perfectly correctly. He proved that (n+1)^k - 1 > n^n > n! which means that (n+1)^k - 1 is never equal to n! for n >= 5 which is what he set out to prove.
@@oussemabouaneni992 Oh, now i understood what you mean, yeah this is accetable. (Almost same as i supposed) Thanks for clarification👍
@@rustemtehmezov9494 Cheers mate.
Is there any problem you can't solve?
Global climate change?
For integers, n^n=>n! Is true. But beyond that, it's not always true. Case in point:(1/2)^(1/2)=sqrt(2)/2 < (1/2)! = sqrt(pi)/2
Because K is the power and n=2 (n+1)^k = n!. 1 is a constant so how did you get k=1 where n=2
3^k = 3
What k satisfies this equation?
@@RealLifeKyurem what do the 3 stripes and the -1(mod p) mean?
TNT ≡ is read “is congruent to.” -1 mod p means if you divide a number n by a prime p, the remainder is -1. In other words, it satisfies the expression:
apm - 1; for any integer a.
The reason why ≡ is used instead of =, is because any multiple of p satisfies the expression.
0 not a natural number?
No Wilson's Theorem is needed. When n>4,
i) (n+1)^k= 1+n!= 1 mod (2). This implies that n is even
ii) n even and n>4 imply that (n-1)! = 0 mod (n)
iii) k = ((n+1)^k-1)/n mod(n) = (n-1)! mod (n) = 0 mod(n)
(iva) k=0, no
(ivb) k>=n, Then (n+1)^k-1 >=( n+1)^n -1>=n^n>n!. No solution,
Hence, when n>4, there is no solution.
What is Mod? 😭😭😭😭
Mod gives remainder. Some examples: 5 mod 3 = 2 because 5/3 has remainder 2. 4 mod 2 = 0 because 4 is divisible by 2 (i.e. no remainder). Once again, 7 mod 2 = 1 because 7/2 has a remainder of 1.
It's important to remember when doing elementary number theory, we work in the integers and naturals. Hence all the whole number concerns.
じっと見ていると、n=4と分かりますな。
K=2
13:33 Or just (n+1)^n -1 >= (n+1)n(n-1)... 2 - =(n+1)! -1 > n!
God he’s such a chad
hahahahahaha
You say K must be a multiple of N, but the solutions given have N as a multiple of K.
all solutions with n >= 5 must have k as a multiple of n. That does not necessarily apply to the given solutions.
Immediately I don't get why n+1 is prime. If n=5 then n+1=6 is not prime.
I had to rewatch to understand it but if you reduce (n+1)^k-1=n! (mod n+1) you get 0-1=n! (mod n+1) then you rearrange to get the form from Wilson's theorem and that n+1 is prime. The zero in the above equation come from the fact that (n+1)^k is divisible by (n+1)
I got confused at how you got k=1 at n=2
Just put n=2
U get 3^k=3
Angel Mendez-Rivera That solves it. Thanks 🙏❤️ @michael penn
Hi,
This was before hair cutting, so I understand my request about the camera is not taken into account.