This is always even??
Вставка
- Опубліковано 17 січ 2025
- We look at a viewer suggested problem from the Indian National Math Olympiad.
Please Subscribe: www.youtube.co...
Merch: teespring.com/...
Personal Website: www.michael-pen...
Randolph College Math: www.randolphcol...
Randolph College Math and Science on Facebook: / randolph.science
Research Gate profile: www.researchga...
Google Scholar profile: scholar.google...
If you are going to use an ad-blocker, considering using brave and tipping me BAT!
brave.com/sdp793
Buy textbooks here and help me out: amzn.to/31Bj9ye
Buy an amazon gift card and help me out: amzn.to/2PComAf
Books I like:
Sacred Mathematics: Japanese Temple Geometry: amzn.to/2ZIadH9
Electricity and Magnetism for Mathematicians: amzn.to/2H8ePzL
Abstract Algebra:
Judson(online): abstract.ups.edu/
Judson(print): amzn.to/2Xg92wD
Dummit and Foote: amzn.to/2zYOrok
Gallian: amzn.to/2zg4YEo
Artin: amzn.to/2LQ8l7C
Differential Forms:
Bachman: amzn.to/2z9wljH
Number Theory:
Crisman(online): math.gordon.edu...
Strayer: amzn.to/3bXwLah
Andrews: amzn.to/2zWlOZ0
Analysis:
Abbot: amzn.to/3cwYtuF
How to think about Analysis: amzn.to/2AIhwVm
Calculus:
OpenStax(online): openstax.org/s...
OpenStax Vol 1: amzn.to/2zlreN8
OpenStax Vol 2: amzn.to/2TtwoxH
OpenStax Vol 3: amzn.to/3bPJ3Bn
My Filming Equipment:
Camera: amzn.to/3kx2JzE
Lense: amzn.to/2PFxPXA
Audio Recorder: amzn.to/2XLzkaZ
Microphones: amzn.to/3fJED0T
Lights: amzn.to/2XHxRT0
White Chalk: amzn.to/3ipu3Oh
Color Chalk: amzn.to/2XL6eIJ
Micheal is actually the only person I "Know" that can say "I love the floor function"
*Michael
After watching him solving some of these, I also began to love the floor function.
I think thats bcs he is a number theorist
As soon as I see a problem with the floor function, I am sweeting bullets.
Everybody:
Michael: ~ Let the bodies hit the ~ (4 times) FLOOOOR!!!
N! ~ Nothing wrong with me ~ (4 times)
N! ~ Something's got to give! ~
I can't believe that I was able to solve this problem 😁
There's a much simpler solution.
Just consider the graph xy=n.(x>0).
Ignoring the last term for now,
[n/1] + [n/2] + ... + [n/n] = number of integral (x,y) that lie on or below the curve xy=n and above x-axis and y-axis.
For every Integral point (x0,y0) here, such that x0!=y0, there exists a point (y0,x0) reflected about the line y=x.
The only points unaccounted for are on the line y=x, which are (1,1), (2,2),..., ([n^0.5],[n^0.5]), overall [n^0.5] points.
This will be balanced out by the additional term at the last [n^0.5].
Hence, the value of the given expression is even.
Great solution!
@@coolnecromancer1 thanks
woah , amazing solution !
@@prithujsarkar2010 thanks 😊
Nice solution bro
There’s a slight slip at 10:25. There are k+1 terms underlined in red, but only k terms are then written, plus the 2b+1. The missing term is the last, which would be floor(k/(k+1)). Of course, floor(k/(k+1)) is always zero so this slip doesn’t affect the result.
Oh, and the exact same thing happens at 13:35 too.
that's a surprisingly nice solution. i wouldn't have expected induction to work well here
A number theoretic solution is this:
Claim: Σ(i= 1 to n) floor(n/i)= Σ(i= 1 to n) d(i)
(where d(k) is the number of divisors of natural number k. )
Proof: floor(n/i) is the number of elements of the set S = {1, 2,...n} that are divisible by i. So, when the total sum is considered, each number k of the set S is counted once, in floor(n/i), for each i that divide k. Hence proved.
Fact(stated without proof, which can be found online easily) : d(i) is odd if and only if i is a perfect square.
So taken modulo 2, our sum becomes
Σ(i= 1 to n) floor(n/i) + floor(√n)
= (Σ( i is a perfect square ≤ n) 1) + floor(√n)
But the set of perfect squares less than n itself has floor(√n) elements.
So, our sum taken modulo 2 becomes 2floor(√n) = 0.
Hence proved.
Claim: Σ(i = 1 to n) [n / i] = -[√n]² + 2 * Σ(i = 1 to [√n]) [n / i]
Proof is simple, use the symmetry of the hyperbola y = n / x and count lattice points under it taking care to avoid double counting of a square with side length [√n].
[√n] + Σ(i = 1 to n) [n / i] ≡ [√n] - [√n]² ≡ 0 (mod 2)
How I did it:
How many ordered positive integer pairs (a,b), satisfy a*b=
Here's an induction-free argument. We will show that the given value divided by 2 actually counts the number of some configuration, which in turn shows that the value is even.
Consider the number of rectangles of integer sides a, b and area ab
Wow
14:28
S thats the good place to stop
यह रुकने के लिए एक अच्छी जगह है।
YESSSSSS FINALLYYY I AND MY FRIEND WERE SPAMMING THIS QUESTION FOR SO LONG!!!!!!!! I FEEL SUCCESSFUL TODAY!!!!!!!THANK YOU SO MUCH!!!!!!!!!
Saw u and Chabbi recommending this,A nice problem
@@yashvardhan6521 actually his name is prithuj
@@debayuchakraborti1963 There is Prithuj and Chabbi Sarkar , Different people ,??
@@yashvardhan6521 same lol
@@debayuchakraborti1963 Same hai really ?
10:34 shouldn't there be an addition of 1 in that red underlined (equation maybe?, Don't know what it's called 😐), because the floor (k/k)+1 came from the floor (k+1/k) So what about the floor (k+1/k+1) from the above red underlined equation? If we cancel both numerator and denominator then we will be left with floor 1 (=1) , where did that 1 go???.
Yess, I also didnt understand where that one extra term disappeared
@@lukasfic1883 is that gara?
You can add floor(k/(k+1)) to the induction hypothesis equation since it is zero. Then it all comes out neatly.
11:50 what about the (k+1)/(k+1) term?
He should have included that as one of the B terms. But since the floor of k/(k+1) is 0, it doesn't mess up the solution
@@MichaelGrantPhD oh, yeah, because itself is one of the factors
@@romajimamulo right.
I was wondering that as well. It is missing from the line at the bottom of the board, but the term should be floor(k/(k+1)) which is zero so it does not affect the result. The difference between floor((k+1)/(k+1)) and floor(k/(k+1)) is 1 because (k+1) divides (k+1) (duh!) and that 1 is included in the 2b+1 value because k+1 is one of the divisors of k+1.
The same thing happens at 13:30
Hello Mr. Penn! I have a suggestion... Could you please not show us the hints right away? By that I mean show us the full statement and only after show the hint, maybe how you snap your fingers or whatever you do when you transition to the empty board to start the solution. There are usually problems that I first try them my self and I don’t want to right away see the hints... Thanks for reading, and have a great day!
I second this! This is a great suggestion.
Hello comrade
He usually makes a thumbnail that has the problem without hints. So if you can find a way to view the thumbnail only, that should be what you want.
@@periolat Yea, you are right, but sometimes the thumbnail doesn’t have the full statement. Here, the thumbnail showed us the sum, but asked if it’s always even, not that we need to prove anything. Have a good day!
Ty. Fantastic.
Another compelling question and an even more so solution. Great.
I found it easier to define S as the expression given, but with denominators going to infinity (note that all terms with a denominator greater than n are zero). I then showed that S(1) = 1+1=2, and solved for S(n+1) - S(n). Using the same arguments about when the floor of each term increases, this difference is equal to the count of factors of n+1, plus one if n+1 is a square. Again using the "count of factors" rule cited in the video, the sum of these is always even. so S(n+1)-S(n) is even. Then, as S(1) is even and even plus even is even, induction follows.
you deserve a million subs easy.
content : 10
likeabiltiy ; 10
math insight : 10
physique : 13
Wait this is all even? Always has been
You forgot about floor((k+1)/(k+1)) term.
In case 2:
SUM(n = 1 to k+1 of floor((k+1)/n)) + floor(sqrt(k+1)) should be equal to SUM(n = 1 to k of floor(k/n) ) + 2b + floor((k+1)/(k+1)) + floor(sqrt(k))
It is already considered inside the term where m is a divisor of k + 1. 2b in this case.
@@FPNader Actually it isn't. 2b is the difference between the first k terms in the sums.
@@antonryzhov if you don't consider (k+1)/(k+1) in 2b, then you're not taking all divisors, you're taking 2b-1 divisors. Then, add the result of (k+1)/(k+1) which is 1, you get 2b again.
Thanks for making this video , nice solution indeed :D btw i am curious about that "geometric solution" which you mentioned , where can i find it ?
I want to see the other solutions as well.
To get things clear 0 is officially determined not to be a natural number so you should exclude this case always when you have natural number.
Zero is not in the N cluster!
oh very clever, I just got it, this is a great problem
Sir, please solve questions which are involving mod
You are the Best !This is exactly the problem I had to do today and you brought me the solution
Geometric proof? I am intrigued.
Take a look at my comment above, for a proof using coordinate geometry.
Aren't you dropping a term when you compare the expression for case k+1 to case k term by term? You can't compare floor((k+1)/(k+1)) to a term in case k b/c it has no floor(k/(k+1)) term. Am I missing something?
Good
Wayyyyy too many ads...
Lambda function is much easier
I wasn’t aware that irrational numbers could be even or odd.
By using the floor function in the equation every number is mapped to the nearest whole number less than it, so it doesn't matter that the square root term is irrational, as it's mapped to a lower whole number in the equation..
@@peglor Oh, okay. That helps a lot-thanks! 👍🏼
2nd comment.... Please do IMO 2011 P2
Go see 3b1b
I hate the floor function but I did enjoy this problem
Though induction is a perfectly robust mathematical method of proof, I can't help find myself wondering if there's a non-inductive proof of this.
Induction feels a bit like cheating (this doesn't take away from the great videos Mr. Penn makes)
@@angelmendez-rivera351 Yes, but what is the exact proof?
i watch all
wow I am so early today
That was a amazing class, but... I need to ask about your name, did anyone ever bully you? Really sorry but I'm actually kind of curious. Like, you know what I'm talking about, take your name and add 'is' to your last name.
@ゴゴ Joji Joestar ゴゴ From borat 2