Michael I think the whole reasoning on 8:41 about pairs of relative primes is not correct. Example: m = 14, then m(m+1) = 6*35 but both m and m+1 do not divide either of 6 or 35. I think this only works with actual primes.
The relatively primes step appears to be wrong. We have m(m+1)=4^{y-1}(4^{x-y}+1), what you said, that either m divides 4^{y-1} or m+1 divides 4^{y-1} is false, the equality only implies 4^{y-1} divides m or it divides m+1.
The general idea is right. Seems like mistakes in the video cancel each other. At 9:10 the statement should be exactly opposite: either 4^(y-1)Im or 4^(y-1)I(m+1), because of prime factorization. So we have two cases: m=u*4^(y-1) or m=u*4^(y-1)-1, where u is natural. In both cases when you put m in the equation, 4^(y-1) will cancel, and it will be clear that 4^(x-y)>=4^(y-1). Therefore x+1>=2y, and in the yellow box we have 2y>= x+1, so the only solution is x+1=2y.
I agree, the fact that each side of the equation is a product of mutually prime numbers does not imply (by itself, at least) that either of these numbers from one side of the equation divides either of the numbers from the other side. My counterexample was 15×77=21×55 (using factors 3, 5, 7, and 11 combined in pairs two ways), where clearly neither 15 nor 77 divides either 21 or 55, but yours is better because one side is actually of the form m(m+1).
Right. And in fact because on the left we have 4^(y-1) * (something odd), and the right hand side is a product of an odd and an even, we can actually conclude the opposite: either 4^(y-1)|m or 4^(y-1)|m+1, depending on which of m and m+1 is even.
There are many mistakes. 1) 8:42 False. There is at least one solution (x,y,z) in NxNxN with x=y, and it is (1,1,3). I don't know if it's the only, maybe yes. 2)9:00 False. (2*2)*(3*13) = (2*2*3)*13 or 4*39 = 12*13; 4 and 39 are coprimes, 12 and 13 are consecutive and so coprimes, but neither 12 nor 13 divides 4. 3) 10:30 False. We arrive at the same conclusion 2y >= x+1
@@angelmendez-rivera351 The fact that the solution (1,1,3) is contained in the original family is irrelevant, he said that solutions with x = y don't exist, and this statement is false.
8:50 4^(y-1) has only one prime in it, 2. So all the possible factors are even. Therefore, either m is divisible by 4^(y-1) or (m+1) is divisible by 4^(y-1). Furthermore, at 9:25, m >= 4^(y-1) not the other way around as written on the board.
Once upon a time, I majored in math and physics. Did not graduate, mostly due to being a dumb, undisciplined kid. I absolutely love watching these videos-I’ve always enjoyed number theory and feel like I can understand the problem solving strategy, even though no chance I’d figure it out myself. Thank you very much.
In the sequence of wrong steps at about 9:00 it is probably simplest when considering the equation 4^{y-1}*(4^{x-y}+1)=m*(m+1) to consider the cases m=4^{y-1}*n where n is odd and similarly m+1=4^{y-1}*n. For the first case you then get the equation 4^{x-y}+1=n*(4^{y-1}*n+1). When n=1 you must have x-y=y-1 or x=2y-1. If n>1 then clearly x>2y-1>=x by the first inequality you obtained which is the desired contradiction. Similarly for the other case.
At 8:50 it is not clear that m has to divide some of the factors, since the prime factors of m can split into both of them. It is true, however, that 4^{y-1} divides exactly one of the factors on the right. Case 1: 4^{y-1} divides m and therefore m >= 4^{y-1}, m+1 >= 4^{y-1}+1 >= 4^{x-y}+1 and because of the equation derived, we must have equalities everywhere. This means z=2m+1=2^{2y-1}+1 and x=2y-1. Case 2: 4^{y-1} divides m+1. If m+1>4^{y-1}, then m+1 >= 2*4^{y-1} and so m >= 2*4^{y-1}-1 >= 4^{y-1} and also m+1 >= 4^{y-1}+1 >= 4^{x-y}+1. Again, the RHS is not less than the LHS, and so we must have equalities everywhere, namely 4^{y-1}=1, consequently y=1, x=1, z=2m+1=3. If it were true that m+1=4^{y-1}, we would obtain from the equation that m=4^{x-y}+1. But then 4^{x-y}+2=4^{y-1}, which is easily seen not to be possible.
5:39 I can't get how did you manage to move from strict inequality: 1 + 4**x + 4**y > (2**x)**2 To non-strict inequality: 1 + 4**x + 4**y ≥ (2**x + 1)**2 ? Counter example: 6 > 2**2, but 6 < (2+1)**2. I can agree with this: 1 + 4**x + 4**y >= (2**x)**2 + 1.
Yes one argument is missing. The term on the left hand side is z^2. So he proved that z^2 > (2^x)^2 which implies that z > 2^x so that z>= 2^x + 1 and then take the square.
Yeah, I had to think about that one too. Mike forgot to say because 1+4^x+4^y is = z^2 so if z^2 > (2^x)^2 then z^2>=(2^x+1)^2 because x and z are natural numbers.
I have spent countless hours trying to solve a problem but have failed; maybe Michael or one you guys can help solve it. Here is the problem: Consider set A to include all the natural numbers from 1 to 4n, let S be the sum 1+2+3...4n. Now lets randomly partition set A into n subsets each with exactly 4 numbers. Prove that you can pick 2 numbers from each subset so that the sum of resulting 2n numbers will be equal to S/2.
I found a (hopefully correct) way to get the second inequality without making the erroneous co-prime argument Mike made at 9:05: We'll assume x >= y, as Mike did. Also we will assume x,y>=2. As the case where either is equal to 1 is easy to deal with and provably has a unique solution that satisfies 2y = x + 1. The original equation can be re-written as (4^y) (4^(x - y) + 1) = (z - 1)(z + 1) Define m = z - 1. (4^y) (4^(x - y) + 1) = m(m+2). Since m is always even, we can define k s.t. 2k = m (4^y)(4^(x - y) + 1) = 2k(2k + 2) = 4k(k + 1) (4^(y - 1))(4^(x - y) + 1) = k(k + 1) Note: all the instances of 2 in the prime factorization are contained in the term 4^(y - 1). If 2 divides the other term, then x = y, which leads to x = 1 if you substitute it into the original equation - a case we excluded. Case 1, k is even: Then k has all the factors of 2 on the right side, so z = n*2^(2y - 1) + 1for some odd, positive n. Substituting into the original equation, 1 + 4^x + 4^y = (n^2)(2^(4y - 2)) + n(2^(2y)) + 1 2^(2x) + 2^(2y) = (n^2)(2^(4y - 2)) + n(2^(2y)) 2^(2x) = (n^2)(2^(4y - 2)) + (2^(2y))(n - 1) = (2^(2y))((n^2)(2^(2y - 2) + n - 1) so 2^(2x - 2y) = (n^2)(2^(2y - 2) + n - 1. The function on the right is always positive and monotonically growing with n. Therefore we may obtain an inequality using n = 1: 2^(2x - 2y) >= 2^(2y - 2) thus, 2x - 2y >= 2y - 2, which leads to the desired inequality. Case 2, k + 1 is even: Define n in the same way as before: k + 1 = n*2^(2y - 2); m = 2k = 2*(n*2^(2y - 2) - 1) z = m + 1 = 2(n*2^(2y - 2) - 1) + 1 = n*2^(2y - 1) - 1 Substituting into the initial eq-n: 1 + 2^(2x) + 2^(2y) = (n*2^(2y - 1) - 1)^2 = (n^2)2^(4y - 2) - n2^(2y) + 1 2^(2x) = (n^2)2^(4y - 2) - (n + 1)2^(2y) = 2^(2y)((n^2)*2^(2y - 2) - n - 1). This function also grows monotonically and is always positive. Taking once more the lowest value of n, we get. 2^(2x - 2y) >= 2^(2y - 2) - 2 = 2(2^(2y - 3) - 1) 2^(2x - 2y - 1) >= 2^(2y - 3) - 1. Here we can use the fact that for any positive integer q, 2^q = (1 + 2 + ... + 2^(q - 1)) + 1 and the fact that 2^(2x - 2y - 1) is even (the case where it's 1 can be excluded) to obtain 2^(2x - 2y - 1) >= 2^(2y - 4) so 2x - 2y - 1 >= 2y - 4, which leads to the desired inequality. Tell me if you see any mistakes XD
I think that the video is missing a simple observation. Start by noticing that z is odd, so we can write z=(2m+1). Substitute for z and expand. We get: 1 + 4^x + 4^y = 4m^2 + 4m + 1 4^x + 4^y = 4m(m+1) so 4^(x-1) + 4^(y-1) = m(m+1) Assume x < y and factor out 4^(x-1) from the LHS: (4^(x-1)).(4^(y-x) + 1) = m(m+1) We had that in the video. But m and (m+1) are _consecutive_ integers and comparing that to the LHS, we can surely uniquely identify m with 4^(x-1) and (m+1) with (4^(y-x) + 1) because the LHS is (a power of 4) multiplied by (a power of 4 plus 1). The former can only have even factors, and the latter can only have odd factors, and there's no other way of re-grouping those factors to make two consecutive integers. That means m = 4^(x-1) = 4^(y-x), which gives x-1 = y-x, so y = 2x-1 and z=2.4^(x-1) +1 = 2^(2x-1) + 1 The first three solutions are (1, 1, 3), (2, 3, 9), (3, 5, 33). Each value of x = { 1, 2, ...} gives a solution, and because x and y are symmetric, swapping x for y gives another set of solutions but those are trivially identical to the first set.
since the equation is symmetric for x and y (swapping them changes nothing), you know for sure that whatever you do (even if it's asymmetric), any solutions you get can just be swapped automatically
Let H be the Binary Hamming Weight. H(1) is 1, H(4^n) is 1. This means H(z²) is 3, unless x=y (we'll get that at the end). For an odd square number to have a Hamming Weight of 3, it's root's weight must be 2. So in binary the first and last digit are 1s, and between are only 0s. When squaring a number of weight 2 in binary, it is logically the same as concatenation of a number onto itself and offsetting the middle digit throught addition. Those three ones in binary must map to the powers of 4 and 1, so this forces the binary representation of z² to be of odd length and the middle, off-center 1 to be in an odd position. Once satisfied, however, all values are solutions. x is any integer, y is 2(x-1)+1, and z is required to be square based on the original assumption and rules of binary arithmetic. Going back to x=y=1, this conveniently fits the same solution set, and it's the only value mapping 2(x-1)+1 back to x, so it is included and unique.
Can someone please explain in a robust way why we're allowed to put an inequality on (2^x+1)^2 (@05:52)? From my point of view the inequality could be the other way around. You can not infer inequality relationships between A, B if they're both larger than C.
The premise on the left half of the board is that 1+4^x+4^y is a perfect square. If it's strictly bigger than the square number (2^x)^2 then it must be at least as big as the next square number up, i.e. (2^x+1)^2
@@Div1nePiece what you say is not false, but you can go further by relying on LHS being a perfect square. Think of it like this to see why - for the whole LHS, substitute z^2. So you have z^2>=(2^x)^2. Square root both sides: z>=2^x. Make it strict by adding 1 to RHS: z>2^x+1. Square both sides again: z^2>(2^x+1)^2. Substitute the original LHS back in instead of z^2, and now you have the result you were after.
@@GeorgeFoot That makes much more sense. Thanks a lot! I feel Mr. Penne often explains very elementary things but explaining some of the more convoluted concepts often eludes him. This helped a lot.
8:40 well, there is a solution with x=y, namely (1,1,3), which occurs in both already known infinite families 8:56 non sequitur as said. But as only one of m, m+1 is even, that one has to be a *multiple* of 4^(y-1). Thus {m or m+1} = 4^(y-1) k, wheras {m+1 or m} = (4^(x-y)+1)/k 1 [and m=1 quickly leads to x = y=1]. Also, k must divide 4^(x-y)+1, which exclude k=4, k=3, and [provided x != y] k=2. Therefore k=1, 1 = |(m+1) - m | = |4^(x-y)+1 - 4^(x-1)|, which leads to the alreaddy known family of solutions.
Hey Mr.Penn why not to do the floor function problem from Indian National Math Olympiad from 2014 ....my friend already suggested that....and that's a real beauty !!!
I didn't understand the part after 8:40, so I tried a bit different way. First, assume x>y (not x≥y) and let z=2m+1. (get the relation "2y≥x+1" in the same way.) Then make the equation "1+4^{x}+4^{y}=z^{2}" into "4^{y-1}(4^{x-y}+1)=m(m+1)" →ⓐ. Suppose m(m+1)=2^{n}*p*q, where n≥0 and p&q are odd integer. Then 4^{y-1}=2^{n} and 4^{x-y}+1=p*q. This is because 4^{y-1} does not have an odd deviser other than 1, and "x>y" implies that 4^{x-y}+1 is odd. Besides, (m, m+1) has the form of (2^{n}*p, q) or (p, 2^{n}*q) because only one of 'm or m+1' is even. If 【m is even】 m+1=q, then (m+1)|4^{x-y}+1, and if 【m is odd】 m=p, then m|4^{x-y}+1 . Thus we can write it as "m≤4^{x-y}+1", and substitute it to the equation ⓐ. 4^{y-1}(4^{x-y}+1)=m(m+1)≤(4^{x-y}+1)(4^{x-y}+2), so 4^{y-1}≤4^{x-y}+2
Thus we can write mm and since 4^y-1 is even and 4^x-y +1 is odd .and there fore 4^x-y +1 >4^y-1 . I wasnt able to understand this so iam considering like how 2(even)×15 (odd) =30 and 5(m) and 6 (m+1) =30 so am I right to consider that odd that is 15 in this case 4^x-y +1 > 5 or m respectively
Maybe it's the physicist in me, but do you even need the "assume x>y" argument at all? The conclusion of it is just to say that the equation is symmetric in x and y, but that's inherently true from arithmetic principles (1+4^x+4^y=1+4^y+4^x). In other words, since x and y are arbitrary to begin with, and both have the same base of 4, interchanging them doesn't give us new solutions.
usually it helps to make certain arguments (imagine: you want to divide by x-y, but if y is bigger, then you would have to switch the inequality). the idea being: a symmetrical equation relating two values is often solved asymmetrically
Problem sugestion! : "(Brazillian undergraduate olympiad 2019 ) Let R> 0 be the set of positive real numbers. Determine all functions f: R> 0 → R> 0 such that f (xy + f (x)) = f (f (x) f (y)) + x for all positive reals x and y.
Fill the board with numbers 1,2,3,4 in a following way row 1: 1,2,3,4,1,2,3,4,1,2, row 2: 2,3,4,1,2,3,4,1,2,3, row 3: 3,4,1,2,3,4,1,2,3,4, and so on, you get the idea. Then you can see that each 1x4 piece will cover exactly 1 of each number, so 25 pieces will cover 25 of 1, 2, 3 and 4s. But If you count the numbers on chessboard you will notice there are 26 of 2s and 24 of 4s, so it's impossible. If you are into matrices, you can write the argument a bit more compactly as 10x10 matrix where a_i,j = (i+j) mod 4 (the numbers will be slightly different, but point still stands).
Simply : if x = 0 or y = 0 (or both), then 1+4^x +4^y = 2 or 3 = z^2 (mod 4), impossible because the only quadratic residues are 0 and 1 mod 4. So WLOG x >= y >= 1, and z is odd, with z = 2k+1. Then 4^(y-1) (4^(x-y)+1) = k(k+1), and since k and k+1 are coprimes, we have 2 cases : case 1 : 4^(y-1) = k and 4^(x-y)+1 = k+1 => x-y = y -1 => y = (x+1)/2. So 2^(2x) + 2^(x+1) + 1 = (2^x+1)^2 = z^2 which give the expected solution. Case 2 : let a = y-1, b = x-y. We have 4^a = k+1, 4^b + 1= k, so 4^a - 4^b = 2, clearly impossible since if a = 0 or b = 0 it is odd and it gives 0 if both are 0, and else it is divisible by 4 which does not divide 2.
Hey, can you do a vid, where you don't do the question before you know the solution, it will be nice to see the thought process, so we know how to think kinda...
@@xxxprawn8374 solutions to Korean (or really just Asian/foreign language math Olympiads) aren't so readily available, so he probably did this pretty much all by himself... In his Q&A too he said that he first thinks about them by himself then looks through some of the solution
Can't we simply factorise the LHS into (1+2^y)² which expands to (1+2.2^y+4^y) so we make 4^x=2.2^y so x=(y+1)/2. By symmetry we can also swap x and y. Thus for any odd natural number t we have solutions (x,y,z)=((t+1)/2,t,1+2^t) and (t,(t+1)/2,1+2^t)
4^y-1 cannot be m+1 because IF that was true, then 4^(x-y) +1 would HAVE TO be equal to m, which would mean 4^(y-1) -1 is EQUAL to 4^(x-y) +1. This CANNOT BE TRUE.
unfortunately with your errors this time around 9:00 and 10:33 i cannot really agree on this conclusion without having to prove it independently. you had: the inequality: 4^(x-1) x-1 >= 2y-2, which is a strict violation of the definition of an increasing function.
I have a sol'n... This is general solution... That is... X= k s.t. k belongs to N Y = 2k-1 Z = 2*4^(k-1)+1 I found it by this way... Since LHS is odd so Z is odd... Put z=2k+1 WLOG assume x 4^x+4^y=4k(k+1) There is 2 case k is odd or k is even K is odd don't work (Why?) If k is even then 4^x(4^(y-x)+1)=4k(k+1) Since k+1 is the only odd part of the eqn So k+1 = 4^(y-x)+1 =>k = 4^(y-x) Again from the eqn we get K=4^(x-1) Thus y=2x-1 Then just substitute and get sol'n
Hello Michael! I did my own solution without watching the video at first, and came to the same result y=2x-1. I did not verify that this is the only solution, as my transformations are all equivalences and "no assumptions or something 'hopeful'". So my question: is verifying the uniqueness of the solution a "must"? (If you like I can do a video of my own proof and post it in YT).
Thank you very much for your videos! They're amazing. Could you please solve some combinatorics problems? Especially graph theory. I think you can show all the beauty of these problems. Thanks!
using the same reasoning in the video ua-cam.com/video/wviiZlYRaGE/v-deo.html and using the fact 2y>x+1 (equality case used to produce the two sol sets) which leads to x-y
I accidentally left out a step at 9:25. There is a simple reason why 4^(y-1) cannot be m+1. Reply to this comment with your argument!
Michael I think the whole reasoning on 8:41 about pairs of relative primes is not correct. Example: m = 14, then m(m+1) = 6*35 but both m and m+1 do not divide either of 6 or 35. I think this only works with actual primes.
Also you stated that x=y doesnt give a solution at approx 8:40. This is incorrect and is easy to notice.
X=y does give a valid solution when x=y=1
The step at 9:03 maybe wrong,it should be 4^(y-1)|m or 4^(y-1)|m+1,then we have 4^(y-1)
The relatively primes step appears to be wrong.
We have m(m+1)=4^{y-1}(4^{x-y}+1), what you said, that either m divides 4^{y-1} or m+1 divides 4^{y-1} is false, the equality only implies 4^{y-1} divides m or it divides m+1.
btw i used am - gm inequality to conclude the quantities are equal (equality occurs iff the quantities are equal in am-gm btw )
The general idea is right. Seems like mistakes in the video cancel each other. At 9:10 the statement should be exactly opposite: either 4^(y-1)Im or 4^(y-1)I(m+1), because of prime factorization. So we have two cases: m=u*4^(y-1) or m=u*4^(y-1)-1, where u is natural. In both cases when you put m in the equation, 4^(y-1) will cancel, and it will be clear that 4^(x-y)>=4^(y-1). Therefore x+1>=2y, and in the yellow box we have 2y>= x+1, so the only solution is x+1=2y.
Step in 9:00-9:05 is wrong 16 * 147 = 48 * 49 but 48 is not a divisor of 16 and 49 is not a divisor of 16
Yeah, that didn't make sense at all. Hoping he would update or post a comment.
(2*3)*(5*7)=(2*7)*(3*5) but 14 is not a divisor of 6 or 35
I agree, the fact that each side of the equation is a product of mutually prime numbers does not imply (by itself, at least) that either of these numbers from one side of the equation divides either of the numbers from the other side. My counterexample was 15×77=21×55 (using factors 3, 5, 7, and 11 combined in pairs two ways), where clearly neither 15 nor 77 divides either 21 or 55, but yours is better because one side is actually of the form m(m+1).
Right. And in fact because on the left we have 4^(y-1) * (something odd), and the right hand side is a product of an odd and an even, we can actually conclude the opposite: either 4^(y-1)|m or 4^(y-1)|m+1, depending on which of m and m+1 is even.
There are many mistakes.
1) 8:42 False. There is at least one solution (x,y,z) in NxNxN with x=y, and it is (1,1,3). I don't know if it's the only, maybe yes.
2)9:00 False. (2*2)*(3*13) = (2*2*3)*13 or 4*39 = 12*13; 4 and 39 are coprimes, 12 and 13 are consecutive and so coprimes, but neither 12 nor 13 divides 4.
3) 10:30 False. We arrive at the same conclusion 2y >= x+1
8:36 if x=y=1 then there is an 'obvious' solution z=3
Except the makes the mistake of claiming that x=y doesnt produce a valid solution at 8:40
I dont know how he didnt see that
@@angelmendez-rivera351 The fact that the solution (1,1,3) is contained in the original family is irrelevant, he said that solutions with x = y don't exist, and this statement is false.
@@angelmendez-rivera351 What do you mean by qualifier?.
8:50 4^(y-1) has only one prime in it, 2. So all the possible factors are even. Therefore, either m is divisible by 4^(y-1) or (m+1) is divisible by 4^(y-1). Furthermore, at 9:25, m >= 4^(y-1) not the other way around as written on the board.
10:30 i'll stop you right there, you got 4^{x-1}
but the second inequality he got actually was going the other way because of the divisibility, so what he did is correct he just had a typo
Once upon a time, I majored in math and physics. Did not graduate, mostly due to being a dumb, undisciplined kid. I absolutely love watching these videos-I’ve always enjoyed number theory and feel like I can understand the problem solving strategy, even though no chance I’d figure it out myself. Thank you very much.
I came here just to listen to the “that’s a good place to stop”
LOL!
But there's a great math problem you'd be missing out on...
In the sequence of wrong steps at about 9:00 it is probably simplest when considering the equation 4^{y-1}*(4^{x-y}+1)=m*(m+1) to consider the cases m=4^{y-1}*n where n is odd and similarly m+1=4^{y-1}*n. For the first case you then get the equation 4^{x-y}+1=n*(4^{y-1}*n+1). When n=1 you must have x-y=y-1 or x=2y-1. If n>1 then clearly x>2y-1>=x by the first inequality you obtained which is the desired contradiction. Similarly for the other case.
11:23 멈추기 좋은 곳
Loading 96.2%...
What are you loading
I get it nvm
ㅎㅇ
as a south korean the better translation for that phrase would be 멈추기 좋은 곳. nvm tho
한국인 많네요 ㅎㅎ
At 8:50 it is not clear that m has to divide some of the factors, since the prime factors of m can split into both of them. It is true, however, that 4^{y-1} divides exactly one of the factors on the right.
Case 1: 4^{y-1} divides m and therefore m >= 4^{y-1}, m+1 >= 4^{y-1}+1 >= 4^{x-y}+1 and because of the equation derived, we must have equalities everywhere. This means z=2m+1=2^{2y-1}+1 and x=2y-1.
Case 2: 4^{y-1} divides m+1. If m+1>4^{y-1}, then m+1 >= 2*4^{y-1} and so m >= 2*4^{y-1}-1 >= 4^{y-1} and also m+1 >= 4^{y-1}+1 >= 4^{x-y}+1. Again, the RHS is not less than the LHS, and so we must have equalities everywhere, namely 4^{y-1}=1, consequently y=1, x=1, z=2m+1=3.
If it were true that m+1=4^{y-1}, we would obtain from the equation that m=4^{x-y}+1. But then 4^{x-y}+2=4^{y-1}, which is easily seen not to be possible.
Quick thought at 8:44, but x = y does give one solution: {x, y, z} = {1, 1, 3}
The step at 10:30 looks wrong, it seems that you have inverted the inequality.
Yes, I noticed the same
4:20 might have been a good place to stop.
Thanks Michael. Watching all your videos 👍👍
5:39 I can't get how did you manage to move from strict inequality:
1 + 4**x + 4**y > (2**x)**2
To non-strict inequality:
1 + 4**x + 4**y ≥ (2**x + 1)**2
?
Counter example: 6 > 2**2, but 6 < (2+1)**2.
I can agree with this:
1 + 4**x + 4**y >= (2**x)**2 + 1.
Because we say the LHS is a perfect square, then it has to be more than or equal to the next larger perfect square
@@bigbrain296 Thanks. Now I've got this.
@@bigbrain296 In this part of the proof there was no mention that LHS is a perfect square.
@@alphabeta3029 What 😂? The whole proof is hinged on the assumption that it's a perfect square lol
I could not follow how (1+4^x+4^y) > (2^x)^2 implies
(1+4^x+4^y)>= (2^x+1)^2
Like :
20>4^2 = (2^2)^2.
But, 20>= (2^2+1)^2 is invalid anyway.
Yes one argument is missing.
The term on the left hand side is z^2. So he proved that z^2 > (2^x)^2 which implies that z > 2^x so that z>= 2^x + 1 and then take the square.
Yeah, I had to think about that one too. Mike forgot to say because 1+4^x+4^y is = z^2 so if z^2 > (2^x)^2 then z^2>=(2^x+1)^2 because x and z are natural numbers.
I would like to see problems on graph theory.
I have spent countless hours trying to solve a problem but have failed; maybe Michael or one you guys can help solve it. Here is the problem: Consider set A to include all the natural numbers from 1 to 4n, let S be the sum 1+2+3...4n. Now lets randomly partition set A into n subsets each with exactly 4 numbers. Prove that you can pick 2 numbers from each subset so that the sum of resulting 2n numbers will be equal to S/2.
I found a (hopefully correct) way to get the second inequality without making the erroneous co-prime argument Mike made at 9:05:
We'll assume x >= y, as Mike did. Also we will assume x,y>=2. As the case where either is equal to 1 is easy to deal with and provably has a unique solution that satisfies 2y = x + 1.
The original equation can be re-written as (4^y) (4^(x - y) + 1) = (z - 1)(z + 1)
Define m = z - 1.
(4^y) (4^(x - y) + 1) = m(m+2). Since m is always even, we can define k s.t. 2k = m
(4^y)(4^(x - y) + 1) = 2k(2k + 2) = 4k(k + 1)
(4^(y - 1))(4^(x - y) + 1) = k(k + 1)
Note: all the instances of 2 in the prime factorization are contained in the term 4^(y - 1). If 2 divides the other term, then x = y, which leads to x = 1 if you substitute it into the original equation - a case we excluded.
Case 1, k is even:
Then k has all the factors of 2 on the right side, so z = n*2^(2y - 1) + 1for some odd, positive n. Substituting into the original equation,
1 + 4^x + 4^y = (n^2)(2^(4y - 2)) + n(2^(2y)) + 1
2^(2x) + 2^(2y) = (n^2)(2^(4y - 2)) + n(2^(2y))
2^(2x) = (n^2)(2^(4y - 2)) + (2^(2y))(n - 1) = (2^(2y))((n^2)(2^(2y - 2) + n - 1)
so 2^(2x - 2y) = (n^2)(2^(2y - 2) + n - 1. The function on the right is always positive and monotonically growing with n. Therefore we may obtain an inequality using n = 1:
2^(2x - 2y) >= 2^(2y - 2) thus,
2x - 2y >= 2y - 2, which leads to the desired inequality.
Case 2, k + 1 is even:
Define n in the same way as before:
k + 1 = n*2^(2y - 2); m = 2k = 2*(n*2^(2y - 2) - 1)
z = m + 1 = 2(n*2^(2y - 2) - 1) + 1 = n*2^(2y - 1) - 1
Substituting into the initial eq-n:
1 + 2^(2x) + 2^(2y) = (n*2^(2y - 1) - 1)^2 = (n^2)2^(4y - 2) - n2^(2y) + 1
2^(2x) = (n^2)2^(4y - 2) - (n + 1)2^(2y) = 2^(2y)((n^2)*2^(2y - 2) - n - 1). This function also grows monotonically and is always positive. Taking once more the lowest value of n, we get.
2^(2x - 2y) >= 2^(2y - 2) - 2 = 2(2^(2y - 3) - 1)
2^(2x - 2y - 1) >= 2^(2y - 3) - 1. Here we can use the fact that for any positive integer q,
2^q = (1 + 2 + ... + 2^(q - 1)) + 1 and the fact that 2^(2x - 2y - 1) is even (the case where it's 1 can be excluded) to obtain
2^(2x - 2y - 1) >= 2^(2y - 4)
so 2x - 2y - 1 >= 2y - 4, which leads to the desired inequality.
Tell me if you see any mistakes XD
You made a terribly and blatently wrong statement at 8:40 when you said there is no solution when x=y
There is though. When x=y=1, then z=3.
Calm down... it's and edge case and super easy to deal with, he probably just dismissed it as it's actually included in the first set of solutions.
He meant that x=y is not a family of solutions, and no it's not at all a terrible mistake
Hi MIchael, Can you re-do the correct version of the videos and delect this one. Thanks!!
no don't delete this one just edit the description. why does everyone love deleting videos
I don’t get the last step. It seems to me like you showed twice that x+1
he wrote the inequality wrong it is supposed to be m(m+1)
Would anyone do the first steo though..why would anyone think of that??
I think that the video is missing a simple observation.
Start by noticing that z is odd, so we can write z=(2m+1).
Substitute for z and expand. We get:
1 + 4^x + 4^y = 4m^2 + 4m + 1
4^x + 4^y = 4m(m+1) so 4^(x-1) + 4^(y-1) = m(m+1)
Assume x < y and factor out 4^(x-1) from the LHS:
(4^(x-1)).(4^(y-x) + 1) = m(m+1)
We had that in the video. But m and (m+1) are _consecutive_ integers and comparing that to the LHS, we can surely uniquely identify m with 4^(x-1) and (m+1) with (4^(y-x) + 1) because the LHS is (a power of 4) multiplied by (a power of 4 plus 1). The former can only have even factors, and the latter can only have odd factors, and there's no other way of re-grouping those factors to make two consecutive integers.
That means m = 4^(x-1) = 4^(y-x), which gives x-1 = y-x, so y = 2x-1 and z=2.4^(x-1) +1 = 2^(2x-1) + 1
The first three solutions are (1, 1, 3), (2, 3, 9), (3, 5, 33).
Each value of x = { 1, 2, ...} gives a solution, and because x and y are symmetric, swapping x for y gives another set of solutions but those are trivially identical to the first set.
I'm not sure I buy the 1:40 case 1: y>=x and then x
since the equation is symmetric for x and y (swapping them changes nothing), you know for sure that whatever you do (even if it's asymmetric), any solutions you get can just be swapped automatically
If x and y are equal to one then that does give a solution to the equation
Let H be the Binary Hamming Weight. H(1) is 1, H(4^n) is 1. This means H(z²) is 3, unless x=y (we'll get that at the end). For an odd square number to have a Hamming Weight of 3, it's root's weight must be 2. So in binary the first and last digit are 1s, and between are only 0s. When squaring a number of weight 2 in binary, it is logically the same as concatenation of a number onto itself and offsetting the middle digit throught addition. Those three ones in binary must map to the powers of 4 and 1, so this forces the binary representation of z² to be of odd length and the middle, off-center 1 to be in an odd position. Once satisfied, however, all values are solutions. x is any integer, y is 2(x-1)+1, and z is required to be square based on the original assumption and rules of binary arithmetic. Going back to x=y=1, this conveniently fits the same solution set, and it's the only value mapping 2(x-1)+1 back to x, so it is included and unique.
Can someone please explain in a robust way why we're allowed to put an inequality on (2^x+1)^2 (@05:52)? From my point of view the inequality could be the other way around. You can not infer inequality relationships between A, B if they're both larger than C.
The premise on the left half of the board is that 1+4^x+4^y is a perfect square. If it's strictly bigger than the square number (2^x)^2 then it must be at least as big as the next square number up, i.e. (2^x+1)^2
@@GeorgeFoot thank you for your response. To me, logic dictates that the expression would be the RHS+1 instead. Why isn't that the case?
@@Div1nePiece what you say is not false, but you can go further by relying on LHS being a perfect square. Think of it like this to see why - for the whole LHS, substitute z^2. So you have z^2>=(2^x)^2. Square root both sides: z>=2^x. Make it strict by adding 1 to RHS: z>2^x+1. Square both sides again: z^2>(2^x+1)^2. Substitute the original LHS back in instead of z^2, and now you have the result you were after.
@@GeorgeFoot That makes much more sense. Thanks a lot!
I feel Mr. Penne often explains very elementary things but explaining some of the more convoluted concepts often eludes him. This helped a lot.
8:40 well, there is a solution with x=y, namely (1,1,3), which occurs in both already known infinite families
8:56 non sequitur as said.
But as only one of m, m+1 is even, that one has to be a *multiple* of 4^(y-1).
Thus {m or m+1} = 4^(y-1) k, wheras {m+1 or m} = (4^(x-y)+1)/k 1 [and m=1 quickly leads to x = y=1].
Also, k must divide 4^(x-y)+1, which exclude k=4, k=3, and [provided x != y] k=2.
Therefore k=1, 1 = |(m+1) - m | = |4^(x-y)+1 - 4^(x-1)|, which leads to the alreaddy known family of solutions.
Hey Mr.Penn why not to do the floor function problem from Indian National Math Olympiad from 2014 ....my friend already suggested that....and that's a real beauty !!!
Hi Debayu
I didn't understand the part after 8:40, so I tried a bit different way.
First, assume x>y (not x≥y) and let z=2m+1.
(get the relation "2y≥x+1" in the same way.)
Then make the equation "1+4^{x}+4^{y}=z^{2}" into "4^{y-1}(4^{x-y}+1)=m(m+1)" →ⓐ.
Suppose m(m+1)=2^{n}*p*q, where n≥0 and p&q are odd integer.
Then 4^{y-1}=2^{n} and 4^{x-y}+1=p*q. This is because 4^{y-1} does not have an odd deviser other than 1, and "x>y" implies that 4^{x-y}+1 is odd.
Besides, (m, m+1) has the form of (2^{n}*p, q) or (p, 2^{n}*q) because only one of 'm or m+1' is even.
If 【m is even】 m+1=q, then (m+1)|4^{x-y}+1, and if 【m is odd】 m=p, then m|4^{x-y}+1 .
Thus we can write it as "m≤4^{x-y}+1", and substitute it to the equation ⓐ.
4^{y-1}(4^{x-y}+1)=m(m+1)≤(4^{x-y}+1)(4^{x-y}+2), so 4^{y-1}≤4^{x-y}+2
Thus we can write mm and since 4^y-1 is even and 4^x-y +1 is odd .and there fore 4^x-y +1 >4^y-1 .
I wasnt able to understand this so iam considering like how 2(even)×15 (odd) =30 and 5(m) and 6 (m+1) =30 so am I right to consider that odd that is 15 in this case 4^x-y +1 > 5 or m respectively
If you need any korean math resource let me know, i can translate a bit for you
You could have simply assumed another case of y>=x and that would have resulted in the second eqn.
Maybe it's the physicist in me, but do you even need the "assume x>y" argument at all? The conclusion of it is just to say that the equation is symmetric in x and y, but that's inherently true from arithmetic principles (1+4^x+4^y=1+4^y+4^x). In other words, since x and y are arbitrary to begin with, and both have the same base of 4, interchanging them doesn't give us new solutions.
usually it helps to make certain arguments (imagine: you want to divide by x-y, but if y is bigger, then you would have to switch the inequality). the idea being: a symmetrical equation relating two values is often solved asymmetrically
Problem sugestion! : "(Brazillian undergraduate olympiad 2019 )
Let R> 0 be the set of positive real numbers. Determine all functions f: R> 0 → R> 0 such that
f (xy + f (x)) = f (f (x) f (y)) + x
for all positive reals x and y.
Who can solve that??
Prove that a 10x10 cheeseboard can't be covered by 25 1x4.
Fill the board with numbers 1,2,3,4 in a following way row 1: 1,2,3,4,1,2,3,4,1,2, row 2: 2,3,4,1,2,3,4,1,2,3, row 3: 3,4,1,2,3,4,1,2,3,4, and so on, you get the idea. Then you can see that each 1x4 piece will cover exactly 1 of each number, so 25 pieces will cover 25 of 1, 2, 3 and 4s. But If you count the numbers on chessboard you will notice there are 26 of 2s and 24 of 4s, so it's impossible.
If you are into matrices, you can write the argument a bit more compactly as 10x10 matrix where a_i,j = (i+j) mod 4 (the numbers will be slightly different, but point still stands).
X=y =1 have a solution with z=3
Simply : if x = 0 or y = 0 (or both), then 1+4^x +4^y = 2 or 3 = z^2 (mod 4), impossible because the only quadratic residues are 0 and 1 mod 4. So WLOG x >= y >= 1, and z is odd, with z = 2k+1. Then 4^(y-1) (4^(x-y)+1) = k(k+1), and since k and k+1 are coprimes, we have 2 cases : case 1 : 4^(y-1) = k and 4^(x-y)+1 = k+1 => x-y = y -1 => y = (x+1)/2. So 2^(2x) + 2^(x+1) + 1 = (2^x+1)^2 = z^2 which give the expected solution. Case 2 : let a = y-1, b = x-y. We have 4^a = k+1, 4^b + 1= k, so 4^a - 4^b = 2, clearly impossible since if a = 0 or b = 0 it is odd and it gives 0 if both are 0, and else it is divisible by 4 which does not divide 2.
solution set is restricted to positive integers; 1 and above
Hey, can you do a vid, where you don't do the question before you know the solution, it will be nice to see the thought process, so we know how to think kinda...
That would be very interesting! I second this comment!
Yeah definitely! We don't care if it goes half an hour long...
@@TechToppers the thing is these problems aren’t easy for someone with little training and it’s likely he can’t solve these problems on his own at all
@@xxxprawn8374 solutions to Korean (or really just Asian/foreign language math Olympiads) aren't so readily available, so he probably did this pretty much all by himself... In his Q&A too he said that he first thinks about them by himself then looks through some of the solution
The second half of the solution doesn't work, but I don't think it's necessary. The first half of the video shows that in case one (x
@ゴゴ Joji Joestar ゴゴ No it isn't: x=1, y=2x-1=1, z=1+2^(2x-1)=3.
@ゴゴ Joji Joestar ゴゴ the only way the logic doesn't work is if there exists some x for which there are two valid y values.
(1,1,3) is a solution, thus solution where x=y exists.
Which also is included in the general solution
@@Mr5nan Yes, but he explicitly stated such solutions don't exist.
@@dominik.sauer1 haha you got me. Only came to see if my conjecture is correct from the youtube notification thumbnail
Can't we simply factorise the LHS into (1+2^y)² which expands to (1+2.2^y+4^y) so we make 4^x=2.2^y so x=(y+1)/2. By symmetry we can also swap x and y. Thus for any odd natural number t we have solutions (x,y,z)=((t+1)/2,t,1+2^t) and (t,(t+1)/2,1+2^t)
4^y-1 cannot be m+1 because IF that was true, then 4^(x-y) +1 would HAVE TO be equal to m, which would mean 4^(y-1) -1 is EQUAL to 4^(x-y) +1. This CANNOT BE TRUE.
x = 1, y = 1, z = 3.
9:16
Let
A=2*3 and B =5*7
And
A'=2*5 und B'=3*7
The an neither AlA' nor BIA' ist true
What am i missing
unfortunately with your errors this time around 9:00 and 10:33 i cannot really agree on this conclusion without having to prove it independently. you had: the inequality: 4^(x-1) x-1 >= 2y-2, which is a strict violation of the definition of an increasing function.
I have a sol'n... This is general solution...
That is... X= k s.t. k belongs to N
Y = 2k-1
Z = 2*4^(k-1)+1
I found it by this way...
Since LHS is odd so Z is odd...
Put z=2k+1
WLOG assume x 4^x+4^y=4k(k+1)
There is 2 case k is odd or k is even
K is odd don't work (Why?)
If k is even then
4^x(4^(y-x)+1)=4k(k+1)
Since k+1 is the only odd part of the eqn
So k+1 = 4^(y-x)+1
=>k = 4^(y-x)
Again from the eqn we get
K=4^(x-1)
Thus y=2x-1
Then just substitute and get sol'n
I would really appreciate that someone could explain me this part 5:40
Hello Michael! I did my own solution without watching the video at first, and came to the same result y=2x-1. I did not verify that this is the only solution, as my transformations are all equivalences and "no assumptions or something 'hopeful'". So my question: is verifying the uniqueness of the solution a "must"?
(If you like I can do a video of my own proof and post it in YT).
There are many mistakes in this vid. I hope prof Penn removes this video.
not remove: correct. update the title and link to a correction in the description. i don't get why people are so delete-happy
한국 파이팅
fascinating
Hi. Thx a lot. Please teach Farey series
Thank you very much for your videos! They're amazing. Could you please solve some combinatorics problems? Especially graph theory. I think you can show all the beauty of these problems. Thanks!
So many mistakes in this one unfortunately, I suggest adding some correction to it.
using the same reasoning in the video ua-cam.com/video/wviiZlYRaGE/v-deo.html
and using the fact 2y>x+1 (equality case used to produce the two sol sets) which leads to x-y
8^1=9^2
한국인 손 ㅋㅋㅋ
손
(1,2,5) is a solution which isnt covered in any of your family of solutions
I LOVE YOU
Incredibale
Good
1-1-3
I have a problem for you to try. Solve for x,y,z in the bound [4,40] such that x+y+z=62 and xyz=2880. Please try this problem.
What is the definition of a mathematicians
I spotted three major mistakes in this video ... You rarely make any major mistakes in your videos. Strange.
There is a faster method. Illegal because technically I used the answer x=y =1 and z= 3 but it gets the answer quicker.
Are you a mathematicians.
뭔진 모르겠고 1+4^3/2 + 4^2 = 5^2 는 찾음
ㅈㄴ 어렵게 생겼네 ㅋㅋㅋ