Blackpenredpen, Lemme tell you this. If e to the iø = cos ø + i sin ø, what if we plugged in i for ø? Well, we would get e to the ii or e to the i squared or e to the -1, a real number. We also see that cos i + i sin i = e to the -1. But what is cos i and sin i? Pls tell me. Edit: i had to use ø instead of the actual symbol because i could not find it.
I solved it using brute force (binary number with all 1's, eight 1's and one 00, seven 1's and one 00, six 1's and two 00's, etc), but this method is beautiful! Did not expect fibonacci at all!
A slightly quicker way to sum the Fibonacci numbers and get to the 144 answer would be just to write down the next two Fibonacci numbers: 89, 144. This is because the sum of the first n Fibonacci numbers [ F(1) ->F(n) ] is F(n+2)-1. In this case you are adding 1 to that, so the number you need (144) is literally the one-after-next Fibonacci number :-)
I think that if you set those functions and you prove that for any positive integer P the ammount of positive integers inside the set S smaller or equal than that number P is always greater or equal to P then you have proven the collatz conjecture but that’s just speculation.
Thanks Sir for such a wonderful video. In my 17 years of life never changed base in solving such questions. It was really like out of the box for me atleast. 😊
As someone who loves competitive programming, my first thought was that this question could be solved with a dynamic programming approach in binary: Let us define subproblem A_n as the number of non-negative integers that can be reached by a combination of f(x) and g(x) with the first n binary digits. We can then show that there are 2 different ways to get to any number counted in A_n: Through applying f(x) to any number counted in A_(n-1), or applying g(x) to any number counted in A_(n-2), since f(x) will consistently add 1 binary digit to any number counted in A_(n-1), and g(x) will consistently add 2 binary digits to any number counted in A_(n-2). We also need to show that any number reached by f(x) cannot be reached via g(x). This can be showed by the fact that f(x)'s output is always odd, while g(x)'s output is always even. Thus, A_n = A_(n-2) + A_(n-1), accounting for both methods of reaching n binary digits, and we are assured we do not over-count from the last fact we proved. We are also assured that we never under-count due to the fact that 0 is included in all A_n, which means that A_(n+x) for all integer x includes A_x. We can then find A_0 to be 1, and A_1 to be 2, through obvious means. We can also show that 0 is always included in the subproblem, thus there are A_n - 1 positive integers that can be reached by a combination of f(x) and g(x) in the first n binary digits. Through the formula we proved, we can find A_2 to be A_0 + A_1 = 1 + 2 = 3, and A_3 to be A_1 + A_2 = 2 + 3 = 5. We then repeat this process until we find A_10, which is equivalent to solving the problem for all non-negative integers
In competitive programming your solution will be too slow. Fibonacci much quicker calculated by fast doubling or matrix exponentiation. Choose functions are much faster calculated by multiplying factorials together. There is the "stars and bars" aka "binomial theorem for negative exponents" and that just wants choose functions. The numbers here is just the regular expressions ^(1*00)*1*$ which is more like formal languages and automata.
While solving this (after learning the binary trick from you because I couldn't work that bit out) I managed to miss the Fibonacci sequence right in front of me. Found a nifty double summation from pascals triangle though to calculate the result. I got this summation knowing that it was probably a nice recurrence and I thought about different ways I could prove what it was, but I never stopped to actually read the numbers in the sequence! Very nice problem. The binary trick is definitely the hardest part I enjoyed solving it.
They are both increasing functions, so we could enumerate them in a reasonable amount of time by expanding the smallest number using both functions. 0 -> 1,0 1-> 3,4 3-> 7,12 4-> 9,16 7-> 15,28 9-> 19,36 12 -> 25,48 15 -> 31,60 16-> 33,64 ... at a modest 10 per minute, we will be done in under an hour.
(I solved it before watching) I started by figuring out that each permutation of functions would result in a different positive integer (i.e. no two combinations of functions would result in the same integer being produced) Next, by converting to base 2, I decided to see it as how the number of digits would increase after each function. f would cause the integer to increase in length by 1 digit, g would cause the integer to increase in length by 2 digits. I then started with 1, since 1 was already an element of S. With the exception of 1 and g⁵(1), all other integers in S had at least 2 digits and at most 10 digits in base 2. So all I needed to find was how many different ways I could increase the length of 1 by up to 9 digits With f increasing the length of the number by 1 digit and g by 2, letting d(n) be the number of ways I could increase the number of digits by n, I had d(1) = 1, d(2) = 2. This led me to a recurrence relation where d(n+2) = d(n+1) + d(n). Since my first 2 terms were 1 and 2, it just became the Fibonacci sequence as a result. Summing d(1) through d(9), I had 142. Since this excluded 1 and g⁵(1), I added them back and got 142 + 2 = 144. (Coming back after watching) Welp I did it. The main difference was that I counted the number ways I was increasing the number of digits rather than the number of digits for each number but the principle behind each way was still the same.
This was more or less what I did, though I had a leg-up in having seen the Fibonacci recurrence in a very similar context (to do with climbing stairs one or two at a time) a few years ago.
Not sure if anyone will see this but I have devised a formula for a^3-b^3 which I believe is easier to use and can help solve a lot of different types of problems. The original formula: (a-b)(a^2+b^2+ab) My formula: x(x^2+3bx+3b^2) where x = a-b The reason I believe this formula is better is because it doesn’t rely on the variable a, if they ask a problem to find a while giving a-b and a^3-b^3 this could make the solving process easier because when I tried to solve it then traditional way it took a lot of time. This also is useful for finding a^3-b^3 by hand. Let a=2763 and b=2760 3(2763^2+2760^2+2763*2760) vs 3(9+9*2760+2760^2) In the traditional way, you have to find 2763*2763, 2760*2760 and 2763*2760 which would take forever but in my way you just need to find 2760^2 and 2763*3 which is way easier because as I timed it and it took me 5x longer to do it the traditional way. If you have any opinion on this formula and have any changes please let me know in the reply section!
I solved it in a similar way but instead of grouping cases by the length of the number created I grouped them by the # of building blocks used (1s and 00s). That way cases can be easily summed up (using powers of 2) because they form Pascal's Triangle, or at least part of it, but that can be easily corrected by hand.
was your method something along the lines of sticking a 1 in the front, and using n 1 blocks and m 0 blocks, there are (m+n)Cn different bit strings and then add up all cases for all possible m,n such that 2m+n
When you write all possible numbers in binary, I can see that when choosing digits for n slots, we have 2 possibilities: If it ends with 1, the options for other digits are the same as that of n-1 slots If it ends with 0, the options for other digits are the same as that of n-2 slots ( the 2^1 digit has to be 0) This means the number of options for n slots is #(n-1)+#(n-2) => creating the Fibonacci sequence.
my solution before watching the video: 4n -> appends 2 0s to the number in binary 2n+1 -> appends a 1 to the number in binary consider a "moveset" where you can either add 2 0s or 1 1 to the end of a number. Let F[n] be the number of ways to make a number starting with 1 with n digits in this manner. F[n] = F[n-1] + F[n-2], since you can either reach n digits from n-2 by adding a 00, or from n-1 by adding a 1. F[1] = 1 (1) F[2] = 1 (11) F[3] = 2 (111, 100) .... add up the first 10 fibonacci numbers and you're done (adding 1 more for 1024)
Sorry for m bad english Step 1 1) f(n) is odd and g(n) is even so for all n f(n) g(n) 2) f and g are injective and increasing functions 3) g(0) = 0 so we'll treat it apart (we an consider the seed to be 1 and add 0 at the end) Lemma Every different composition of f and g applied to 0 when f is applied first, give different images: Let k by the maximum number of functions in one composition Proof by induction on k. If k = 1 see point 1). For k+1: if f(composition of k functions on 0) = g(composition of l function on 0) is impossible by 1) and if f(composition of k functions) = f(composition of l function), l f^(k-1)(8n+1) = f^(k-1)(f(4n)) = f^k(g(n)) (moving g to the left decreases the result) ** So for all n > 0 f^(k+1) (n) < g(f^k(n)) < f^k(g(n)) < f^(k+2) (n) by * and ** Summary: we can apply f 10 times on 0 before passing 1024 and applying g counts as applying f twice. Applying f is 1 point, applying g is 2 points and we need to apply f first. If the number of ways to reach k point is a_k, we have a_k = a_(k-1) + a_(k-2). Proof by induction: For k = 1 and k = 2 we only have 1 possibility f(0) and f(f(0)) (f is always applied first) For k = 3 we have f(f(f(0))) and g(f(n)) so 2 possibilities For k+1, look at the last function applied, we have 2 cases: 1) g(something), something has exactly k-2 points 2) f(something), something hads exactly k-1 points By the lemma every single one of them give different results, so we have a total a_(k-2) + a_(k-1) possibilities. And now we only have to add the fibonnaci numbers up to the 11th (since the first one is 0), and it gives the 13th fibonnaci number minus 1, 143 (easy proof by induction, f_1 + f_2 + f_3 = 1 = 3 - 1 = f_5 - 1. f_1 + ... + f_(k+1) = f_1 + ... + f_(k_1) + f(k+2) = f(k+1) - 1 + f(k+2) = f(k+3) - 1) We finally need to add 0 so the total is 144.
I solved it on my own in a similar way, and when I wrote the recurrence and saw Fibonacci I just jumped in excitement! This is such a nice problem, I loved it
I solved it by constraining the maximum value of 1024, putting f and g on the x y axis, counted all positive intersections within the graph of y = 5-0.5x, for each intersection find the xCy value on the pascals triangle, and added them together. After the video I learnt the relation between pascals triangle and fibonacci. it is whack.
In general, the number of positive integers less than 2^n that can be represented as such is precisely F_{n+2}-1, and in the problem the additional 1 is added due to 2^10 being a power of 4 (as I completely forgot when I initially solved the problem :P).
plz make a video on solving x^3 - 2x -1 using the cubic formula and making a trigonometric substitution x=rcos(theta) where r is chosen such that we get cos(3theta). when you get to the final trigonometric form, prove that it's phi. also prove the cubic formula for x^3 + px + q using trig sub x=rcos(theta) where r is chosen to get cos(3theta)
would be pissed if I had been denied entrance to Oxford for not being able to make a dent in this problem. Even your modified version is Verboten even though you helped quite a bit!
The method I used led to the same casework: note that 2n+1 doubles it but increases it too afterward, so treat the operations like powers of 2 with an upper limit of 2^9 instead of 2^10 when you use 2n+1, and add 1 for the case of 2(0)+1 = 1 --> 4n applied 5 times for 1024.
I built some code for iterating F and G into each other multiple times, but I couldn't figure out an exhaustive way to go through all the possible sequences. My method for checking the results was to use the resulting integers as the index for writing a value of 1 to an array, then summing the elements of that array once everything is done. But since I was left with manually inputting the sequences (i.e., applying F some number of times, then G some number of times, then F some number of times, etc. until the value exceeds 1024), I missed some and ended up counting 137, which is notably less than what other comments are saying it is. So yeah pretty sure I needed a more fully systematic way to iterate through all the combinations. Edit: 15:50 this is where I got stumped by my method -- i couldn't think of a way to do it other than guessing and checking with each amount of leading F (or leading 1s in your approach), and that took way too long and had too much room for error.
Steve write program for this question C# is a good choice for Windows users\ Convert numbers to binary Show the recursion Recursion appears to be the same as for shifted Fibonacci sequence
Hello. I’ve been enjoying a lot of your videos lately. I had a silly request. Would you be able to work the phrase “Name a more iconic duo” into one of your problem prompts? Just for the fun of it? :)
Hi to everyone. In some of the videos on this channel, there was one in which Mr. Blackpen talked about a certain book of analysis or calculus, I don't remember. The point is that he recommended it, and the exercise he did in that video came from that book. I only remember the color of the book, blue, and it has formulas written on the cover. Actually, I watched that video around 3 years ago. I have an idea that it was written by an Indian author, but I am not sure. Sorry if I don't have more details about it, but I will really appreciate it if someone remember that book. Thank you!
Recently started learning to code so immediately went to that after seeing the question. Here's my stupid-looking-cuz-i've-watched-the-video-now python code. count = 0 for i in range(1025): num = i while True: if num == 0: count += 1 break elif num / 4 == int(num / 4): num = num / 4 elif (num-1)/2 == int((num-1)/2): num = (num - 1) / 2 else: break print(count -1)
I solved this using the negative approach counting numbers not belonging in S. We can see that all numbers of form 4k+2 don't belong in S. As for 8k + m, we count values of m for which the numbers are not already included in previous forms aka 4k+2 so m here takes up 5 as putting 4k+2 in f gives us that. And for 16k+m, m receives a value for each value in form 4k+m and 8k+m as putting them in g and f presents us with form 16k+m, so the number of values in m follows the Fibonacci sequence. So for ak+m, a taking up value 4,8,..1024, m takes up 1,1,...21 values each. Multiplying first 1 by 256 because for number 4k+m to be less than 1024, k can take 256 values, similarly next 1 by 128, next 2 by 64 and so on upto 21 by 1, we get a total of 880 values which don't belong in S. So the no. of values in S becomes 144. I'm sure the way I explained my method is really bad, I've never been good at explaining😅. Please ask in replies so i can clarify🙂.
"we count values of m for which the numbers are not already included in previous forms" I think you meant 8k+m is the form of numbers not included in the form 4k+2
So u included 10000000000=1024 w/ the +1, but u forgot to also add +1 for the 0 in S. W/ that I think the answer's 145. But either way, great video! I've never considered switching to base 2 for an odd even proof, but looking back it makes a lot of sense!
S contains only positive integers. 0 is nonnegative but it is not positive. Of course, a small detail like that does not affect the elegance of the solution.
Of course, this only is a small detail but this is really puzzling to me : 0 ≥ 0, therefore 0 is a positive number, isn't it? Aren't positive numbers, integers and natural numbers all synonyms? It doesn't make sense to me to exclude 0 from the list of integers. Integers are canonically constructed from the empty set, so you can't even construct any other number without accounting for 0.
Hello friends. Lemme tell you this. If e to the iø = cos ø + i sin ø, what if we plugged in i for ø? Well, we would get e to the ii or e to the i squared or e to the -1, a real number. We also see that cos i + i sin i = e to the -1. But what is cos i and sin i? Pls tell me. Edit: i had to use ø instead of the actual symbol because i could not find it.
First, e^(ix)=cos(x)+i*sin(x). So e^(-ix)=cos(x)-i*sin(x) since cos is even and sin is odd. So e^(ix)+e^(-ix)=2*cos(x) and e^(ix)-e^(-ix)=2i*sin(x). So cos(x)=(e^(ix)+e^(-ix))/2 and sin(x)=(e^(ix)-e^(-ix))/(2i)=i(e^(-ix)-e^(ix))/2. So cos(i)=(e^(-1)+e)/2 and sin(i)=i(e-e^(-1))/2.
cos i = cosh 1 sin i = i*sinh 1 You can show this using the complex definitions of sin, cos, as well as the definition of sinh and cosh. Then just use a calculator.
Hey! This might be a bit much to ask, but could you do a video that explains how the complex plane works? It would be great because I’m trying to get ahead going into algebra 2 and some of your videos confused me
Huh, I never even converted to binary to solve this problem. Instead I looked at what numbers you can get if you lower the limit and then successively increase it. I did so in powers of two as I recognised 1024 as being a power of two and thus relevant to the problem. Then I considered which numbers you can apply the functions to, because if you can apply either function, you get a new number. And from that I made a set of recursive equations that encapsulated the behaviour of the number of numbers as the limit goes up
Great! I'm just wondering why the fibonacci appears in this pattern, the one thing that left me uneasy is that u assume the pattern holds after seeing it work for the first five powers of 2, but u don't prove that the combinatorics problem results in the fibonacci numbers
solved using a java program, but I suppose this wouldn't be allowed on a real exam basically there's this method public static boolean isInSetS(int number){ if (number == 0) { return true; }
i dont disagree with the solution but how would you go about actually proving that the number of integers can be calculated with the fibonacci sequence?
When looking at a number with a given number of digits say 5, you have 4 free digits since there is always a leading 1, call it n. Then you fix the last digit with 1, and ask how numbers you can fill with the remaining free n-1 digits. Or you fix the last two digits with 0s and ask how many numbers can fill the remaining n-2 digits. Then you get your recurrence relation: count of numbers with n free digits = count of numbers with n-1free digits + count of digits with n-2 free digits. The base cases of 0 free digits and 1 free digit are 1, together give exactly the Fibonacci sequence.
When he puts the 1 at the last spot, the number of the remaining spots are the same as the last number's spots, and when he puts 00 at the last two spots, the number of the spots remaining are the same as the last before number's spots.
Let's say you want to find out how many numbers with k digits in base 2 are there in S. Lets call this function x(k). You can get a k-digit number only by applying f to a (k-1)-digit number, or applying g to a (k-2)-digit number. Therefore x(k) = x(k-1) + x(k-2) and you have the fibonacci sequence.
8+2n=2^(n) We divide both sides by 2 4+n=2^(n-1) Now we want to get the solution of the equation for natural numbers Let n-1=N+1 4+(N+2)=2^(N+1) (N+2) Move to the right 4=2^(N+1)-(N+2) The right side is equal to the sum of combinations from zero to N 4=nCr(1,0)+nCr(2,0)+nCr(2,1)+....nCr(N,0) We calculate the values of each of these combinations nCr(1,0)=1!/(0!1!)=1 nCr(2,0)=2!/(0!2!)=1 nCr(2,1)=2!/(1!1!)=2 Their sum is equal to 4 As result 4=nCr(1,0)+nCr(2,0)+nCr(2,1)=4 N=2. So n=N+2=4
I tried using a probablity tree diagram and then sumed the terms of the geometric sequence of ratio 2. Found that 129 is the answer.( 2^7+1). Can anyone tell me why am I wrong?
i graduated from high school and i am from morroco and i think i should improve my math level can someone please give me some advices, maybe ressources that i could use. Sorry if there any spelling mistake not very familiar with the language
[WARNING: THIS COMMENT WAS WRITTEN BEFORE I WATCHED THE VIDEO, I HAVE NO IDEA IF IT IS CORRECT] My solution: In binary, f(x) looks like appending 1, and g(x) looks like appending 00. Then count. 0 digits: 0 (0) //you'll see why I do this later 1 digit: 1 (1) 2 digits: 1 (11) 3 digits: 2 (111, 100) 4 digits: 3 (1111, 1001, 1100) 5 digits: 5 (11111, 10011, 11001, 11100, 10000) Notice, that if D(N) is the number of numbers with exactly N digits in binary that can be reached with f(n) and g(n), then D(N) = D(N-1) + D(N-2). Why? Because D(N-1) means adding the 1, and D(N-2) means adding the 00. And they have to be distinct and disjoint because they have different lengths and end in different digits. So given that D(1) = 1 and D(2) = 1, the rest follows nicely as the fibonacci series! Now we just need to figure out D(1) + ... + D(10) + 1 (for the number 1024 itself which can be reached by g(g(g(g(g(f(0))))))) I won't prove it here but there's a result that the sum of the first N fibonacci numbers is F_(N+2) - 1. So that's 1 + 1 + 2 + ... + 55 + 1 = (144 - 1) + 1 = 144. Done! EDIT: i miscounted and only went up to 9 digits and not 10... oops
@@stephenbeck7222 But this is not a Fibonacci number. This is the summ of first 10 Fibonacci number plus one. How is it related to Michael Penn's proof?
It's half a coincidence. The sum of the first n fibonacci numbers is another fibonacci number (minus one). The coincidence is that 144 is a fibonacci number and a square.
Applying g(n)=4n in base 4 is just adding a zero, but what about f(n)=2n+1 ? For example 27 in base 4 is 123. f(27) = 55, which in base 4 is 313. f(f(27)) = f(55) = 111, in base 4 is 1233. This is because 2(2n+1)+1 = 4n+3. Applying f two times in a row means attaching a 3 at the end in base 4, but that's not really helpful enough. Compared to base 2, there isn't a nice pattern here that makes it easy to see what's going on.
Check out Brilliant: 👉brilliant.org/blackpenredpen/ (20% off with this link!)
Where you can find thos cool math questions?
Please, please, please let me know!!!
Blackpenredpen, Lemme tell you this. If e to the iø = cos ø + i sin ø, what if we plugged in i for ø?
Well, we would get e to the ii or e to the i squared or e to the -1, a real number. We also see that cos i + i sin i = e to the -1. But what is cos i and sin i?
Pls tell me.
Edit: i had to use ø instead of the actual symbol because i could not find it.
I solved it using brute force (binary number with all 1's, eight 1's and one 00, seven 1's and one 00, six 1's and two 00's, etc), but this method is beautiful! Did not expect fibonacci at all!
i used python for this and got that S has 334 numbers
@@ttermitnice 💀
@@ttermit I used breadth first search to generate all the combinations and i got 145 :D
I solved it by watching RUclips. In fact, this exact video.
A slightly quicker way to sum the Fibonacci numbers and get to the 144 answer would be just to write down the next two Fibonacci numbers: 89, 144. This is because the sum of the first n Fibonacci numbers [ F(1) ->F(n) ] is F(n+2)-1. In this case you are adding 1 to that, so the number you need (144) is literally the one-after-next Fibonacci number :-)
Now let f(n) = 3n+1 and g(n) = n/2
I think that if you set those functions and you prove that for any positive integer P the ammount of positive integers inside the set S smaller or equal than that number P is always greater or equal to P then you have proven the collatz conjecture but that’s just speculation.
@@guillermo3412 this can’t work unfortunately because g(n)
@@tristan9585 so? What’s your point exactly.
Isn't it the collatz conjecture
i was also thinking of collatz the whole time
Thanks Sir for such a wonderful video. In my 17 years of life never changed base in solving such questions. It was really like out of the box for me atleast. 😊
"I'm just going to start from small and then look for a pattern and hope for the best" sums up all the struggle of solving olympiad questions
As someone who loves competitive programming, my first thought was that this question could be solved with a dynamic programming approach in binary:
Let us define subproblem A_n as the number of non-negative integers that can be reached by a combination of f(x) and g(x) with the first n binary digits. We can then show that there are 2 different ways to get to any number counted in A_n: Through applying f(x) to any number counted in A_(n-1), or applying g(x) to any number counted in A_(n-2), since f(x) will consistently add 1 binary digit to any number counted in A_(n-1), and g(x) will consistently add 2 binary digits to any number counted in A_(n-2).
We also need to show that any number reached by f(x) cannot be reached via g(x). This can be showed by the fact that f(x)'s output is always odd, while g(x)'s output is always even.
Thus, A_n = A_(n-2) + A_(n-1), accounting for both methods of reaching n binary digits, and we are assured we do not over-count from the last fact we proved. We are also assured that we never under-count due to the fact that 0 is included in all A_n, which means that A_(n+x) for all integer x includes A_x.
We can then find A_0 to be 1, and A_1 to be 2, through obvious means. We can also show that 0 is always included in the subproblem, thus there are A_n - 1 positive integers that can be reached by a combination of f(x) and g(x) in the first n binary digits.
Through the formula we proved, we can find A_2 to be A_0 + A_1 = 1 + 2 = 3, and A_3 to be A_1 + A_2 = 2 + 3 = 5.
We then repeat this process until we find A_10, which is equivalent to solving the problem for all non-negative integers
In competitive programming your solution will be too slow. Fibonacci much quicker calculated by fast doubling or matrix exponentiation. Choose functions are much faster calculated by multiplying factorials together. There is the "stars and bars" aka "binomial theorem for negative exponents" and that just wants choose functions. The numbers here is just the regular expressions ^(1*00)*1*$ which is more like formal languages and automata.
Counting is an underappreciated form of art in maths
While solving this (after learning the binary trick from you because I couldn't work that bit out) I managed to miss the Fibonacci sequence right in front of me. Found a nifty double summation from pascals triangle though to calculate the result. I got this summation knowing that it was probably a nice recurrence and I thought about different ways I could prove what it was, but I never stopped to actually read the numbers in the sequence! Very nice problem. The binary trick is definitely the hardest part I enjoyed solving it.
They are both increasing functions, so we could enumerate them in a reasonable amount of time by expanding the smallest number using both functions.
0 -> 1,0
1-> 3,4
3-> 7,12
4-> 9,16
7-> 15,28
9-> 19,36
12 -> 25,48
15 -> 31,60
16-> 33,64
...
at a modest 10 per minute, we will be done in under an hour.
(I solved it before watching) I started by figuring out that each permutation of functions would result in a different positive integer (i.e. no two combinations of functions would result in the same integer being produced)
Next, by converting to base 2, I decided to see it as how the number of digits would increase after each function. f would cause the integer to increase in length by 1 digit, g would cause the integer to increase in length by 2 digits.
I then started with 1, since 1 was already an element of S. With the exception of 1 and g⁵(1), all other integers in S had at least 2 digits and at most 10 digits in base 2. So all I needed to find was how many different ways I could increase the length of 1 by up to 9 digits
With f increasing the length of the number by 1 digit and g by 2, letting d(n) be the number of ways I could increase the number of digits by n, I had d(1) = 1, d(2) = 2.
This led me to a recurrence relation where d(n+2) = d(n+1) + d(n). Since my first 2 terms were 1 and 2, it just became the Fibonacci sequence as a result. Summing d(1) through d(9), I had 142.
Since this excluded 1 and g⁵(1), I added them back and got 142 + 2 = 144.
(Coming back after watching) Welp I did it. The main difference was that I counted the number ways I was increasing the number of digits rather than the number of digits for each number but the principle behind each way was still the same.
This was more or less what I did, though I had a leg-up in having seen the Fibonacci recurrence in a very similar context (to do with climbing stairs one or two at a time) a few years ago.
Not sure if anyone will see this but I have devised a formula for a^3-b^3 which I believe is easier to use and can help solve a lot of different types of problems.
The original formula: (a-b)(a^2+b^2+ab)
My formula: x(x^2+3bx+3b^2) where x = a-b
The reason I believe this formula is better is because it doesn’t rely on the variable a, if they ask a problem to find a while giving a-b and a^3-b^3 this could make the solving process easier because when I tried to solve it then traditional way it took a lot of time.
This also is useful for finding a^3-b^3 by hand.
Let a=2763 and b=2760
3(2763^2+2760^2+2763*2760) vs 3(9+9*2760+2760^2)
In the traditional way, you have to find 2763*2763, 2760*2760 and 2763*2760 which would take forever but in my way you just need to find 2760^2 and 2763*3 which is way easier because as I timed it and it took me 5x longer to do it the traditional way.
If you have any opinion on this formula and have any changes please let me know in the reply section!
I solved it in a similar way but instead of grouping cases by the length of the number created I grouped them by the # of building blocks used (1s and 00s). That way cases can be easily summed up (using powers of 2) because they form Pascal's Triangle, or at least part of it, but that can be easily corrected by hand.
was your method something along the lines of
sticking a 1 in the front, and using n 1 blocks and m 0 blocks, there are (m+n)Cn different bit strings
and then add up all cases for all possible m,n such that 2m+n
@@yashpermalla3494 Yes, basically that.
I basically did this and got a vastly different number than 144 and am struggling to see what I did wrong
When you write all possible numbers in binary, I can see that when choosing digits for n slots, we have 2 possibilities:
If it ends with 1, the options for other digits are the same as that of n-1 slots
If it ends with 0, the options for other digits are the same as that of n-2 slots ( the 2^1 digit has to be 0)
This means the number of options for n slots is #(n-1)+#(n-2) => creating the Fibonacci sequence.
Woah that's such a good explanation of how the Fibonacci sequence relates to this
please make more Oxbridge admissions test videos!
my solution before watching the video:
4n -> appends 2 0s to the number in binary
2n+1 -> appends a 1 to the number in binary
consider a "moveset" where you can either add 2 0s or 1 1 to the end of a number. Let F[n] be the number of ways to make a number starting with 1 with n digits in this manner. F[n] = F[n-1] + F[n-2], since you can either reach n digits from n-2 by adding a 00, or from n-1 by adding a 1.
F[1] = 1 (1)
F[2] = 1 (11)
F[3] = 2 (111, 100)
....
add up the first 10 fibonacci numbers and you're done (adding 1 more for 1024)
Base 2, Fibonacci, and the answer is a perfect square. What more could one ask for? Beautiful question, beautiful logic, beautiful answer!
Sorry for m bad english
Step 1
1) f(n) is odd and g(n) is even so for all n f(n) g(n)
2) f and g are injective and increasing functions
3) g(0) = 0 so we'll treat it apart (we an consider the seed to be 1 and add 0 at the end)
Lemma
Every different composition of f and g applied to 0 when f is applied first, give different images:
Let k by the maximum number of functions in one composition
Proof by induction on k. If k = 1 see point 1).
For k+1: if f(composition of k functions on 0) = g(composition of l function on 0) is impossible by 1) and
if f(composition of k functions) = f(composition of l function), l f^(k-1)(8n+1) = f^(k-1)(f(4n)) = f^k(g(n)) (moving g to the left decreases the result) **
So for all n > 0 f^(k+1) (n) < g(f^k(n)) < f^k(g(n)) < f^(k+2) (n) by * and **
Summary: we can apply f 10 times on 0 before passing 1024 and applying g counts as applying f twice. Applying f is 1 point, applying g is 2 points and we need to apply f first.
If the number of ways to reach k point is a_k, we have a_k = a_(k-1) + a_(k-2). Proof by induction:
For k = 1 and k = 2 we only have 1 possibility f(0) and f(f(0)) (f is always applied first)
For k = 3 we have f(f(f(0))) and g(f(n)) so 2 possibilities
For k+1, look at the last function applied, we have 2 cases:
1) g(something), something has exactly k-2 points
2) f(something), something hads exactly k-1 points
By the lemma every single one of them give different results, so we have a total a_(k-2) + a_(k-1) possibilities.
And now we only have to add the fibonnaci numbers up to the 11th (since the first one is 0), and it gives the 13th fibonnaci number minus 1, 143 (easy proof by induction, f_1 + f_2 + f_3 = 1 = 3 - 1 = f_5 - 1.
f_1 + ... + f_(k+1) = f_1 + ... + f_(k_1) + f(k+2) = f(k+1) - 1 + f(k+2) = f(k+3) - 1)
We finally need to add 0 so the total is 144.
I love how he shows his struggles with questions ❤
I solved it on my own in a similar way, and when I wrote the recurrence and saw Fibonacci I just jumped in excitement! This is such a nice problem, I loved it
I solved it by constraining the maximum value of 1024, putting f and g on the x y axis, counted all positive intersections within the graph of y = 5-0.5x, for each intersection find the xCy value on the pascals triangle, and added them together.
After the video I learnt the relation between pascals triangle and fibonacci. it is whack.
This is so mindblowing, it would have taken me forever to realize that it is clever to use base 2 numbers
In general, the number of positive integers less than 2^n that can be represented as such is precisely F_{n+2}-1, and in the problem the additional 1 is added due to 2^10 being a power of 4 (as I completely forgot when I initially solved the problem :P).
plz make a video on solving x^3 - 2x -1 using the cubic formula and making a trigonometric substitution x=rcos(theta) where r is chosen such that we get cos(3theta). when you get to the final trigonometric form, prove that it's phi. also prove the cubic formula for x^3 + px + q using trig sub x=rcos(theta) where r is chosen to get cos(3theta)
would be pissed if I had been denied entrance to Oxford for not being able to make a dent in this problem. Even your modified version is Verboten even though you helped quite a bit!
It's Impossible to understand the Oxford questions until the all mighty Blackpenredpen steps in and clears the confusion up!
Happy Birthday BPRP!
Thank you!
Thank you!
This is great . Please do more of this kind
Every math video is more fascinating than the one before. Amazing.
Another great question would be to prove that the number of positive integers less than or equal to 2^n is F(n+2)
Once I saw 1024 = 2^10 there, to me that was a hint that binary numbers had to be important somehow.
The method I used led to the same casework: note that 2n+1 doubles it but increases it too afterward, so treat the operations like powers of 2 with an upper limit of 2^9 instead of 2^10 when you use 2n+1, and add 1 for the case of 2(0)+1 = 1 --> 4n applied 5 times for 1024.
You: "pause the video and try this first" me: "No"
The limit of 1024 = 2^10 was a big hint as well that base 2 was important.
Nice. Very pleased to figure out in a couple of minutes how the binary expansion of members of S must look.
The mere mention of 2^10 in the Q is a big hint to consider binary.
Brilliant way of solving this. I got the right answers, but only by trial and error of the solutions given in the multiple choice question😂😂
I built some code for iterating F and G into each other multiple times, but I couldn't figure out an exhaustive way to go through all the possible sequences. My method for checking the results was to use the resulting integers as the index for writing a value of 1 to an array, then summing the elements of that array once everything is done. But since I was left with manually inputting the sequences (i.e., applying F some number of times, then G some number of times, then F some number of times, etc. until the value exceeds 1024), I missed some and ended up counting 137, which is notably less than what other comments are saying it is. So yeah pretty sure I needed a more fully systematic way to iterate through all the combinations.
Edit: 15:50 this is where I got stumped by my method -- i couldn't think of a way to do it other than guessing and checking with each amount of leading F (or leading 1s in your approach), and that took way too long and had too much room for error.
Hi, can I ask what code you used?7
Steve write program for this question
C# is a good choice for Windows users\
Convert numbers to binary
Show the recursion
Recursion appears to be the same as for shifted Fibonacci sequence
man i love combinatorics and discrete math
ayy, i did this question the other day, you and Flammable etc. need to to more MAT questions!
Hello. I’ve been enjoying a lot of your videos lately. I had a silly request. Would you be able to work the phrase “Name a more iconic duo” into one of your problem prompts? Just for the fun of it? :)
Happy birthday!!!
Thank you!
Hi to everyone. In some of the videos on this channel, there was one in which Mr. Blackpen talked about a certain book of analysis or calculus, I don't remember. The point is that he recommended it, and the exercise he did in that video came from that book. I only remember the color of the book, blue, and it has formulas written on the cover. Actually, I watched that video around 3 years ago. I have an idea that it was written by an Indian author, but I am not sure. Sorry if I don't have more details about it, but I will really appreciate it if someone remember that book. Thank you!
Very good explanation bro I am from india🎉🎉
Now imagine f(n) = 3n+1 and g(n) = n/2 all in base 6 😀
you're awesome dude, thank you
Recently started learning to code so immediately went to that after seeing the question. Here's my stupid-looking-cuz-i've-watched-the-video-now python code.
count = 0
for i in range(1025):
num = i
while True:
if num == 0:
count += 1
break
elif num / 4 == int(num / 4):
num = num / 4
elif (num-1)/2 == int((num-1)/2):
num = (num - 1) / 2
else: break
print(count -1)
I solved this using the negative approach counting numbers not belonging in S.
We can see that all numbers of form 4k+2 don't belong in S. As for 8k + m, we count values of m for which the numbers are not already included in previous forms aka 4k+2 so m here takes up 5 as putting 4k+2 in f gives us that. And for 16k+m, m receives a value for each value in form 4k+m and 8k+m as putting them in g and f presents us with form 16k+m, so the number of values in m follows the Fibonacci sequence.
So for ak+m, a taking up value 4,8,..1024, m takes up 1,1,...21 values each.
Multiplying first 1 by 256 because for number 4k+m to be less than 1024, k can take 256 values, similarly next 1 by 128, next 2 by 64 and so on upto 21 by 1, we get a total of 880 values which don't belong in S.
So the no. of values in S becomes 144.
I'm sure the way I explained my method is really bad, I've never been good at explaining😅. Please ask in replies so i can clarify🙂.
I think I understand your method -- it was my first idea as well. You did the final step wrong though-- 1024 - 880 = 144, not 140
@@yf-n7710 ya my bad, mistyped it
"we count values of m for which the numbers are not already included in previous forms" I think you meant 8k+m is the form of numbers not included in the form 4k+2
@@gytoser801 ya pretty much, that also extends for 16k+m and so on...
not very hard but still proud to do it :) Also i found cute generalisation- number of such numbers less or equal than 2^n is F_(n+2)
So u included 10000000000=1024 w/ the +1, but u forgot to also add +1 for the 0 in S. W/ that I think the answer's 145. But either way, great video! I've never considered switching to base 2 for an odd even proof, but looking back it makes a lot of sense!
Oh S only contains positive integers
S contains only positive integers. 0 is nonnegative but it is not positive.
Of course, a small detail like that does not affect the elegance of the solution.
0 is whole number not natural number
@@geneyoungdhothis question talks about positive integers, not natural numbers. 0 is a natural number from ISO-800002
Of course, this only is a small detail but this is really puzzling to me : 0 ≥ 0, therefore 0 is a positive number, isn't it? Aren't positive numbers, integers and natural numbers all synonyms?
It doesn't make sense to me to exclude 0 from the list of integers. Integers are canonically constructed from the empty set, so you can't even construct any other number without accounting for 0.
I never knew that we could use number conversions to do maths questions. I wonder if it is studied in mathematics also as it is in programming.
I dont understand the final solution, why didn't you continue the fibonacci sequence until your reach 2¹⁰? Why was adding +1 for 2⁵enough?
Hello friends. Lemme tell you this. If e to the iø = cos ø + i sin ø, what if we plugged in i for ø?
Well, we would get e to the ii or e to the i squared or e to the -1, a real number. We also see that cos i + i sin i = e to the -1. But what is cos i and sin i?
Pls tell me.
Edit: i had to use ø instead of the actual symbol because i could not find it.
First, e^(ix)=cos(x)+i*sin(x).
So e^(-ix)=cos(x)-i*sin(x) since cos is even and sin is odd.
So e^(ix)+e^(-ix)=2*cos(x) and e^(ix)-e^(-ix)=2i*sin(x).
So cos(x)=(e^(ix)+e^(-ix))/2 and sin(x)=(e^(ix)-e^(-ix))/(2i)=i(e^(-ix)-e^(ix))/2.
So cos(i)=(e^(-1)+e)/2 and sin(i)=i(e-e^(-1))/2.
cos i = cosh 1
sin i = i*sinh 1
You can show this using the complex definitions of sin, cos, as well as the definition of sinh and cosh. Then just use a calculator.
generally for complex trig, cos(z) = (e^iz + e^-iz)/2 and sin(z) = (e^iz - e^-iz)/2i, so you can evaluate the expressions that way.
@@yashpermalla3494 I’d like to say this but you already answered
Thanks PROF more videos like this 😘
I think we all "aha"'d when he first talked about seeing the pattern
Yep, I was like "Hey, that's our good old friend Fibonacci!"
Hey! This might be a bit much to ask, but could you do a video that explains how the complex plane works? It would be great because I’m trying to get ahead going into algebra 2 and some of your videos confused me
there are tons of videos on elementary topics like this
Huh, I never even converted to binary to solve this problem. Instead I looked at what numbers you can get if you lower the limit and then successively increase it. I did so in powers of two as I recognised 1024 as being a power of two and thus relevant to the problem. Then I considered which numbers you can apply the functions to, because if you can apply either function, you get a new number. And from that I made a set of recursive equations that encapsulated the behaviour of the number of numbers as the limit goes up
Where you can find thos cool math questions?
Please, please, please let me know!!!
Great! I'm just wondering why the fibonacci appears in this pattern, the one thing that left me uneasy is that u assume the pattern holds after seeing it work for the first five powers of 2, but u don't prove that the combinatorics problem results in the fibonacci numbers
If blackpenredpen mentions his "hardest problem this year", then you know you are in for something brutal.
Amazing!!
solved using a java program, but I suppose this wouldn't be allowed on a real exam
basically there's this method
public static boolean isInSetS(int number){
if (number == 0) {
return true;
}
if (number % 4 == 0) {
return isInSetS(number / 4);
} else if ((number - 1) % 2 == 0) {
return isInSetS((number - 1) / 2);
} else {
return false;
}
}
then use a for loop (until i
Yeah the MAT (the test which this comes from) is all maths based, so you won't be writing any code
Function composition notation would have gotten rid of all those parentheses lol.
my ans is 261 before seeing the soln, will edit the msg later today after watching the video
i dont disagree with the solution but how would you go about actually proving that the number of integers can be calculated with the fibonacci sequence?
When looking at a number with a given number of digits say 5, you have 4 free digits since there is always a leading 1, call it n. Then you fix the last digit with 1, and ask how numbers you can fill with the remaining free n-1 digits. Or you fix the last two digits with 0s and ask how many numbers can fill the remaining n-2 digits. Then you get your recurrence relation: count of numbers with n free digits = count of numbers with n-1free digits + count of digits with n-2 free digits. The base cases of 0 free digits and 1 free digit are 1, together give exactly the Fibonacci sequence.
When he puts the 1 at the last spot, the number of the remaining spots are the same as the last number's spots, and when he puts 00 at the last two spots, the number of the spots remaining are the same as the last before number's spots.
Let's say you want to find out how many numbers with k digits in base 2 are there in S. Lets call this function x(k).
You can get a k-digit number only by applying f to a (k-1)-digit number, or applying g to a (k-2)-digit number.
Therefore x(k) = x(k-1) + x(k-2) and you have the fibonacci sequence.
Solve for n: 8+2n=2^n
8+2n=2^(n)
We divide both sides by 2
4+n=2^(n-1)
Now we want to get the solution of the equation for natural numbers
Let n-1=N+1
4+(N+2)=2^(N+1)
(N+2) Move to the right
4=2^(N+1)-(N+2)
The right side is equal to the sum of combinations from zero to N
4=nCr(1,0)+nCr(2,0)+nCr(2,1)+....nCr(N,0)
We calculate the values of each of these combinations
nCr(1,0)=1!/(0!1!)=1
nCr(2,0)=2!/(0!2!)=1
nCr(2,1)=2!/(1!1!)=2
Their sum is equal to 4
As result
4=nCr(1,0)+nCr(2,0)+nCr(2,1)=4
N=2. So n=N+2=4
dear @blackpenredpen do you know the IYMC or not ? if you know it please tell me your opinion about it
I shit my pants when the Fibonacci sequence popped up
Trying to solve it in base 2: 🦋
Trying to solve it in base 10: 💀
Can you solve this one?
You have integral from 0 to infinity of f(x) (x-b) dx =0 and have to find f(x)
There is a gazillion such functions and there is no simpler way to describe them than via this equation.
when I saw this problem binary numbers came to my mind for some reason, despite the fact that I had no clear idea how to solve the problem
That was awesome!
I tried using a probablity tree diagram and then sumed the terms of the geometric sequence of ratio 2. Found that 129 is the answer.( 2^7+1). Can anyone tell me why am I wrong?
Can you do a video where you calculate pi^pi^pi^pi^....
that diverges, no?
@@lumina_ yeah probably
Wouldnt base 4 be better?
Does any one knows what’s the answer :
Lim x^x - (sinx)^x
--------
X->0 x^3
Maths is so beautiful when the smart people are doing it
Woohoo! Paused the video & got the answer 144 in under 5 mins.
It reminds me of P-adic numbers
can you make a video on probablity
i graduated from high school and i am from morroco and i think i should improve my math level can someone please give me some advices, maybe ressources that i could use. Sorry if there any spelling mistake not very familiar with the language
Golden ratio everywhere.
I knew that there's a reason for the 1024 bcs I instinctively convert it to 2^10 lol
me too lol, thats the reason 1gb is 1024mb's
[WARNING: THIS COMMENT WAS WRITTEN BEFORE I WATCHED THE VIDEO, I HAVE NO IDEA IF IT IS CORRECT]
My solution:
In binary, f(x) looks like appending 1, and g(x) looks like appending 00.
Then count.
0 digits: 0 (0) //you'll see why I do this later
1 digit: 1 (1)
2 digits: 1 (11)
3 digits: 2 (111, 100)
4 digits: 3 (1111, 1001, 1100)
5 digits: 5 (11111, 10011, 11001, 11100, 10000)
Notice, that if D(N) is the number of numbers with exactly N digits in binary that can be reached with f(n) and g(n), then D(N) = D(N-1) + D(N-2).
Why?
Because D(N-1) means adding the 1, and D(N-2) means adding the 00. And they have to be distinct and disjoint because they have different lengths and end in different digits.
So given that D(1) = 1 and D(2) = 1, the rest follows nicely as the fibonacci series!
Now we just need to figure out D(1) + ... + D(10) + 1 (for the number 1024 itself which can be reached by g(g(g(g(g(f(0)))))))
I won't prove it here but there's a result that the sum of the first N fibonacci numbers is F_(N+2) - 1.
So that's 1 + 1 + 2 + ... + 55 + 1 = (144 - 1) + 1 = 144.
Done!
EDIT: i miscounted and only went up to 9 digits and not 10... oops
Mine answer was 75
hey one question. what’s the cubed root of -1?
It's -1... why don't you just use a calculator
Why do you keep changing the thumbnail and title @blackpenredpen ?
How many primes are in S?
Is the fact that 144 a perfect square a coincidence?
Yes. Michael Penn did the proof a few days ago that there are only a couple squares in the Fibonacci sequence.
@@stephenbeck7222 But this is not a Fibonacci number. This is the summ of first 10 Fibonacci number plus one. How is it related to Michael Penn's proof?
It's half a coincidence.
The sum of the first n fibonacci numbers is another fibonacci number (minus one).
The coincidence is that 144 is a fibonacci number and a square.
Recursion
Bro can we do a 100 differential equations in one take?
Would base 4 suit just as well?
Applying g(n)=4n in base 4 is just adding a zero, but what about f(n)=2n+1 ?
For example 27 in base 4 is 123.
f(27) = 55, which in base 4 is 313.
f(f(27)) = f(55) = 111, in base 4 is 1233. This is because 2(2n+1)+1 = 4n+3.
Applying f two times in a row means attaching a 3 at the end in base 4, but that's not really helpful enough.
Compared to base 2, there isn't a nice pattern here that makes it easy to see what's going on.
@@Deeds_of_Love last digit odd - simple!
Sir, is it possible to have x^(1) = 2, if x ≠ 2.
I might be silly to ask but can't help to get answer from you.😁😁
1.11 million subs (plz tell us when you hit 1,111,111 subs)
This was beautiful🥹
ok now prove it’s fibonacci
s'' il vous plait je veux la sol a-by^2=dy/dx
{(y(0)=0@(dy/dx)(∞)=0)
Functions 😟
Please use wireless microphone like rode microphone. We can't see your pain holding the mic for a long time
IQ 180+ problem.
?