An awesome number theory contest problem

🌟Support the channel🌟

🌟my other channels🌟

🌟My Links🌟

🌟How I make Thumbnails🌟

🌟Suggest a problem🌟

[carstenmeyer]

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*

[jursamaj]

Just for fun: the limit as n approaches -∞ is 1, which is a square.

[think_logically_]

From 1-n<2^(-n), after substitution m=-n, you get m+1<2^m, rather than m-1<2^m, so proving that m<2^m doesn't help.
However, it is a minor issue, as m+1<2^m can be proven in the same way.

[erazorheader]

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 <= r + 1 or r >= 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.

[goodplacetostop]

5:17 Classic Michael Penn induction
14:03 Good Place To Stop

[sergeipetrov]

Thanks a lot! I liked your solution of the problem!

[nodiceism]

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!

[txikitofandango]

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.

[bigjukebox]

there is a small mistake at 12:40.

When x is equal to 1, then both sides are in fact equal (since 1^2 = 1) - the same is true for the following inequality - they should really be >=.

If it wasn't, that would contradict the n=4 solution we found earlier, since both sides are equal in that case.

[udic]

4:48 1-n=1+m not m-1. Although the proof is the same

[davidcroft]

"n equals 1 is zero" Michael Penn, 2022

[urekah]

Thanks 😊 for making the video really needed something for my mind to do to help he rationalize.

[guidomartinez]

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.

[Gninofisico]

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.

[givrally]

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.

[krisbrandenberger]

I have decided to use induction to show that
n<2^(n-2) for all n>=5.
Base Case:
5<2^(5-2) since 5<2^3=8.
Inductive Step:
Assume k<2^(k-2) for all k>=5 and consider k+1.
k+1<2*k<2^(k-1) which makes k+1<2^(k-1).
Thus, n<2^(n-2) for all n>=5 which means n-1<2^(n-2) for all n>=5 as well.

[owlsmath]

Thanks! Great problem and explanation

[anon]

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

[zygoloid]

At 3:46, that is not equivalent. I think you mean <= here, not <=>.

[alikaperdue]

@8:18 - the moment "= 1" is written backward in chalk on the back of Michael's shirt