International Math Olympiad | 2006 Question 4
HTML-код
- Опубликовано: 23 дек 2024
- We present a solution to question 4 from the 2006 International Mathematics Olympiad. This problem involves determining when a certain combination of powers of 2 is a perfect square.
Please Subscribe: www.youtube.co...
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
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...
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
A classical number theory equation. I loved your clear explanation.
Motivation for question: 1. Try some values that makes sense to you. Especially in the number theory questions we generally take some little values and continue our way to search for other solutions. 2. Factoring is a good way to solve these type of equations. It is clear that we can factorize y^2-1 and tried and reached our solution. If it hadn't worked, we would have tried to prove x is even and could factorize y^2-2^x. But we know a little bit about the prime divisors of 2^(2x+1)+1 so it doesn't make sense too.
8:00 Or in short: Distinct multiples of 4 differ by at least 4, hence one of two consecutive even numbers is not a multiple of 4
Yeah, much simpler way to see it
19:20 m=1 only since m=3 is greater than 8
Yupp, exactly. And he skipped the m=1 case, because obviously it satisfies the equation which he derived for m^2≤8 (they're equivalent). You have to plug it back into the original equation to see that m=1 doesn't solve it.
alternate proof for the x>=0 case: let u=2^x. we have the product u(1+2u)=(y-1)(y+1) and y^2 = 2u^2+u+1 > 2u^2, which means y > sqrt(2) u. From the product, we can split the cases that either all odd factors of (1+2u) belong to (y-1) or to (y+1) or they are split between the two.
Case 1: 1+2u divides y-1 strictly because y-1 has at least one even factor, then u > y+1 to maintain the product. Then u > y+1 > sqrt(2) u + 1 which has no solutions.
Case 2: Same argument as Case 1 with the signs changed. End with inequality u > y-1 > sqrt(2) u - 1. Can only happen when u = 1 and u = 2, corresponding to x = 0 and x = 1.
Case 3: Both (y-1) and (y+1) are missing at least one prime factor of (1+2u) and one of these terms has only one factor 2. say it is (y-1). Then you get the inequality (y-1)/2 < (1+2u)/3 yielding
4/3 u +5/3 > y > sqrt(2) u. The possible values of u are u
Just making sure, you did just say that 3^2
I thought I was going insane
He said that .. your are not going bonkers....
You ad to stick around for the whole thing to catch it :)
Where?
@Alain R: He made this mistake at about 19:23. However, as Michael Penn points out, m=3 does not yield solution(s).
I took a different path from about 10:00 onwards:
Have {y-1, y+1} = {2a, 2^(x-1)b}, with a,b odd.
Note that y ≥ 2^(x+1) implies that y² = 2^(2x+1) + 2^x + 1 ≥ 2^(2x+2), so 2^x + 1 ≥ 2^(2x+1) = 2^2x + 2^2x, implying x = 0. That gives the (0, ±2) solution.
Otherwise y < 2^(x+1), and y = 2^(x-1)b ± 1, with b odd. So b is 1 or 3.
If b = 1, y = 2^(x-1) ± 1, so y² = 2^(2x-2) ± 2^x + 1 < 2^(2x+1) + 2^x + 1, so b = 3.
We know that ab = 2^(x+1)+1 because ab.2^x = y².
Also 2a = 2^(x-1) * 3 ± 2 because y+1 and y-1 differ by 2.
So:
3a = 2^(x+1)+1
2a = 2^(x-1) * 3 ± 2
6a = 2^(x+2)+2 = 2^(x-1) * 9 ± 6 = 2^(x-1) * 8 + 2^(x-1) ± 6
Which gives 2^(x-1) = 2±6. So x = 4, giving the remaining (4,±23) solution.
7:46 Shouldn't the gcd divide 2?
Absolutely! So gcd is either 1 or 2. But since y-1 and y+1 are both even, it follows that gcd=2.
@@johnvandenberg8883 Yeah his statement was wrong, but his reasoning was right
@@JM-us3fr Agreed
There is also a "brute force" solution. Rule out all but x>=3. Subtract (2^(x-1) + 1)^2 from both sides and simplify the lhs and use the square rule on the rhs. We then get 2^(2x - 2) * 7 = (y - 2^(x-1) - 1) (y + 2^(x-1) + 1). Next, write y = 2^d v + 1 for an uneven v and insert to get:
2^(2x - 2) * 7 = 4(2^(d-1) v - 2^(x-2) ) (2^(d-1) v + 2^(x-2) + 1)
It is now a matter of considering which factor is uneven and thus equal to 7. I first ruled out v = 1 (this can be done using the orignal equation), then we consider d > 1 (in which case the second expression is equal to 7 which is easily ruled out) and finally d=1 in which case 7 = 2^(d-1) v - 2^(x-2) = v - 2^(x-2), at which point we can easily simplify and get x=4 as the only possible remaining solution.
I’m a beginner in number theory, but once I saw that you factored (y+1)(y-1), I could solve the rest of the problem by myself, so I’m quite happy, I learned something today!
For Case 2, where y-1 = (2^(x-1))*m, where m >= 1 and is odd, you obtained the inequality, after rearranging and factoring on both sides, the following: (m^2)-8
>> You list the possible solutions as m=1 and m=3, but m=3 …
… is IMMEDIATELY not a solution of m^2 ≤ 8. Because for m=3, clearly m^2 = 3^2 = 9. He made a "typo" mistake.
For m=1, you probably have to plug back in to the original equation given in the problem.
Upload more imo problems,please cover the geometry part also
19:23 - since 3*3 is already equal to 9 and bigger than 8, you should not have written m = 1 or 3.
Totally agree, noot sure where he got the 3 there, and even if there are some comments bellow that it was a slip I dont think that it is acceptable excuse for this kind of math.
I was struggling to understand logic at 7:20 to show that gcd (y-1,y+1)=2. Here is what I came up with:
Since y-1 and y+1 are even, 2 is a common divisor of both. Thus gcd(y-1,y+1)≥2. It is also easy to prove that for and positive integers x and n, gcd(x,x+n) divides n. So gcd(y-1,y+1) divides 2, meaning gcd(y-1,y+1)≤2. So 2≤gcd(y-1,y+1)≤2 implies gcd (y-1,y+1)=2.
OMG, at 19:30 you're saying 3²≤8 haha. We all make those mistakes 😂
1:43 both terms should be less than *or equal to* 1/2 , isnt it?
The hints are very helpful in this one !
I have a nice question I had for an oral to enter a french university
Find one function f ∈ C∞(ℝ) such as for Ɐn ∈ N, the n-th derivative of f verifies f(n)(0) = (n!)^2(-1)^n (f(n) means the n-th derivative)
The problem to solve is much harder than it thinks since you need the function to be C∞(R) and not only C∞(]0,+infty[) !
You can probably define the Taylor’s function with the help of the given data asymptotically around x=0 that might be analytic and will belong to Cinfinity
Angel Mendez-Rivera tjxjjdjdjjdjd
@@angelmendez-rivera351 it's true Borel lemma gets you a solution instantly and it's nice maths. In the context of this exam however, it was probably unusable
Edit : but maybe the examinator wanted to go for a Borel like proof, I'm not able to find a simple solution
omg, thank you so much for solving this one, I was constantly searching for a solution but couldn't find any
AoPS is a great place to search for solutions to questions (you can find solutions + discussion for this question at artofproblemsolving.com/community/c6h101485p572815 ). It takes a bit of practise to navigate the site to find the question you want, but it's really useful once you've learnt to use the site well.
7:23 This should be gcd(y+1,y-1) divides 2, not the other way around.
Ohh .. I see you are a man of culture as well.
The reason for this is that difference between them 2 biggest one should divisible by 2 but not 4. Example, 8 and 10, gcd is 2.
The inequality 1
Yeah true
I'd consider it a math error because he failed to consider all the cases. Like if he was being graded (at university level or IMO level), he wouldn't get full marks with that solution.
Can we do something like this?
We'll take 2^x =u. Then 2^2x+1 =2.2^2x. Take y^2 on the other side and the equation becomes quadratic . Use the quad equation to find u. Make discrimnant > =0 . Find condition for y and check for which value satisfy u>0 as 2^x>0?
Can you recommend me any books to start practicing with IMO (international math Olympiad
At 19:43, why is m=3 possible if m^2
Could we get some geometry problems please??
MindYourDecisions has plenty of geometry problems.
Or Osman nal channel
You mean gcd(y-1,y+1)|2 not the other way around.
What about 2*(2^x)^2 +2^x +1 - y^2= 0
The discriminant is 4y^2-7 and it must be a perfect square so 2^x is rational (if x is rational, then it follows that 2^x is rational). 4y^2-7=s^2
(2y-s)(2y+s)=7
And now we find the values for s and y and plug them in 2^x to find all solutions. This seems very simple. Does it work?
Edit: my bad, it should be 8y^2-7=s^2
If you include limiting behaviour (-inf,1) and (-inf,-1) are solutions
ya but infinity isn't an integer
love the white board syndrome being fixed in post at 2:18 i feel this on a physical level and can imagine one of the kids I tutor calling out that exact mistake as a gocha
Why can't you say that when 2^x * (1+2^(x+1)) = (y+1)(y-1) and since 2^x < 1+2^(x+1) and y-1 < y+1 you set 2^x = y-1 and 1 + 2^(x+1) = y+1?
2*9=3*6 2
greatest math guy on the internet !!
Dear Michael, I've noticed a minor typo: "evenness"
19:20
doesn't 3 not satisfy the inequality?
The 1-m would be -2, the right side would be 2^1(9-8)=2. Since 3^2 is 9, and 9>8, m=3 should not have been considered
19:41
You may assume 2^ x= z,this the left side becomes 1+ z+2z^2 =y^2 an even number that is possible for z=1and hence x=0,y=2.
if (y^2) is even, how can (y^2)-1 be even also
y cannot be even.1+ 2^(2x+1)+2^x is odd. So y² is odd. Thus y must be odd.
Is it just me or these types of problems have one way of doing it? (I dont know how to formally explain what i mean by "These types" but the ones that appear in olympiads and asks us to find x,y)
At 7:55: why not 4?
Tell me anyone why either y plus or y minus 1 is divisible by 2 I think they both are divisible by 2 since there gcd is 2 and gcd divides both the numbers
Awesome video bro 👌👌👌......
Can you please solve this question
I am not able to solve it
Problem : find all pairs (m,n) of positive integers such that both of (n^2+1)/2m and √(2^(n-1)+m+4) are integers
This is a good question.. I'll try that out
Pretty simple. Divide cases and observe that 2m is even for all m, n^2+1 is odd or even depending on n, but 2m is a factor of n^2+1 => n odd always. Try m=1 => n=1 works for the first one but not for the second. m=2, find all n such that 4| (n^2 +1) ...
@@mathissupereasy I've been working on solving it and so far I know that n is odd and greater than or equal to 3, and I know that m is odd. I also have found the solution (3,1) but I can't figure out whether there are more solutions or not and how to find them.
1. n^2 + 1 = 0 mod(2), n^2 = 1 mod(2), so n is odd
2. n is odd, so n = 2k+1, where k = 0, 1, 2... (k is not a negative, k is integer). In this case, (n^2+1)/2m = (4k^2 + 4k +2)/2m = (2k^2 + 2k + 1)/m. √(2^(n-1) + m +4) = √(2^(2k+1-1) + m +4) = √(2^2k +m +4)
3. (2k^2+2k+1)/m => m ≤ (2k^2+2k+1)
4. We know that √(2^2k + m + 4) is integer, so 2^2k + m + 4 = a^2
m + 4 = a^2 - 2^2k
But 2^2k = 2^k2 = (2^k)^2, so
5. m+4 = (a)^2 - (2^k)^2 = (a - 2^k)(a + 2^k). By 3., m ≤ (2k^2+2k+1), so
2k^2 + 2k + 5 ≥ (a - 2^k)(a + 2^k)
6. We know that k, m, a ≥ 0, so 2^2k + m + 4 > 0, so (a-2^k) > 0 and (a-2^k) ≥ 1. Also, a+2^k ≥ 2^k.
In this case, if 2k^2 + 2k + 5 < 2^k => 2k^2 + 2k + 5 < (a-2^k)(a+2^k)
7. If you know derivative, it's easy to prove that if 2^k is greater than 2k^2+2k+5 starting at some point - for example, point K, so 2^k is greater than 2k^2 + 2k + 5 for any k > K.
8. By 7., look at k = 10. 2*100 + 2*10 + 5 = 225, 2^10 = 1024. 225 < 1024, so all k >10 do not fit this equation.
9. Last thing that we need to do is check all k from 0 to 10 (but we checked 10 yet), so
k=0, n=1, m=1, but sqrt(1 + 1 + 4) is not a integer
k = 1, n is 3, m is 1 or 5; sqrt(4+1+4)=3, sqrt(4+5+4) is not a integer, so only (3;1)
k=2, n =5, m = 1 or 13. sqrt(20+1) and sqrt(20+13) is not a integer
k=3, n=7, m=1 or 5 or 25. sqrt(68+1), sqrt(68+5) and sqrt(68+25) is not a integer
k=4, n=9, m=41 or 1. sqrt(260+1) or sqrt(260+41) is not a integer
k=5, n=11, m=1 or 61, sqrt(1028+1) is not a integer, but sqrt(1028+61) is a integer, so only (11;61)
k=6, n=13, m = 1 or 5 or 17 or 85. sqrt(4100+1), sqrt(4100+5), sqrt(4100+17) and sqrt(4100+85) is not a integer
k=7 - you know, 2k^2+2k+1 = 113; 2^k = 128. So, by 7., k=7, 8, 9... do not fit this equation.
Answer: (n=3, m=1); (n=11, m=61)
P.S. sorry for my english, it is not very good
ooopsi gt n^2+1 and square root of... go together or 2 separate problems?
I've got a feeling that there's some clever way of looking at it with base-2 arithmetic.
I just want to mention your physique: one can see that you work out, but you keep it on a normal healthy level. Thats inspiring!
Can someone confirm if this is correct/explain how this solution is the same?
Set a=2^x
Then 1+2^x+2^(2x+1)=y^2
Is the same as 1+a+2a^2=y^2
This factors into a(a-1)=(y+a+1)(y-a-1)
Since both terms on the right must have a two, divide both sides by 4.
So the product of a/4 and a-1 have to be represented by 2 factors with a gap between factors of a+1. The smallest increase in the gap is greater than a+1 for x>6=a>64. This is because a/4 goes into a-1 just over 4 times. To lower a-1 till it can reach 5 times will lower it by what approaches a factor of 4/5 which means the minimum increase is a factor of 5/4. So after first time it doesn’t work at x=7 the factor only gets closer to 5/4 and higher so the smallest increase will be too large a gap.
Then you can check from x=0 to 6 to find x=0 and x=4 work.
Idk if this is simpler, but I’m curious if it’s trivially the same or a different approach. Or is there a flaw in the proof?
No doubt sir your exquisite solution will help students
Hello from the futer man! Thanks so much!
Actually there is sol when x
Excellent explanation.
Your demonstration is perfect. Good for you M.Penn !
19:23 m cannot equal 3.
1+2^{x+1} = 2^{x-2}m^2 \pm m > 2^{x-2}(m^2-m), so 2^3 >= m^2-m leaves just a handful of candidates for m
What you call "hints" i call it "spoilers" lol
Thank you for this amazing content
19:29 m=1 or m=2 and not 3
When I solved it, I tried factoring, but worked myself into a loop. So I scrapped it and instead looked at the possible binary expansions of y and y^2. With that approach I also found the trivial base cases and +/-y = 2^4 + 2^2 + 2^1 + 2^0 = 23.
Could you elaborate on how to do that?
Can u please explain it in depth?
Give us the deets
I have a question... Gcd of 2 even number can also 4 or 6 or any greater even number. So how can we take 2 as the gcd for those two?
They can't be both multiple of 4 (means their gcd cant be 4) because there is only 1 multiple of 4 every 4 numbers but these numbers are only 2 numbers apart. But they can be both multiple of 2 because they are 2 numbers apart and are even
The first inequality is wrong. If x can take the value -1, then the value of 2^x is not strictly less than 1/2.
I worked with y^2 - (2^(x-1)+1)^2 because I noticed that 2^(2x+1)+2^x+1 has two terms of a perfect square namely 2^(2x-2)+2^(x-1)+1.
After some calculations I worked out that then (y-2^(x-1)-1)*(y+2^(x-1)+1) = 7*2^(2x-2), which leads to a case distinction of which term is 7 times a power of 2, and which term is a power of 2.
In the end I reached the same result, so yay! :P
same!!
Pulling the 1 to the RHS was inspired. I started factoring the LHS. Put u=2^x. Then get (2u-1)(u+1)=y^2. But half an hour later, no solution!
A slightly different solution has been uploaded today. Kindly consider
Where is the time machine???
1+2^x+2^(x+1)=y²
Or, 1+2^x(1+2^(x+1))=y²
Let 2^x = m such that m is an even natural number
Also , y is always odd (Since (y+1)*(y-1) is even)
Then y=2n+1
First checking for 0 , we get (0,2 and 0,-2)
Now substituting x and y as m and n
m(2m+1)=4n(n+1)
So , m>=4
Also , m is a multiple of 4
Also , m(2m+1)/4 is a pronic number (n(n+1) is a pronic number which is the product of consecutive natural numbers)
So 2m+1 cannot be prime
Now for m=8,12 , 2m+1=17,37 which is prime
And for m=4 , equation doesn't satisfy
Hence m=16
And solving it n=11,-12
Hence x=4 , y=±23
And x=0 , y=±2
I know this method is a lot of hit and trial and is a bit shaky - but it provides the solution anyways...
This guy won the gold medal.
X=4,y=7?
what does the SSC on your T-shirt mean?
SCC
Nice! I got Bronze in that competition :)
be humble..people like me who were interested in maths and couldnt make it to imo team feel bad...
Adam Romanov thanks very much! I really love this Channel! I learn a lot of things here :)
qwerty yuiop Don’t worry dude I didn’t even make it to selection phase.
@Adam Romanov man.. even i dont care about my "stupid arse" feelings... it was tongue in cheek reply...😂😂😂
and yeahh ...i always did maths because it was fun...not just to get some medal or something...medal is always better but good for
leandro..
@@aptilious2774 I am just before it. Well, not for math, but for computer science, but tomato tomato. God I am stressed.
One very easy IMO problem, the appetizer number 4 of that day 2.
I couldn’t solve what should I do?
Which class
Good evening!
It is easy to show that for x0 ==> y odd so gcd(y+1,y-1)=2
2^x(2+1)=(y+1)(y-1)
2^(x-1)*(3)=(y+1)*(y-1)/2
(y-1)/2=3 ==> y=7 then 2^(x-1)=8; x=4
(4,7) ia a solution so (4, -7) either
(y+1)/2=3==> y=5 then 2^(x-1)=4; x=3
(3,5) and (3,-5) are solutions.
And that are the only solutions.
Question 5 pls
But why y-1 and y+1 divise by 2 and not by 4 ?
They're consecutive even numbers, so they both can't be divisible by 4. One is surely going to be divisible, however. Try small cases like 8 and 10 or something to convince yourself. :)
They can't both be divisible by 4 (equal to 0 modulo 4) because they differ by 2 modulo 4.
Thanks teacher for this video
Using Log or Ln would shorten the solution.
liked your beautiful solution
Pls solve other 2006 imo problem plzzzz
A little nitpick, but at ruclips.net/video/wviiZlYRaGE/видео.html you say that x 2^x < 1/2. This inequality is not strict, but in the end that doesn't change anything. (as there is no integer y such that 1 < y^2
Dude since when 9 -8
Believe me or not but this is my favourite diophantine equation and i have solved it maybe a thousand times...lol
m=3 doesn't satisfy m²
(0,2) ,(4,23) I guessed only these solutions
What about x = 3, y = 5
If x = 3, the LHS becomes 1 + 2^3 + 2^(2*3+1) which equals 1 + 8 + 128 which gives us 137. You probably forgot to multiply the x by 2 on the second exponent.
that would give 1+2^3+2^7 = 137 =/= 25. It would be the solution to 1+2^x+2^(x+1) = y^2
x=-infinity, Y=_+1 is an obvious solution too!!
This why I prefer to choose language class
I always thought those Olympiad problems are unsolvable for me - fortunately I was wrong, as Michael has proved now multiple times (OK, so far I have to find a solution really by myself - but I'm convinced now I can...).
So far I also wasn't aware that 3^2 is < = 8...
Great explanation ....Xmas
Thx. International Olympic maths not so hard than we think.
as y^2 is always nonnegative so the L.H.S will be nonnegative. so directly x will be positive .my doubt is do this point require proof
if we put - 1 for x we got 1+1/2+1/2 = 2 actually left side is positive for all x values
Try this:
Set 2∧x ＝ g
LHS ＝ (1+g)∧2
RHS ＝ Y∧2
Thus, solve abs(1＋g) ＝ abs(Y) to get the answer.
never mind. I miss readed question.
Arthur Nogueira omg you are right.
Impressive
Outstanding 🔥🔥
x=0, y=2 for 15 sec
Wow nice efforts..
@Nirupam DebNath isn't it obvious
X=0 y=2 ❤❤❤
Less than 1 minute in and already an advert. RUclips is so crappy now. Save the ads for viewers of soap clips or other vacuuous pap - some of us are trying to learn something.
Considering the infiniteness of integers, it makes me sad that no solution exists for x>4.
I think the answer is x=0 and y=2
X=0,y=2,y=-2
x=4
y=23
if you go on trying after x=2 and x=3, you will just find all the solutions xd
-but not a complete solution by that. This was a difficult point for exercises by proof for me always. Knowing some complex analysis and combinatorics helps, but you still need the foundation in building proofs to see how to pull out something rigorous. He missed some simplicity, and did half a board of algebra working it longer, but it was comprehensive all the same.
Ok, great.
Wow
okay so Zuckerberg is really good at maths
What do you do when it is 1 + 2^x + 3^(2x+1) instead of 1 + 2^x + 2^(2x+1)? Then the whole thing won't work. My point is these questions have been designed in such a way that you necessarily have to lucky-guess the way to the solution. All this happens under time pressure at the olympiads. To me, this is not mathematics... If you're lucky enough to guess your way towards the answer then you're in. But if you really want to do Math, which for me is a creative thought process, abstraction, modelling, rigid logic and discovering something about the real world (no, Math is not disconnected from reality)...? This question here is a good example for a whole host of questions where the situation is that the creator of the question basically says "If you manage to think exactly as I thought when I made up the question then you'll be rewarded with points and if not you can go home right away". There is nothing Math about this. It could be music (I give you 9 bars of notes and you have to complete the 10th bar and you'll get points only when the bar looks exactly like the one I would have put there) or poems (What meaning did the author put into this poem?) or paintings... I don't know exactly what the point of these olympiads is (I took part in several during my teens) but it certainly cannot be promoting Math or discovering future prodigies...
🥴🥴🥴🥴🥴🥴🥴, head blew up
Instead of correcting your calculation/transcription mistakes in post-production, why didn't you just shoot the video over again, mistake-free -- or just re-shoot the segment that had those mistakes and splice that refilmed segment over the blooper segment?
W