This problem was proposed by me 😀. Thanks a lot for choosing to solve it! My original solution was pretty complicated (which is also the official solution) and the problem turned out to be much easier. Your method was pretty good! Although in the end there's a tiny mistake: equality holds for (m,m+2) only when m is even.
Loved the question! An interesting note to make: you can get a more explicit form of the pairs for which equality hold with only a small bit of additional maths. To see how, we can plug both resulting pairs into the first condition: gcd(m+1, n+1) = 1. Note that for the pair (m, m+1), this is just the gcd of two consecutive numbers. Thus: gcd(m+1, (m+1)+1) = 1. For the other option, (m, m+2), we have: gcd(m+1, (m+2)+1) = gcd(m+1, (m+2)+1-(m+1)) = gcd(m+1, 2) = 1. But this is the case iff m+1 is odd, i.e. m is an even number. This allows us to write that equality holds iff (m,n) is given by one of the following forms: (k, k+1), (2k, 2k+2), (k+1, k), (2k+2, 2k) for any positive integer k. Funnily enough, the (2k, 2k+2) pair and its symmetric counterpart are just twice the other solution.
@@anksssssssss I think you have to rewatch the end of the video (at around 10:55) a tad more carefully. He explicitly notes that his additional requirement gcd(m+1, n+1) = 1 must hold. As a counterexample to your claim that any (m, m+2) will work, you can try it with m = 13, i.e. (m, n) = (13, 15). Calculating the individual terms: gcd(13+0, 15+0) = 1 gcd(13+1, 15+1) = 2 gcd(13+2, 15+2) = 1 Summing these together you get 4, but: 2|13 - 15| + 1 = 2*2 + 1 = 5. Thus equality is not attained and the statement does not hold. The secret here lies in the fact that this first requirement is violated: gcd(13+1, 15+1) = gcd(14, 16) = 2. But the video does prove that _with_ this requirement, the conclusion holds. And this is only true for the case (m, m+2) if m is an even number, i.e. m = 2k for some positive integer k. Other counterexamples also exist, such as @chen reddy sundeep's above (m=3), but even m=1 violates this condition.
Thanks for all these interesting problems. A similar solution exists using only the first priority and proving easily that if gcd(a,b) not =1 then gcd(a+1,b)=1. For the equality you can easily prove in the same way that if gcd(a,b)>2 then gcd(a+2,b)=1 or 2 and take the necessary contition m-n=1 or m-n=2. These set of solutions under the examination for gcd(m,n)=1 and gcd(m,n)=2 will give you the sufficient contition that m has to be even in the set (m, m+2). (Your solution is richer.)
You have a small mistake about the equality condition. (m,m+1),(m+1,m) works always but (m,m+2) works only if m is even. If (m-n) is equal to 2 and previously you discovered that (m-n) divides m, that means m is even. Take (7,9) for example. Lhs is 4. Rhs is 5. For equality when (m-n)=2 you need in the lhs for 2 of the gcd's to be 2 and one of them (in the middle) to be 1.
14:07 You also need m to be even in the case where the difference equals 2. If m is odd, then the middle gcd is 2, and the outer 2 are both 1, which isn’t good enough.
Hello Micheal, I am confused about the step atound 5:53, where you claim that d^’ is divisible by n. Can anyone explain this step in further detail to me? Many thanks
Thank you so much for explaining it so well. One question I have is, for the derivation of the conditions for equality, it seemed to me that only necessary conditions were obtained, but not sufficient conditions, i.e., in addition to necessity, I believe sufficiency should also be established.
@Tangent of circle. functional eqautions from B J Venkatachala. He teaches at IMOTC. Combinatorics i don't think u need any particular book for INMO level. I suggest just solving previous problems and refer theories while referring solutions
Alternative solution (using product of two gcd with one common argument): Lemma1: gcd(a,b) = 1 then gcd(a,c)*gcd(b,c) n: Let e = gcd(m,n), f=gcd(m+1,n+1), g=gcd(m+2,n+2) e*f = gcd(m,n)*gcd(m+1,n+1) = gcd(m,m-n)*gcd(m+1,m-n)
I enjoyed the little revision at the start. One question, when d/d’ and d’/d, shouldn’t we conclude that d=d’ or d=-d’? Anyway, I assumed you were working with a>b (wlog).
I read and heard gcd as greatest common denominator, which was really confusing; I had to do a web search to find out that d was divisor. Whatever happened to gcf (greatest common factor)? Also, probably trivial, but looking at the other end, the smallest answer is when |m-n| =1, so all three gcds are 1, and the sum is 3. O, by the way: this is an equality case.
Hey Michael, nice solution BUT for the equality you show that m-n=1 or 2 is necessary, but not that it is sufficient. (m, m+2) only achieves equality when m is even, and not when m is odd, so you've got some extra cases included in your answer.
This problem was proposed by me 😀. Thanks a lot for choosing to solve it! My original solution was pretty complicated (which is also the official solution) and the problem turned out to be much easier. Your method was pretty good! Although in the end there's a tiny mistake: equality holds for (m,m+2) only when m is even.
If gcd(a, b) > 1, then gcd(a +- 1, b) 1,
gcd(m, m - n) + gcd(m + 1, m - n) + gcd(m + 2, m - n)
I am Indian, going to give INMO this year. You really helped me Prof. Michael 😇
Thanks a lot
Wait basically u gotta qualify for that first ..
Yo u on aops?
@@throwawayuser9931 yes.... DebayuRMO my username
@@debayuchakraborti1963 Unless he has an INMO Merit Certificate.
Lekin ioqm Ka result to 1 month pehle nikla hai naa?
Yesss.....thanks to Mr. Penn for solving this so beautifully, the official solutions were not that good ...thanxx !!!!
What do u expect ? Mr Penn solves these by himself
What do u mean?
@@debayuchakraborti1963 are you a fifth grader?
No I am a 8th grader
@@agnibeshbasu3089 he's a 4th grader bro lol , he's pro i know him , he's my neighbor too
Loved the question! An interesting note to make: you can get a more explicit form of the pairs for which equality hold with only a small bit of additional maths.
To see how, we can plug both resulting pairs into the first condition:
gcd(m+1, n+1) = 1.
Note that for the pair (m, m+1), this is just the gcd of two consecutive numbers. Thus:
gcd(m+1, (m+1)+1) = 1.
For the other option, (m, m+2), we have:
gcd(m+1, (m+2)+1) = gcd(m+1, (m+2)+1-(m+1)) = gcd(m+1, 2) = 1.
But this is the case iff m+1 is odd, i.e. m is an even number.
This allows us to write that equality holds iff (m,n) is given by one of the following forms:
(k, k+1), (2k, 2k+2), (k+1, k), (2k+2, 2k) for any positive integer k.
Funnily enough, the (2k, 2k+2) pair and its symmetric counterpart are just twice the other solution.
This is a great observation
I think u took unnessary trouble.
It's it's true for all (m,m+2) , then u need not to write two solutions as (k,k+2) and (2k,2k+2)
@@anksssssssss It's not true for all (k,k+2)
Try substituting m=3 and n=5 and check it
@@anksssssssss I think you have to rewatch the end of the video (at around 10:55) a tad more carefully. He explicitly notes that his additional requirement gcd(m+1, n+1) = 1 must hold. As a counterexample to your claim that any (m, m+2) will work, you can try it with m = 13, i.e. (m, n) = (13, 15).
Calculating the individual terms:
gcd(13+0, 15+0) = 1
gcd(13+1, 15+1) = 2
gcd(13+2, 15+2) = 1
Summing these together you get 4, but:
2|13 - 15| + 1 = 2*2 + 1 = 5.
Thus equality is not attained and the statement does not hold. The secret here lies in the fact that this first requirement is violated:
gcd(13+1, 15+1) = gcd(14, 16) = 2.
But the video does prove that _with_ this requirement, the conclusion holds. And this is only true for the case (m, m+2) if m is an even number, i.e. m = 2k for some positive integer k.
Other counterexamples also exist, such as @chen reddy sundeep's above (m=3), but even m=1 violates this condition.
For equality, in the case (m,m+2) or (m+2,m), m needs to be even, otherwise the sum of the gcds is 4, not 5.
Thanks for all these interesting problems. A similar solution exists using only the first priority and proving easily that if gcd(a,b) not =1 then gcd(a+1,b)=1. For the equality you can easily prove in the same way that if gcd(a,b)>2 then gcd(a+2,b)=1 or 2 and take the necessary contition m-n=1 or m-n=2. These set of solutions under the examination for gcd(m,n)=1 and gcd(m,n)=2 will give you the sufficient contition that m has to be even in the set (m, m+2). (Your solution is richer.)
You have a small mistake about the equality condition.
(m,m+1),(m+1,m) works always but (m,m+2) works only if m is even.
If (m-n) is equal to 2 and previously you discovered that (m-n) divides m, that means m is even.
Take (7,9) for example.
Lhs is 4. Rhs is 5.
For equality when (m-n)=2 you need in the lhs for 2 of the gcd's to be 2 and one of them (in the middle) to be 1.
Thanks a lot , I'm a Indian and preparing for INMO this year ! Was really helpful
At 12:25 , gcd(m+1, n+1) = 1 only if m,n are even. So, if gcd(m+1, n+1) = 1 then m and n won't be odd.
Thanks so much for considering solving an INMO problem
14:07 यहाँ रुकने की अच्छी जगह है।
Wow ! So fast !
Woah
So you are Indian
Hindi is not the language of india it has many other language other than hindi
Ohh HINDI
14:07 You also need m to be even in the case where the difference equals 2. If m is odd, then the middle gcd is 2, and the outer 2 are both 1, which isn’t good enough.
Please proceed with your real analysis playlist. Can't wait for new videos!
6:27 can someone explain how he got d'|n from d'|a+1 and d'|b?
suppose m>n. lets call the 3 gcd's g0,g1,g2. all of them divide m-n so the all are
These videos are so good - and, along with other online content, a real “leveller” for bright teens who do not have top quality maths teachers.
Hello Micheal, I am confused about the step atound 5:53, where you claim that d^’ is divisible by n. Can anyone explain this step in further detail to me? Many thanks
d' divides dm+1 so d' divides n(dm+1) and d' divides dn so d' divides m(dn) and so d' divides n(dm+1) - m(dn) = n
@@saroshadenwalla398 thanks!
Thank you so much for explaining it so well. One question I have is, for the derivation of the conditions for equality, it seemed to me that only necessary conditions were obtained, but not sufficient conditions, i.e., in addition to necessity, I believe sufficiency should also be established.
Damn. I gave this INMO last year and solved it. Good memories :)
Did u go to IMOTC'19?
Share your experience then
@Tangent of circle. functional eqautions from B J Venkatachala. He teaches at IMOTC. Combinatorics i don't think u need any particular book for INMO level. I suggest just solving previous problems and refer theories while referring solutions
@@kaklisarangi2550 I went to IMOTC 2018. I didn't get selected in 2019 , as I was busy with JEE schedule :(
@@kingpin1199 hi senior. I was in imotc 19, that's y I asked. Are u in iit? Asking cuz I am fresher in one. Maybe could ask u a couple of things.
Finally you listened to our request !! Yaaaaay thanks !
Alternative solution (using product of two gcd with one common argument):
Lemma1: gcd(a,b) = 1 then gcd(a,c)*gcd(b,c) n:
Let e = gcd(m,n), f=gcd(m+1,n+1), g=gcd(m+2,n+2)
e*f = gcd(m,n)*gcd(m+1,n+1) = gcd(m,m-n)*gcd(m+1,m-n)
I enjoyed the little revision at the start.
One question, when d/d’ and d’/d, shouldn’t we conclude that d=d’ or d=-d’? Anyway, I assumed you were working with a>b (wlog).
Ah true plus minus
I read and heard gcd as greatest common denominator, which was really confusing; I had to do a web search to find out that d was divisor. Whatever happened to gcf (greatest common factor)? Also, probably trivial, but looking at the other end, the smallest answer is when |m-n| =1, so all three gcds are 1, and the sum is 3. O, by the way: this is an equality case.
Hola Michel Penn, can someone explain how he got d'|n from d'|a+1 and d'|b?
Please, please i thanks
I consider myself pretty good at number theory but I’ll be frank I don’t think I would have gotten this on my own
Please discuss Ramanujan mock theta function.
Could you do geometry and combination problems? Thanks,
@Michael Penn: Why is the flag rotated in the thumbnail? Anyway, very well explained proof.
He always rotates the flags.
@@adeeb1787 Fine. But why?
It's question of Euclidean algorithm
How exactly?
i'm a little confused in the begining the inequatlity says
d 2:09, b: 4:28, d: 10:32
5:01 why is n
Since we have already taken the case of d=1 , so now d>=2 , b=dn, d=b/n, so b/n>=2, hence
n
Hey Michael, nice solution BUT for the equality you show that m-n=1 or 2 is necessary, but not that it is sufficient. (m, m+2) only achieves equality when m is even, and not when m is odd, so you've got some extra cases included in your answer.
🤩 OP question
V. Nice soln.
Wow, most of the comments are of indian !!
Hmmm
What is gcd?
Your name is JEE 2021??
At what age did you start solving Olympiad level problems?
13
If u r asking in general
@@debayuchakraborti1963 avi kitne saal ke ho ?
@@MANISHGUPTA-oe3in 13 lol
@@debayuchakraborti1963 kaash hume v 13 saal ki umar mai olympiads ka pta hota chutiya kismat
Noice Problem
Aur HIMADRI
HM tu bhi yaha XD XD XD
I never feel so much patriotic while solving a problem..
lol
XD 😆😆
At __ : __ coming soon...
Nice ...
I m indian
So what?
He shown indian flag on wall..soon he will surely cross his subcriber more than 1 lakh
top
Anyone தமிழ்....?