Swiss Mathematical Olympiad | 2017 Question 7
ฝัง
- เผยแพร่เมื่อ 24 พ.ค. 2020
- We present a solution to Question 7 of the 2017 Swiss Mathematical Olympiad.
Please Subscribe: th-cam.com/users/michaelpennma...
Personal Website: www.michael-penn.net
Randolph College Math: www.randolphcollege.edu/mathem...
Research Gate profile: www.researchgate.net/profile/...
Google Scholar profile: scholar.google.com/citations?...
Books I like:
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/ntic/
Strayer: amzn.to/3bXwLah
Andrews: amzn.to/2zWlOZ0
Calculus:
OpenStax(online): openstax.org/subjects/math
OpenStax Vol 1: amzn.to/2zlreN8
OpenStax Vol 2: amzn.to/2TtwoxH
OpenStax Vol 3: amzn.to/3bPJ3Bn
"Probably we will not be able to find specific value of n..."
...then goes and finds all possible n's.
Anyway excellent explanation!
he didn't really and you can't, none has ever found an odd perfect number and there is no proof about there existence or non existence. As for a power of 2 you can easily add all the factors and see that you come 1 short so not possible.
@@maosatela If i don't miss anything, then in this context the term "n is a perfect square" just means sqrt(n) is in setN := {1, 2, 3, ... }.
So the set of solutions for n (with setP := set of all prime Numbers) is:
{ p^1008 | p in setP }.
@@maosatela Perfect numbers are not the same as perfect squares.
@@derwolf7810 You would still need to check that of these solutions work. He only showed that a solution n is in the form p^1008, not that a number in the form p^1008 is a solution.
I'd say that it would be nice to also find the list of corresponding pairs (a,b) for a solution n.
@@Djorgal He did show that when n is the form p^1008, then it is a solution. All values of p work and the list of solutions is given by reversing the steps in the video. Take any prime p. Let n = p^1008, then n^2 = p^2016. The 2017 divisors of n^2 are 1, p, p^2, ..., p^2016, so it is also the case that (a-n) takes on the values 1, p, p^2, ..., p^2016 and the corresponding (b-n) then is p^2016, p^2015, ..., p, 1. You can check that (a-n)(b-n) = n^2. So the 2017 solutions of the original problem is the pairs (a,b) from the list (1+p^1008, p^2016+p^1008), (p+p^1008, p^2015+p^1008), (p^2 + p^1008, p^2014+p^1008) ..., (p^2016 + p^1008, 1+p^1008).
Not only is it square , but also a cube and a seventh power , WOW
Small correction: at 6:45, the set of ordered pairs (s, n^2/s) is NOT equal to the set containing the divisors of n^2. They just have the same cardinality.
Haha, came here to comment this as well
Yes. It should be a second correspondence double arrow.
Yh I was about to comment this too
where can I estudy about this?
Ah yes I found the same small mistake while watching it. I think it also applies to the last two sets he writes on that board before erasing. Thankfully, the proof still holds of course since bijection exists iff equicardinal, and all we really care about is equicardinality since 2017 is the cardinality of the first set.
Hi, 2017 SMO contestant here (and I now work in the SMO organization): thank you so much for making a video on one of our problems! Your solution was, of course, perfect. Subscribed!
You’re the guy who slept during the imo lol
@@lgooch???
@@omicronl2172 iirc he took a nap during the imo (i think i read it on quora or something, idk)
Absolutely spectacular video! You are doing the world a great service right now, and I hope that you get the recognition you deserve as a truly remarkable teacher.
Your content has grown up when talking about quality, great job!
The factoring trick used here is Simon's Favorite Factoring Trick. Found in both the AOPS wiki, and AOPS Alcumus. And yes, lots of competition type problems depend on this trick.
Excellent.I just love your way of explaining the whole thing.Its really a nice problem.
Good video. Also, two cameras!
Essa foto aí é amaldiçoada amigo
Kkkkkkkk caralho que perfil desgraçado
Cinematic!
I love these videos even though I do not understand all of it. Keep up the good work!
A very interesting question, thank you for a clear explanation!
At 7:13 I think you meant that the cardinality of the last three sets are all equivalent-not that the sets themselves are equivalent. As you said, this satisfies the one-to-one correspondence needed for bijection because the first and last sets have the same cardinality.
Can tou explain the difference? If they have a one-to-one and onto correspondence, doesn't that mean they have the same number of elements?
wow your video quality got a lot better in just a month hats off man
Damn. Your subscribers are growing at an insane rate now. Well done!
this is so entertaining (and intimidating) to watch as someone who only has a vague idea of what is going on and has only taken one uni-level maths class lol! even though i didn't know much of what was being said, i was able to follow along since you weren't beating around the bush about anything, and the colours and separate boards helped too
In the third part of the videos, we actually find the specific format that n must have. If we wish to restrict ourselves to solving the questions, then we can simply note that only a perfect square will have an odd number of divisors
exactly
I don't understand. We show that n^2 (which is obviously a perfect square) has an odd number of divisors, but that says nothing about the number of divisors of n.
@@dmhouse1024 Hope you might still get this. Nice observation. You are right that it doesn't fully prove it, but it does give something important. n^2 has an odd number of divisors.
Firstly, all the divisors of n are divisors of n^2. They all have factor pair counterparts(of n^2) larger than n. And lastly n is repeated twice(as its counterpart is itself), so we'll have to remove 1. Assuming the number of divisors of n is d, then 2d-1=2017. 2d=2018. d=1009. Which is also odd, therefore d is also a perfect square.
This agrees with Michael's answer too as p^1008 also has 1009 divisors (1,p,p^2...p^1008).
That’s what I initially thought. But 2017 is the number of divisors of n^2, not n.
@@wyseebbah7193 hello, what you said is actually true for squares of only prime powers and not , in general, for the squares of other composite numbers with two or more distinct prime factors. For example, consider 144 = 12^2. 144 has 16 and 9 as divisors and none of them are divisors of 12. Also, 12 has 6 divisors and 144 has 15 divisors which is not 2*6 - 1 = 13. Of course, your explanation matches with Michael's answer because co-incidentally the number, n, in consideration is a prime power.
Amazing solution! Great work!!
The camera setup is so good!
Beautiful problem, and quite accessible. Thanks for curating these gems for us!
Im speechless, im breathless... what a nice problem!
What a cool problem and an even more elegant solution!
I like this solution so much.
Odd number of divisors implies perfect squares can also be proven with bijections :)
Good point. Also, I think this fact is well known enough to state in a solution. That being said, for the purposes of the video I like to illustrate more than necessary.
very well explained and detailed solution.
me encantan tus videos, muy buenas explicaciones 🤘🏻🤘🏻🤘🏻🤘🏻
Excellent explanation.
Maaan, that was amazing! Thank you! Made my day🥰
Why dont you have a lot of subscribers you’re content is amazing!!
This is young channel. I watched him since 5k subsribers. Soon, he will hit 100k subs then 1 mil subs.
Just leave comment and like, so it probably pop up in someone's recommendation :) and subsribe too
Thanks! Last Fall I was excited when I hit 100 subscribers!!
I completely agree. He has great content and deserves lot more subscribers. However, how many people do you think can even understand this question? :)
Keeping up with mathematicians?
Recreational math is also not the biggest audience in the world, and Dr. Penn has to compete against a lot of established channels aimed at various levels like numberphile, 3blue1brown, mathologer, blackpenredpen, and others. So it would be pretty amazing if the channel grew much faster.
Excellent
Wow this is what I have been planning to do~ having two cameras focusing on angles accordingly. About to record with two cameras as well~
Once again, there was a very similar problem on thr British Math Olympiad in 2005. Great solution!
.. But 2005 isn't prime.
Loved the factorization. That's genius, I'd have never thought of that!
Standard Olympiad trick...
This came in 5th grade Olympiad in India.
India india india.
India the best country that has ever existed abd every person born by chance in india is better than everyone else in the world@@TechToppers
Mas videos sobre esto, por favor. Están bacanes!!
Fantastic video.
This was so good
Please try this one
Suppose positive integers m, n, K satisfy mn = K^2 + K + 3. Prove that at least one of the following Diophantine equations x^2+11y^2= 4m and x^2 + 11y^2 = 4n has a solution (x, y) with x, y being odd numbers.
That is a pretty interesting problem. I will check it out.
This is Chinese Olympiad 2006, not an easy problem at all ( unless you use some agebraic number theory ), there is a solution in the AoPS forum, and also in a famous book entiteled "Mathematical Olympiad in China", both uses Thue lemma.
Wow! 2 Cameras! Great Job!
There's a famous puzzle involving a corridor with an infinite number of doors, initially all closed, and an infinite barrel of monkeys. The first monkey runs down the corridor opening every door, the second opens or closes every other door, the third every third door etc.. The doors' state (open or closed) depends on the parity of their number of divisors. The ones that are open are the first, fourth, ninth etc. because only perfect squares have an odd number of divisors (a non-square has at least one odd exponent in its prime factorisation which makes the divisor function even).
Well I'm actually proud of myself because I did figure it out!
This was beautiful
That's a clever exercise, it was fun
This problem, in fact, has infinitely solutions and for all non-zero positive integers, I found some trivial solutions and we can set the equation to be equal to any perfect square c² except 0.
a=b= 2c²
Or
a=c²+1. b= c²(c²+1)
Note: Nice vid ^^
It follows in general for all primes of form 4k + 1
Why doesn't this channel have more subscribers and views?!
This was relatively easy!
I'm speechless...N.I.C.E.
Mr. Penn, you have proven that every natural number N such that there are 2017 specifications of the two natural numbers X and Y such that 1/X + 1/Y = 1/N is a perfect square. It also follows as a corollary that N is a perfect cube and has only one prime factor P, and that N = P^1008, but 1008 is divisible by 3, therefore N is a perfect cube.
Good job !!!
Hey you did it 😊
I do love it... 'this is a good place to stop"
amazing , I like it .
Lovely Swiss cheese and chocolate!
Cheers from Zurich, Switzerland!
voice is excellent 👍 The solution is very nice 👍
Interesting. So it is also true if 2017 is replaced by any product of primes congruent to 1, modulo 4, or, equivalently, any odd number which can be expressed as the sum of two relatively prime squares. For example, 2041=13*157 .
good job
The only natural numbers with an odd number of divisors are perfect squares. Still beautifully illustrative for you to establish that truth via prime factorization! There is famous lock and unlock jail cell doors where the odd number jail cells are the only ones still unlocked........Also that complete the product you did aka Simon's favorite factoring trick(SFFT) is prevalent in Olympiad problems I believe.
awesome
So when you're chosen to participate to an olympiad, you have to check if the year is a prime number or has something special.2022 probably will be next, is it a number with special properties ?
How are we making sure that the 2017 (a-n,b-n) pairs are not just subsets of all possible factor pair of n*n?
So if there exists a prime number (greater than 2) of solutions to 1/a+1/b=1/n then n is square
They really love forcing the date into problems in the various math olympiads. Here we proved that n was a perfect square by first proving that it was a perfect 1008th power. This would have been an excellent problem to ask in the year 5.
Good evening! It is easy to ser that (a-n)|n^2.
b=an/(a-n) . w=a-n ==> w|w-n^2. Só a-n|n^2. As 2017 os prime n^2=p^2016, p is prime. So n=p^1008 and n is a perfect square.
what keeps confusing me is that the prolem text does not exclude the case that there could be more than 2017 pairs (a, b).
This proof is beautiful
How much time should we spend on a questions like this?
LOL
I ENJOYED THAT RIDE !!
Hey man, all i have to say is congrats and thanks for the explanation. Beautiful solution. Perfect explanation. Amazing!
One problem i like a lot, is an old Soviet one (urss Olympiad)
*Find the last 1000 digits of
N = 1+50+50^2+...+50^999
This is just a basic modulo arithmetic with geometric series
1
On the last part, a easier solution would be to see that the number of divisers is odd. Numbers can be divided in the form a*b, so the number of divisers (its pairs of numbers) should be an even number. So to become odd, one of the number must repeat one time. like Number= a*a. So the number must is a square. i find it to be a more elegant solution.
Yeah but this solution gives us an excuse to use the prime factorization to number of factors formula
Great.
That factorising method, also known as Simon's Favourite Factoring Trick is so amazing.
Thanks
Is there any book i can read to learn more about these solving tricks . Thanks in advance
@@andersen9044 get the Art of Problem Solving books. You can get it from their official website.
@@andersen9044 Art and Craft of Problem Solving by Paul Zeitz is a great book.
Here is AoPS link for Simon's Favourite Factoring Trick.
artofproblemsolving.com/wiki/index.php/Simon%27s_Favorite_Factoring_Trick
am i missing something or is pefrect square not what i think it means (all x=n^2 for n e N) ? (non english native) but in my mind as soon as you have the bijection to divisors you are done because 2017 is an uneaven number and you can only ever get uneven number of divisors if it is self replicating(for n>1) and self replicating means the original number must be a "perfect square".
Is factor pair (a,b) same thing as factor pair (b,a)? Or order matters here?
Good video .
Try this problem:-
If curves C1: x^2+y^2=32 and C2: y^2=4x at A and B . Tangents are drawn to C1 at A and B which intersect at C also tangents are drawn to C2 to A and B which intersect at D . The ratio of areas of the triangles ABC and ABD is ?
Its not an olympiad problem . It just came in a test
Thanks, I'll take a look!
Wow. So accurate.
Do we even need the fact that 2017 is prime? It seems that any number with an odd number of divisors must be a perfect square (all its prime factor exponents must be even, otherwise the product of their +1s would be even).
1/a + 1/b = 1/n so a = b*n/(b - n) = n + n^2/(b-n) thus solutions are given by b - n = D or equivalently
b = n + D and a = n + n^2/D where D is a divisor of n^2.
Distinct pairs of (a,b) are generated by divisors D of n^2 such that D n you get the same pair in reverse order. For example D =1 gives b = n+1 and a = n + n^2 while D = n^2 gives
b = n + n^2 and a = n + 1.
Therefore the number of divisors of n^2 which are less than or equal to n must be 2017 and the total number of divisors of n^2 must be 1 + 2* (2017-1) = 4033 = 37*109 so n must have factorization
n = p1^r1 * p2^r2 where (2*r1 + 1)*(2*r2 + 1) = 37*109 consequently (r1, r2) = (18, 54) and since both powers are even we conclude that n is a perfect square.
Try this 2019 IMO question:
Find all (k , n) such that k! = (2^n - 1)(2^n - 2)(2^n - 4)...(2^n - 2^n-1)
I'll check it out.
One of the prettiest questions lol. I really put an effort on it and although I am junior I was able to solve it 😂I am sure Penn will find a shorter solution
@@electrovector7212 why don't you try the problem I have put in the comments
I smell valuation p-adique there
i can see here some Legendre's theorem and n-adique stuffs
isn't n actually "better" than a prefect square, since n=(P^63)^16?
I didn't understand in 10:24 why did he multiply (2ri+1)....?,
I feel stupid.
When (k,l) solve s.t=m, then (l,k) solve it. If m is not a square, there is no solution (k,k) i.e. there is an even number of solutions. As we have an odd number of solutions, m has to be a square.
I like the prime factoring exercise, but is it necessary at all?
Interesting problem
I’m curious as to what your opinion on the Project Euler problems is. It seems to me to be an interesting mix of both problem solving as well as computation for answers.
More like good for learning programming than math
Thanks for mentioning Project Euler! As a computer programmer with degrees in Applied Mathematics and Mechanical Engineering (2) who broke into the top 500 on the Purnam Exam my last two undergraduate years, those problems hold a particular interest for me. The problem shown in this video was amazing also. I feel that solving these kind of problems gives one a dogged determination that is hard to come by via other means. This channel is a joy to behold. Thanks.
Your solution is waaaay better and slick than mine. I solved it in a bit of a round about way. Assume gcd(a,b) = 1. We know that na + nb = ab which means both a and b divide n as gcd(a,b)=1. However, n/a + n/b = 1 which is impossible given that they are all positive integers, and both a and b divide n. So we m_ust have that gcd(a,b) > 1. Let a = ga' and b= gb' where g = gcd(a,b). Then we get na' + nb' = ga'b'. From this equation, we can see that a' and b' divide n as gcd(a',b')=1, and for each such pair of relatively prime numbers (a',b') where they both divide n individually, you can set g = (n/a' + n/b') to get a unique pair of solutions (a,b). So the problem boils down to counting the number of ordered pairs (a',b') such that they are relatively prime, and are each a divisor of n. As a counting problem , the answer ends up being exactly same as counting the number of divisors of n^2 :).
This was how I ended up solving it, too. Not quite as elegant as in the video but a similar line of reasoning.
You could make videos about college olympiads.
You explain very well. You should make videos of Complex Analysis, Real Analysis, Abstract Algebra, Linear Algebra, Vector Calculus, Multivariable calculus, Algebraic Geometry and other topics.
I already have full playlists of abstract algebra and multivariable calculus!
We can notice that a,b > n
So a = n + c and b = n + d
1/(n+c) + 1/(n+d) = 1/n
(n+c)n + n(n+d) = (n+c)(n+d)
n(n+n+c+d) = (n+c)(n+d)
2n^2 + n(c+d) = n^2 + n(c+d) + cd
n^2 = cd
And that leads to the same conclusion
Wow good video
27 seconds ago, new video :)
Clever ^ 4
Please do the Romanian maths Olympiad problem that I suggested previously.thank you😀
Can someone explain me that,
As there are 2017 ordered pair a,b such that (a-n)(b-n)=n^2 how does this proves that n^2 has 2017 divisors.
2017 is given. Confused me at first too.
n=Prod_i p_i^{r_i}. Then #(divisors of n)=Prod_i (r_i +1) is odd iff all r_i +1 are odd iff all r_i are even, i.e. n is a perfect square.
solutions are in bijection with the divisors of n^2, no? You have only shown that n^2 is a perfect square.
@@tracyh5751 Yeah, you're right. I just wanted to state that the number of divisors of any number is odd iff that number is a perfect square. Has nothing to do with that problem here. For that you need #solutions=2017 or any other prime congruent 1 mod 4.
Thanks for ur videos
I've uploaded all imo problems of 2021 and 2020 and I will upload the past years soon
I've also uploaded national olympiads of USA,UK,Switzerland,Belgium,Luxembourg,Netherlanda,Indonesia,....
Wow - two camera setup now!
Really enjoyed this this problem. Have worked through similar ones in the past myself.
Very good problem. Thank you for a clear explanation! Here is a beautiful puzzle:
Cheryl’s Birthday Puzzle
(Wiki) Cheryl’s Birthday is the unofficial name given to a mathematics brain teaser that was asked in the Singapore and Asian Schools Math Olympiad, and was posted online on 10 April 2015 by Singapore TV presenter. It is an interesting problem and might be asked in the interviews. It is based on logical deduction. It doesn’t require any prior mathematical acumen. It is advised that you try to hustle through the problem yourself without looking at the solution and just to motivate you further to solve the problem, the problem has been talked about in international newspapers like Telegraph and Guardian, so If you are able to solve the problem without looking at the solution you deserve a pat on the back!
The problem:
It is known that Cheryl’s birthday is one of the following 10 dates listed below.
May 15,May 16,May 19,June 17,June 18,July 14,
July 16,August 14,August 15,August 17.
Cheryl tells Albert and Bernard separately the month and the day of her birthday respectively.
Then following conversation takes place
Albert: I don’t know when Cheryl’s birthday is, but I know that Bernard doesn’t know too.
Bernard: At first I didn’t know when Cheryl’s birthday is, but I know now.
Albert: Then I also know when Cheryl’s birthday is.
So when is Cheryl’s birthday?
Answer: ....... (you can find the complete solution online)
This was a viral problem when it came out. I think Numberphile did a video on it.
May 19??
Does this proof work for any natural number subbed in for 2017? Does it only work for prime numbers?
I was thinking halfway through that he was going to pull in 2017 as an odd number to complete the proof, not that 2017 was prime. But he has a habit (fully confessed on the channel) of using convoluted methods to prove a perhaps simpler problem, if only for the purpose of pulling in more concepts to make the video more interesting.
It works for number of solutions = 4k+1. The factorization of 2017 is irrelevant, but 2017-1 must be a multiple of 4.
n = p^2k is a perfect square as required.
n^2 = p^4k has 4k+1 factorizations. The (a,b) are
a = n+p^i,
b = a n / (a-n)
= n+n^2/p^i
= n+p^(4k-i)
with i = 0 to 4k.
At i=0, a=n+1, b=n(n+1).
At i=2k, a=b=2n.
At i=4k, a=n(n+1), b=n+1.
Yes, it's hard. But looking at the solution, you can see that is not impossible, actually. Nice Video :)
What if there are 2016 solutions?
Is reverse statement true ? Let p be an arbitrary prime and n=p*1008, then the mentioned equation has exactly 2017 solutions?
Just go through the argument backwards and see if you have implications there as well.
I approached the problem like this
1/a + 1/b = 1/n
na+nb = ab
na = b(a-n)
b = an/(a-n)
=> b = n + (n²/(a-n))
n²/(a-n) must be natural, hence
(a-n)|n²
but that means n|a (necessarily)
What that means is that each solution pair (a,b) corresponds to a factor pair of n²
What that tells us, is that n² has 2017 factor pairs
so if
n = p1^e1.p2^e2.....pk^ek
n² = p1^2e1.p2^2e2.....pk^2ek
since n² has 2017 factor pairs
(2e1+1)(2e2+1)(2e3+1)...(2ek+1)=2017
(2e1+1)(2e2+1)...(2ek+1) = 2017
=> e1 = 1008 (2017 is prime)
n = p1^e1 = p1^1008 = (p1^504)^2
n is a perfect square.
n sometimes divides a, but not always. For example, suppose we want d = 7 solutions. Then n^2 must be chosen to have 7 divisors. These will be p^0, p^1, ..., p^6. For p = 2, these are 1, 2, 4, 8, 16, 32, 64, and n = 8 = p^3, n^2 = 64 = p^6 = p^(d-1). The 7 (a,b) ordered pairs are {(9,72), (10,40), (12,24), (16,16), (24,12),(40,10), (72,9)}. n = 8 divides a = 16, 24, 40, and 72, but not a = 9, 10, or 12.
@@edwardhuff4727 I stand corrected, thanks for your input!
You are so cool! :D