To prove that we can always pick a line that intersects all previous lines and does not cross any existing intersection we can do the following. First we pick any line with slope not parallel to the previous lines and notice that it will intersect the previous lines (possibly the intersections fall outside the circle, but since the number or regions can only increase we can always work in a new big enough circle - and then scale everything back). Now since there are infinitely many such slopes and only finitely many previous intersections, we can pick a line that doesn't cross any existing intersection. The same reasoning also shows that we can find a new plane intersecting all previous planes and not containing any existing intersection line (this is useful to show that S(k+1) is a maximum and not only an upper bound: with this choice of the new plane we end up in the setting of the circle with k different lines without common intersections, and hence we know from before that in this care the regions are exactly A(k), and we get S(k+1)=S(k)+A(k)).
Thank you! Actually, however, what I wrote only shows that we can pick a plane which has k distinct lines on it, but it is still to be proved that it's always possible to pick the plane in such a way that all the k lines on it intersect two by two (i.e. there are no three lines intersecting at a same point) is that a point at the intersection of three lines would correspond to a point at the intersection of three existing planes, but by induction we might suppose that three existing planes only intersect in singletons (i.e. points as opposed to lines) and hence once again we have only finitely many bad cases to avoid and infinitely many possible slopes.
Thank you for the brilliant video. I would like to ask why S(k+1) = S(k) + A(k) at 3:56? I understand the previous part of cutting a circle. Thank you!
Thank you! Regarding the recurrence, when we add the (k+1)th plane, this will intersect the sphere resulting in a circle(similar to 3:30). The intersection of the plane with the previous planes are lines that split this circle, in a maximum of A(k) parts (as we saw before, since we have k lines that cut the circle). All the resulting pieces of the circle will split in half A(k) of the previous chunks of the sphere so they add an additional A(k) pieces. In conclusion, when moving from k planes to k+1, we can add a maximum of A(k) chunks.
Hi Shubham, Thank you for your comment and for the recommendation. The most straightforward approach seems to be using a recursion. Considering you want one of 4 cards in a deck of n cards, you have E[4,n] = 1 + (1-4/n) E[4, n-1]; using E[4,4]=1, you find E[4,n]=(n+1)/5, thus our answer must be 10,6 . Expanding the initial expectation and computing the P(x=i) also seems like a feasible option. What did you go for?
@@atypicalquant Consider the deck as A a_1 B a_2 C a_3 D a_4 E. Where each a_i are the 4 aces and A,B,C,D,E are some number of cards that separate the aces. We want E(A). Since there are 48 cards left (after we fix the aces) and 5 spots for them to go in we have, on average that each A,B,C,D,E has 48/5 cards. 48/5 = 9.6 plus the 1 to get the ace so we get 9.6 + 1 = 10.6
@@atypicalquant also is there a quick way to get from E[4,n] = 1 + (1 - 4/n)E[4, n - 1] --> E[4,n] = (n+1)/5 or did you do it manually considering each case
@@shubhamp8053Really nice solution! After manually computing E[4,5]=1.2, E[4,6]=1.4, the general formula becomes obvious. A quick induction formally proves that indeed E[4,n] = (n+1)/5, for all n>=4. The increase in expectation by 0.2 as you're adding an extra non-ace card, is nicely in line with your argumentation above, as it increases E(A) by 1/5.
For the formula of A(n) = (n+...+2+1)+A(1) = n(n+1)/2+1, shouldn't it be A(0) instead of A(1), since A(0)=1. Also, same goes for the formula S(n)=sum(i*(i+1)/2+1)+S(1). I believe it should be S(0). Correct me if I'm wrong.
Hi! We arrived at the following recursive relation at 2:44, A(k+1) = A(k) + k+1 (*). For k=n-1, we get: A(n) = A(n-1) + (n-1)+1 = A(n-1) + n For k=n-2, we get: A(n-1) = A(n-2) + (n-2) + 1 = A(n-2) + n-1 ... For k=2, we get: A(3) = A(2) + 2 + 1 = A(2) + 3 For k=1, we get: A(2) = A(1) + 1 + 1 = A(1) + 2 ------------------------------------------------------------- (sum up and simplify) A(n) = n + n-1 + ... + 3 + 2 + A(1) Here, replacing A(1) with the 2 value from 1:25, you get that A(n) = n(n+1)/2+1. This was my approach. If I understand correctly, you propose that we also add this line For k=0, we get: A(1) = A(0) + 0 + 1 = A(0) + 1 And sum up and simplify after, leveraging A(0)=1. While I agree that this could be correct, it required some extra attention on defining A(0) as well as showing that (*) works for 0. I opted to avoid this :D
I am genuinely curious how you developed such mathematical intuition. Was it from solving brainteasers or did you study something similar professionally?
On developing a mathematical intuition, practice is the key. To get the most out of it, always try and solve the problems before reading a solution and aim to have structure in your approach as well as an overview of the techniques you can apply. Wrt the closed form solution for the S(k) sum, as replied above: We can first split our sum into 3 sums (all going from 1 to n-1): LHS1 = sum of i^2 / 2 LHS2 = sum of i/2 LHS3 = sum of 1 Using the formula for the "Sum of Squares of Natural Numbers", we get LHS1 = (2n^3 - 3n^2 + n) /12 . Using the formula for the sum of natural numbers (sometimes called Gauss Sum Formula), we get LHS2 = (n^2 -n)/4 = (3n^2 - 3n)/12 Finally, without any formulas, LHS3 = n-1 = (12n-12)/12 Adding them up, you get LHS = (2n^3 + 10n - 12)/12 = (n^3 + 5n)/12 - 1 Adding the S(1), which is equal to 2, you get the final RHS.
I don't think this answer is true? Are you claiming that if you have four planes that fulfill your conditions, then they will always divide up the sphere into 15 chunks? I think I have such a configuration, and it only makes 14 chunks (and I actually didn't succeed in making 15). Does anybody have an explicit example of four planes making 15 chunks?
Yes, choosing 4 planes according to the conditions will create 15 chunks. There is actually a very nice animation here: en.wikipedia.org/wiki/Cake_number
I don't understand the jump from the 2d instance to the 3d one. Could you explain why there is an additional S(k) pieces added for the kth recursion of A_k. I can't seem to visually understand it.
Amazing interview guide! Thank you!! I have a question about the last formula shown at 4:05min of the video. How did the summation part of the equation (LHS) work out to the part with n cube + 5n (RHS)?
Hey! Thank you. I wanted to send you a pic of the detailed calculations, but it doesn't seem like the comment section here allows for it (nor does it allow for latex). I'll do my best to explain it here, in writing: We can first split our sum into 3 sums (all going from 1 to n-1): LHS1 = sum of i^2 / 2 LHS2 = sum of i/2 LHS3 = sum of 1 Using the formula for the "Sum of Squares of Natural Numbers", we get LHS1 = (2n^3 - 3n^2 + n) /12 . Using the formula for the sum of natural numbers (sometimes called Gauss Sum Formula), we get LHS2 = (n^2 -n)/4 = (3n^2 - 3n)/12 Finally, without any formulas, LHS3 = n-1 = (12n-12)/12 Adding them up, you get LHS = (2n^3 + 10n - 12)/12 = (n^3 + 5n)/12 - 1 Adding the S(1), which is equal to 2, you get the final RHS.
I understand you might prefer this notation, but they are equivalent from a proof point of view. As for clarity, I prefer to name the starting case K, and go from there.
This channel really is a gold mine for great problems and explanations. Thanks!
To prove that we can always pick a line that intersects all previous lines and does not cross any existing intersection we can do the following. First we pick any line with slope not parallel to the previous lines and notice that it will intersect the previous lines (possibly the intersections fall outside the circle, but since the number or regions can only increase we can always work in a new big enough circle - and then scale everything back). Now since there are infinitely many such slopes and only finitely many previous intersections, we can pick a line that doesn't cross any existing intersection.
The same reasoning also shows that we can find a new plane intersecting all previous planes and not containing any existing intersection line (this is useful to show that S(k+1) is a maximum and not only an upper bound: with this choice of the new plane we end up in the setting of the circle with k different lines without common intersections, and hence we know from before that in this care the regions are exactly A(k), and we get S(k+1)=S(k)+A(k)).
You are right, this is exactly the explanation on why we are always able to find a new hyperplane to intersect all the others in new points!
Thank you! Actually, however, what I wrote only shows that we can pick a plane which has k distinct lines on it, but it is still to be proved that it's always possible to pick the plane in such a way that all the k lines on it intersect two by two (i.e. there are no three lines intersecting at a same point) is that a point at the intersection of three lines would correspond to a point at the intersection of three existing planes, but by induction we might suppose that three existing planes only intersect in singletons (i.e. points as opposed to lines) and hence once again we have only finitely many bad cases to avoid and infinitely many possible slopes.
great explanation! simple, precise and exact!
Glad it was helpful! :D
Thank you for the brilliant video. I would like to ask why S(k+1) = S(k) + A(k) at 3:56? I understand the previous part of cutting a circle. Thank you!
Thank you!
Regarding the recurrence, when we add the (k+1)th plane, this will intersect the sphere resulting in a circle(similar to 3:30). The intersection of the plane with the previous planes are lines that split this circle, in a maximum of A(k) parts (as we saw before, since we have k lines that cut the circle). All the resulting pieces of the circle will split in half A(k) of the previous chunks of the sphere so they add an additional A(k) pieces. In conclusion, when moving from k planes to k+1, we can add a maximum of A(k) chunks.
@@atypicalquant Thank you very much for the reply!
great video! Here is a question i got in an interview you might want to try: Expected draws until an ace from a shuffled deck of 52 cards?
Hi Shubham,
Thank you for your comment and for the recommendation.
The most straightforward approach seems to be using a recursion. Considering you want one of 4 cards in a deck of n cards, you have E[4,n] = 1 + (1-4/n) E[4, n-1]; using E[4,4]=1, you find E[4,n]=(n+1)/5, thus our answer must be 10,6 .
Expanding the initial expectation and computing the P(x=i) also seems like a feasible option.
What did you go for?
@@atypicalquant Consider the deck as A a_1 B a_2 C a_3 D a_4 E. Where each a_i are the 4 aces and A,B,C,D,E are some number of cards that separate the aces. We want E(A). Since there are 48 cards left (after we fix the aces) and 5 spots for them to go in we have, on average that each A,B,C,D,E has 48/5 cards. 48/5 = 9.6 plus the 1 to get the ace so we get 9.6 + 1 = 10.6
@@atypicalquant also is there a quick way to get from E[4,n] = 1 + (1 - 4/n)E[4, n - 1] --> E[4,n] = (n+1)/5 or did you do it manually considering each case
@@shubhamp8053Really nice solution!
After manually computing E[4,5]=1.2, E[4,6]=1.4, the general formula becomes obvious. A quick induction formally proves that indeed E[4,n] = (n+1)/5, for all n>=4. The increase in expectation by 0.2 as you're adding an extra non-ace card, is nicely in line with your argumentation above, as it increases E(A) by 1/5.
For the formula of A(n) = (n+...+2+1)+A(1) = n(n+1)/2+1, shouldn't it be A(0) instead of A(1), since A(0)=1. Also, same goes for the formula S(n)=sum(i*(i+1)/2+1)+S(1). I believe it should be S(0). Correct me if I'm wrong.
Hi!
We arrived at the following recursive relation at 2:44, A(k+1) = A(k) + k+1 (*).
For k=n-1, we get: A(n) = A(n-1) + (n-1)+1 = A(n-1) + n
For k=n-2, we get: A(n-1) = A(n-2) + (n-2) + 1 = A(n-2) + n-1
...
For k=2, we get: A(3) = A(2) + 2 + 1 = A(2) + 3
For k=1, we get: A(2) = A(1) + 1 + 1 = A(1) + 2
------------------------------------------------------------- (sum up and simplify)
A(n) = n + n-1 + ... + 3 + 2 + A(1)
Here, replacing A(1) with the 2 value from 1:25, you get that A(n) = n(n+1)/2+1. This was my approach.
If I understand correctly, you propose that we also add this line
For k=0, we get: A(1) = A(0) + 0 + 1 = A(0) + 1
And sum up and simplify after, leveraging A(0)=1.
While I agree that this could be correct, it required some extra attention on defining A(0) as well as showing that (*) works for 0. I opted to avoid this :D
I am genuinely curious how you developed such mathematical intuition. Was it from solving brainteasers or did you study something similar professionally?
Also, how did you derive the closed form solution to the S(k) sum? It's not entirely clear how you got n^3. Excellent video as always.
On developing a mathematical intuition, practice is the key. To get the most out of it, always try and solve the problems before reading a solution and aim to have structure in your approach as well as an overview of the techniques you can apply.
Wrt the closed form solution for the S(k) sum, as replied above:
We can first split our sum into 3 sums (all going from 1 to n-1):
LHS1 = sum of i^2 / 2
LHS2 = sum of i/2
LHS3 = sum of 1
Using the formula for the "Sum of Squares of Natural Numbers", we get LHS1 = (2n^3 - 3n^2 + n) /12 .
Using the formula for the sum of natural numbers (sometimes called Gauss Sum Formula), we get LHS2 = (n^2 -n)/4 = (3n^2 - 3n)/12
Finally, without any formulas, LHS3 = n-1 = (12n-12)/12
Adding them up, you get LHS = (2n^3 + 10n - 12)/12 = (n^3 + 5n)/12 - 1
Adding the S(1), which is equal to 2, you get the final RHS.
Fascinating! 👏👏👏
I don't think this answer is true? Are you claiming that if you have four planes that fulfill your conditions, then they will always divide up the sphere into 15 chunks? I think I have such a configuration, and it only makes 14 chunks (and I actually didn't succeed in making 15). Does anybody have an explicit example of four planes making 15 chunks?
Yes, choosing 4 planes according to the conditions will create 15 chunks. There is actually a very nice animation here: en.wikipedia.org/wiki/Cake_number
I don't understand the jump from the 2d instance to the 3d one. Could you explain why there is an additional S(k) pieces added for the kth recursion of A_k. I can't seem to visually understand it.
I see ur reply to lily thanks!
Glad to see you found the answer!
Amazing video!!
Thank you!
Amazing interview guide! Thank you!!
I have a question about the last formula shown at 4:05min of the video.
How did the summation part of the equation (LHS) work out to the part with n cube + 5n (RHS)?
Hey! Thank you.
I wanted to send you a pic of the detailed calculations, but it doesn't seem like the comment section here allows for it (nor does it allow for latex). I'll do my best to explain it here, in writing:
We can first split our sum into 3 sums (all going from 1 to n-1):
LHS1 = sum of i^2 / 2
LHS2 = sum of i/2
LHS3 = sum of 1
Using the formula for the "Sum of Squares of Natural Numbers", we get LHS1 = (2n^3 - 3n^2 + n) /12 .
Using the formula for the sum of natural numbers (sometimes called Gauss Sum Formula), we get LHS2 = (n^2 -n)/4 = (3n^2 - 3n)/12
Finally, without any formulas, LHS3 = n-1 = (12n-12)/12
Adding them up, you get LHS = (2n^3 + 10n - 12)/12 = (n^3 + 5n)/12 - 1
Adding the S(1), which is equal to 2, you get the final RHS.
Better to use K and K-1 in place of K+1 and K respectively
I understand you might prefer this notation, but they are equivalent from a proof point of view. As for clarity, I prefer to name the starting case K, and go from there.
3 views 3 likes, excellent