An awesome number theory contest problem
Вставка
- Опубліковано 20 вер 2024
- 🌟Support the channel🌟
Patreon: / michaelpennmath
Merch: teespring.com/...
My amazon shop: www.amazon.com...
🟢 Discord: / discord
🌟my other channels🌟
Course videos: / @mathmajor
non-math podcast: / @thepennpavpodcast7878
🌟My Links🌟
Personal Website: www.michael-pen...
Instagram: / melp2718
Randolph College Math: www.randolphcol...
Research Gate profile: www.researchga...
Google Scholar profile: scholar.google...
🌟How I make Thumbnails🌟
Canva: partner.canva....
Color Pallet: coolors.co/?re...
🌟Suggest a problem🌟
forms.gle/ea7P...
It should be m+1 at 4:58
That's exactly right ✅! And it would have been okay to prove by induction that m+1=2.
Just for fun: the limit as n approaches -∞ is 1, which is a square.
I suppose he missed a solution then lmao
2^n yes, but not (n-1)*2^n, the limit is still -inf
@@rocky171986 2^n grows much faster than n, so the division goes to 0, leaving the +1. That's a standard limit technique.
@@jursamaj Alternatively,
let m = -n, so the limit is -(m+1)2^(-m) as m approaches infinity.
= -(m+1)/(2^m) as m approaches infinity
L’Hopital now gives -1/(ln(2)2^m), which clearly approaches 0 as m approaches infinity.
@@DavidSavinainen Yup, different method, same result.
9:00 The factors *m* and *m+1* are relatively prime, so we can combine both cases:
- *2^{n-2}* divides either *m* or *m+1* . In both cases, we have *2^{n-2} ≤ m+1*
- The other factor divides *n-1* . In both cases, we have *m ≤ n - 1*
For both statements to be true, we need to have *2^{n-2} ≤ n* . Via induction this is only true for *n ≤ 4*
"n equals 1 is zero" Michael Penn, 2022
Deepity or Derpity, you be the judge
Nx4-4 is easier for finding squares
From 1-n
4:48 1-n=1+m not m-1. Although the proof is the same
Actually, it should have started with 0 < -1-n < 2^n. So the error was earlier and m-1 is correct.
5:17 Classic Michael Penn induction
14:03 Good Place To Stop
2:15 Spoiler ;)
Inside out t-shirt
You're the best, Michael!!!
I have a little question: (n-1)2^n + 1 has to be an integer? Because it could be, for example, a number like 16/49 that is a perfect square.
A bit easier way is to look at (n - 1)*2^n as a product of two consecutive even numbers:
(n - 1)*2^n = a*(a+2), n >=2.
Then, there are two cases depending on which one of a, a + 2 is divisible by 4.
Case 1: a = b * 2^r, b is odd, r > 1. Here r > 1 because a is divisible by at least 4. Then,
a + 2 = 2 * (b * 2^(r-1) + 1)
Then, we see that
(n - 1) * 2^n = 2^(r + 1) * b * (b * 2^(r - 1) + 1)
From this it is clear that
n = n - 1
We also use that b >= 1, so we have the inequality:
(n - 1) * 2^n >= 2^n * (2^(n-2) + 1)
This can be simplified to
n - 2 >= 2^(n-2)
This inequality is false at any n >=2.
Case 2: a + 2 = b * 2^r, b is odd, b >= 1, r >=2.
After using similar logic we get:
n >= 2^(n - 2)
This is only possible for n = 2, 3 or 4.
Then, by substitution we find that only n = 4 yields the solution among n >=2.
yes but how do you know that (n-1)*2^n is a product of two consecutive even numbers?
@@backyard282 assume (n-1)*2^n + 1= m^2
then (n-1)*2^n = m^2 - 1 = (m-1)(m+1)
since we know that m^2 has to be odd (as the video showed), then m must also be odd, and so m-1 and m+1 are the two consecutive even numbers on either side of m
Cool
I've basically figured it out... I have
(n - 1)2^(n-2) = k(k+1) for some integer k. Now either k or k+1 must be divisible by 2^(n-2), because 2 does not divide the other factor. This works out for n=4, but if n starts getting too big...
For big enough n, n-1 < 2^(n-3), so the LHS < 2^(2n-5). However, either k or k+1 will be divisible by 2^(n-2), and therefore k > 2^(n-2), and the RHS > 2^(2n-4) so we've reached a contradiction. The RHS quickly outpaces the LHS. This is very crude but it works even if n is still quite small.
Like, if n=8, then the LHS is 7*2^6, which means k >= 2^6, which means k(k+1) >= 2^12, and this discrepancy grows as n grows.
What about breaking it into difference of squares k minus 1 times k pkus q and set each factor equal to 2^n or (n-1)..you can solve that way
About the negative case, I wonder what happens if instead of integer perfect squares, we're talking about rational perfect squares ? By that, I mean rational numbers whose square roots are also rational. 4/9 is a rational perfect square but 1/2 isn't.
Yes - his proof for n
Thanks for the videos. I have watched keenly and enjoyed. Getting good enough to actually finish some of them and I felt super accomplished having gotten to the end of this one! I prefer my solution though for case n>=5 although do appreciate that yours is more algebraically robust.
If we accept that 2^(n-2)>n-1 (and the difference differs by more than 1) for n>=5. We can exhaustively extract all 2 contained in n-1 leaving an odd number. The LHS is now the product of two numbers: one is an odd number less than n-1 and the other a power of two that is greater than or equal to n-2. i.e LHS is now the product of two coprime integers. This implies that the smaller of these numbers is equal to smaller of that on the RHS and vice versa. However, the difference between these two numbers is even greater than what we started with (at least 2) and yet the RHS only differs by 1 which is a contradiction!
Thanks a lot! I liked your solution of the problem!
Nice problem. For the size contradiction, instead of splitting by cases you could start with stating that 2^(n-2) divides either m or m+1, so m+1 >= 2^(n-2) in any case, and get the contradiction. It saves a bit of case analysis.
Good point
At 3:46, that is not equivalent. I think you mean
I have decided to use induction to show that
n=5.
Base Case:
5
Nice problem.
Here's my version of the no solutions where n > 4:
(n-1) 2^n = (N-1) (N+1)
For larger and larger n, the multiple of 4 on the right dominates.
For largest max n, set:
N+1 to be a power of 2 (so it can't eat-up any of the odd factors of n-1)
and n to be even (so N+1 doesn't eat-up any of the even factors of n-1)
This ensures N-1 is as large as it can be.
Then compare:
N-1 = 2(n-1)
with
N+1 = 2^(n-1)
They differ by 2 when n = 4
but differ by more than 2 (increasing) when n > 4
Thanks! Great problem and explanation
Thanks 😊 for making the video really needed something for my mind to do to help he rationalize.
If you wrote a book with even just the major theorems used for proofs with proofs of those with examples along with a few general techniques such as strong induction, I'd buy it. I'd much prefer that to channel donations.
Using odd numbers to find squares. Or box in a box in a box effect.
Use N x 4 - 4
n=-2 would work as plugging in that value you get .25 which is .5²
@8:18 - the moment "= 1" is written backward in chalk on the back of Michael's shirt
What if we allowed perfect squares of rational numbers? Are there any solutions for negative n?
For a moment I was going to say it was satisfied for n=-2, as it *is* technically (1/2)^2 (-3*1/4+1=1/4), but then I realized they meant perfect squares in the *integers* and not the *rationals*.
How does one work and see such hidden inequalities, and I loved how you could conclude om fly that m = 2^(n-2) * x
I would have messed up there and notice it much later. I am a Computer Science and Engg student and I really wanna improve with handling such stuff in my mind, I will be glad to have suggestions. I struggle with exercises in technical/mathematical texts very bad
Tshirt is inside out, that proves the solution is correct.
10:58 Why doesn’t that inequation hold either for n=1 or n=4 when those values are solutions ???
I’m not a fan of Number Theory, but I did enjoy this problem very much.
Thank you, professor.
CMU shout out! 😄
m+1?
So - rational numbers can’t be perfect squares(?!)
What's the preliminary to this video by Penn to explain basics about number theory
Check his other channel "MathMajor". He has a full course on number theory there.
Isn’t the output being a fraction still possible to be a perfect square ex 1/4 = (1/2)^2
Edit: or do perfect squares have to be integers
yes perfect squares have to be integers
@@vanjansampath5753 says who?
@@AmosNewcombe joe
Couldn't you have stopped the n≥5 case at 8:53, when the product of two integers of opposite parity (clearly odd) was "equal" to an even integer?
Nope. 2*3 is the product of two integers of opposite parity, but it is even. In fact, the product of two numbers of opposite parity will _always_ be even, because one of the numbers must have a factor of 2.
3:44 I'm struggling to understand why that's equivelant
just a direct way
wowww cool solution
N=-1 solution
Does the phrase perfect square imply integers only? Is 9/49 not considered a perfect square?
Exactly what I thought , isn’t n=-2 a solution too as for n=-2 we get the simplified value as 1/4
@@notananimenerd1333 pretty sure the original question specified “the square of an integer” because apparently “prefect square” could mean the square of an integer or the square of a rational number, depending on the context.
Moreover, I think it would be difficult to solve cases when n
Michael is king of inequalities. Other content providers would probably use other methods to solve this.
Its a perfect Square for all n except for the ones it is not.
Can't we have like fractional perfect squares?
No, the definition of perfect square is that it has an integer square root
Please make a probability cours in mathmajor
Very cool
3:43 I did not follow this part. Could someone clarify?
At that point, you want to show the following implication
*n ≤ -2: f(n) := (n-1) * 2^n ∈ (-1; 0) => f(n) ∉ ℤ*
Notice *f(n)* is clearly negative, so you only need to show *f(n) > -1* - that's what happens at 3:45ff.
The reason why you do it this way is the graph of *f(x)* with *x ∈ ℝ* .
Hi Dr.!
Ηii,has anyone solve it with square entrapment?? If yes I would like to see the solution, thank you
A bit off the topic, but is 9^m-1 a perfect square?
Only when m is 0. If m negative, the difference is non-integer. If m>0, a square is either 0 or 1 mod 3 but 9^m-1 is -1 mod 3.
Well, 9^m is always a perfect square :). So if you subtract one it usually won't be, the only exception being m=0 as Kenneth explains.
3:12 Does anyone see alternating 0 and 1 on the top of the board?
Not quite alternating. There are more 0s than 1s. I think that's from the Prime Constant video.
For all real x, we have 2 to the x power is
greater than x.
Please! :) can we not do induction? sick of it, already!!!! :):):) love you pro!
@8:20 Remember, don't drink (water) and use math. 🤡