Correction Corner! In the list of problems at the end, it should read 2^(n-1) time (n+1 choose 2) [not (n+1 choose k)]. Also, there are other ways of structuring the injection to show the sequence is increasing that don't even require a "palette". See if you can find a simpler argument than the one presented here!
Ah, I believe I found a simpler solution without a palette, in a comment I just left. Adult throws at one rascal who throws at the next until run out of balloons, but each rascal has been identified in a chain. Reverse: Follow chain to identify all rascals, then retarget them to the adult.
$\left(1 + \frac 1n ight)^n$ makes the brackets automatically resize to fit whatever is inside. That way you won't have those puny parentheses trying to encase that tall, majestic fraction, but instead get royally large parentheses that better suit such an expression.
This honestly felt like it would be from a channel with atleast tens of thousands of subscribers, I was surpirsed to see you had less than a thousand! This was such a great explanation.
These graphical explanations make all the difference, and allows a persone to actually understands the solution. All the best to your channel, cant wait for future videos :)
This is awesome! I'm a big fan of combinatorial proofs, especially when dressed up in fun scenarios like paint balloon fights :D The case where there's exactly 1 rascal is actually a bijection, so the entire excess is in the multiple rascals case. We want to find out what kinds of fights in the n^n set aren't hit by the injection. Two obvious cases are Alice hits herself and Alice hits someone who hits themselves. This would give (1 + 1/n)^n
Thanks for the encouragement, John! You'll need to quantify something more substantial than 2/n-1/n^2 if your goal is to get the limit strictly less than 3. 😁
I believe I have a (conceptually) simpler solution for the problem at 13:11. Since each of the r rascals no longer has a target, that means there are r balloons unused. Give one of those balloons to the adult. Have the adult throw at the first rascal (actually, can be arbitrary which rascal is chosen). Then have that rascal throw at the next (arbitrary) rascal, and so on, until you run out of balloons, and the last remaining rascal, who is left without a target -- which is fine. So now you have a simple chain to identify all the rascals: Just start at the adult and follow the chain to find each rascal. To reverse the snowball fight, just identify all the rascals in the chain starting at the adult and retarget them to throw at the adult, who no longer gets a balloon.
Also, there's a solution to the one-rascal problem that only requires changing who the rascal throws at (and not Alice nor any other child). [This solution also is similar to how simple error-detection / error-correction schemes are often designed in computer science, using the idea of 'parity checking'.] First, give numerical ids to the n children from 0 to n-1. For each child i, T(i) = 'the id of child targeted by child i'. For the moment, if the rascal is child r, then temporarily assign T(r) = A, for Adult. For example, at 6:45, the rascal is r = 2, and the assignment of T(i) would be as follows: 012345 15A042 Now compute the sum, S1 (for 'first sum'), of the non-rascal targets and take the 'parity', P1 = S1 mod n. In this case n=6, and the sum is: S1 = (1 + 5 + 0 + 4 + 2) = 12, and P1 = S1 mod n = 12 mod 6 = 0 Next, assign the rascal's target, T(r), to be equal to the id of the rascal, r, minus the parity, again mod n: T(r) = (r - P1) mod n , so T(2) = (2 - 0) mod 6 = 2 Thus, in this case, retarget the rascal to target child 2, which in this case happens to be the rascal itself. So in this case, the new targets are: 012345 152042 To reverse, simply take the entire sum of all the targets, S2 (for 'second sum'), and again take the parity by modding by n. S2 = (1 + 5 + 2 + 0 + 4 + 2) = 14 P2 = S2 mod n = 14 mod 6 = 2 This parity P2 exactly identifies who the rascal is! That is, r = P2. In this case, r = P2 = 2. Therefore, we can reconstruct the original snowball fight by re-targeting the freshly-identified rascal back to the adult: 012345 15A042 We can prove this is always possible because out of all possible sums of targets of n children targeting withing themselves, there are always exactly 1/n of all such sums which have parity equal to 0, again 1/n of all sums with parity 1, 1/n of sums with parity 2, and so on up to 1/n of sums with parity (n-1). [For clarity: 1/n of all possible sums is 1/n * n^n = n^(n-1). This is the same as the number of snowball fights of the other n-1 children throwing at 'themselves including the rascal' which is n.] So we can always assign a new target for the rascal such that the final parity of the sum will be equal to the identity of the rascal. Mapping back just requires identifying the rascal (by finding the parity) and re-targeting the rascal to the adult.
while this is a cool concept, I think for many people, the first exposure to most of the techniques you use come after they have been doing calculus, and it feels like if you are promising a proof without calculus, people will assume that you mean using the stuff you learn in school before you get to calculus. (at least at the college where I work as a tutor, students don't generally learn about sigma notation until calc 2, and don't generally encounter sequences and series until calc 3. binomial theorem is introduced as an interesting form for things to take while learning about taylor and mclauren series, also in calc 3.) still an incredibly clever and elegant proof that e is less than 3 (although surely there is a way of defining e that doesn't involve limits, as defining e in terms of limits presents a small problem for giving a proof without calculus: firstly, limits are generally introduced in calculus, and indeed are probably what sets calculus apart from the rest of math.)
I almost immediately just went to calculus in my head, but this is without calculus... you might have broken me already, and I’m only just starting the video
13:25 I thought we'd just have the adult aim at the first rascal, the first to the second, and so on, while the last rascal gets no balloon. In fact we could imagine taking a balloon from the last rascal and giving it to the adult, so the number of the balloons stays the same. In case there are no rascals at all, the adult gets no balloon and the mapping actually stays the same. This is clearly reversible, we've essentially reinvented the single-linked list. More importantly, it's even simpler than any other method in the video, while using the exact same basic idea. That's why I'm wondering - did I make a mistake? Why use such a complicated method instead?
Awesome video. I was wondering what a formal expression of one of these injective transformations would look like. Having that, we could verify that it in fact is a valid injection by proving that it's inversible (or maybe there's some other way?)
Could we also just have Alice aim at the leader, then have the leader aim at the first crew member, first aim at the second, etc. And have the last crew member aim back to the leader? Not sure if this would work as well but I can't see why it wouldn't, and to me it seems simpler than specifying the leader and having their setup be different. Great video by the way - so well made! Edit: I've answered my own question. If we do what I said we can't deduce who Alice's original target was :)
It was a really fun and relaxing video, thanks ! Also I thought of an other injection for the case when exactly 1 kid aims the adult. You make the rascal aims himself and every otber kids aiming at themselves throw their ballons at the rascal. I think it works, but I'm not sure. Thanks !
I'm a bit confused at the start, how do we know each term of our sequence is rational. When we have( (n+1)/n)^n if n was an irrational number this would be irrational, right?
When you're referring to a *sequence*, the index is an integer. And we usually remind ourselves of this difference by using variables traditionally associated with integers, such as i, k, n, etc. When we want to denote a continuous variable, we tend to use a different set of variables, like x, y, z. Certainly there are exceptions to variable notation, but in general (and especially combinatorics--this channel's focus!) n will stand for an integer. Keep asking questions!
@@enumerable345 Thanks so much for replying. I'm still a bit confused though. If our definition of e is lim-> infinity of (1+1/n)^n, how can we use the the facts that the sequence of (1+1/n)^n is monotonically increasing and each term of the sequence is less than equal to 3 to show e converges to some value less than three? I'm confused on how we can go from a limit over all real numbers to integers so easily?
What if a raskal is hit by two snowballs of other children ? This makes the process of finding the person at the end of the path not unique. Is this creating a problem ?
Not a problem, but you have found a way to make the inequality strict! We get to choose the method of finding the palette, so in the video we just chose the leftmost one, but any would do. Following the throws *forward* has to be unique, which it is since everyone only gets one balloon.
Hey, is the channel this video ruclips.net/video/myKkhVy74V4/видео.html was posted by yours? The videos appear to be exactly the same, and I couldn’t find any mention of this channel in the video.
Yeah, we had a little miscommunication about publishing the video, and posted it both here (where I hope to have more content in the future) and on Liam's channel (he does fantastic visualizations). We decided to leave both up, but thanks for your concern! I did add a mention to this in the description of this video.
Pi is a very geometry-inspired number, so it's pretty easy to see geometrically. Imagine a unit circle circumscribing a regular hexagon. The circumference (2 pi) is larger than the perimeter of the hexagon (which is 6). This does require that a "straight line" is the minimum length curve between two points--which is a bit nontrivial. But just because it's geometric doesn't mean there's no combinatorial angle--I'll think about it!
Correction Corner!
In the list of problems at the end, it should read 2^(n-1) time (n+1 choose 2) [not (n+1 choose k)].
Also, there are other ways of structuring the injection to show the sequence is increasing that don't even require a "palette". See if you can find a simpler argument than the one presented here!
ruclips.net/video/myKkhVy74V4/видео.html？
Ah, I believe I found a simpler solution without a palette, in a comment I just left. Adult throws at one rascal who throws at the next until run out of balloons, but each rascal has been identified in a chain. Reverse: Follow chain to identify all rascals, then retarget them to the adult.
$\left(1 + \frac 1n
ight)^n$ makes the brackets automatically resize to fit whatever is inside. That way you won't have those puny parentheses trying to encase that tall, majestic fraction, but instead get royally large parentheses that better suit such an expression.
Outstanding video!
This honestly felt like it would be from a channel with atleast tens of thousands of subscribers, I was surpirsed to see you had less than a thousand! This was such a great explanation.
These graphical explanations make all the difference, and allows a persone to actually understands the solution. All the best to your channel, cant wait for future videos :)
Glad it helps. Hopefully more forthcoming!
This is awesome! I'm a big fan of combinatorial proofs, especially when dressed up in fun scenarios like paint balloon fights :D
The case where there's exactly 1 rascal is actually a bijection, so the entire excess is in the multiple rascals case. We want to find out what kinds of fights in the n^n set aren't hit by the injection. Two obvious cases are Alice hits herself and Alice hits someone who hits themselves. This would give (1 + 1/n)^n
Thanks for the encouragement, John! You'll need to quantify something more substantial than 2/n-1/n^2 if your goal is to get the limit strictly less than 3. 😁
I believe I have a (conceptually) simpler solution for the problem at 13:11.
Since each of the r rascals no longer has a target, that means there are r balloons unused. Give one of those balloons to the adult. Have the adult throw at the first rascal (actually, can be arbitrary which rascal is chosen). Then have that rascal throw at the next (arbitrary) rascal, and so on, until you run out of balloons, and the last remaining rascal, who is left without a target -- which is fine.
So now you have a simple chain to identify all the rascals: Just start at the adult and follow the chain to find each rascal. To reverse the snowball fight, just identify all the rascals in the chain starting at the adult and retarget them to throw at the adult, who no longer gets a balloon.
Yep, that does seem to work and is simpler. Thanks Rob! 👍
This is the one I found too :)
My interest in this video is 1) unbounded, and 2) exponentially increasing! #math
I liked the idea of presenting the "rigorous" part of proof in a more digestible way
great video, keep it up!
Also, there's a solution to the one-rascal problem that only requires changing who the rascal throws at (and not Alice nor any other child). [This solution also is similar to how simple error-detection / error-correction schemes are often designed in computer science, using the idea of 'parity checking'.]
First, give numerical ids to the n children from 0 to n-1. For each child i, T(i) = 'the id of child targeted by child i'. For the moment, if the rascal is child r, then temporarily assign T(r) = A, for Adult. For example, at 6:45, the rascal is r = 2, and the assignment of T(i) would be as follows:
012345
15A042
Now compute the sum, S1 (for 'first sum'), of the non-rascal targets and take the 'parity', P1 = S1 mod n. In this case n=6, and the sum is:
S1 = (1 + 5 + 0 + 4 + 2) = 12, and
P1 = S1 mod n = 12 mod 6 = 0
Next, assign the rascal's target, T(r), to be equal to the id of the rascal, r, minus the parity, again mod n:
T(r) = (r - P1) mod n , so
T(2) = (2 - 0) mod 6 = 2
Thus, in this case, retarget the rascal to target child 2, which in this case happens to be the rascal itself. So in this case, the new targets are:
012345
152042
To reverse, simply take the entire sum of all the targets, S2 (for 'second sum'), and again take the parity by modding by n.
S2 = (1 + 5 + 2 + 0 + 4 + 2) = 14
P2 = S2 mod n = 14 mod 6 = 2
This parity P2 exactly identifies who the rascal is! That is, r = P2. In this case, r = P2 = 2. Therefore, we can reconstruct the original snowball fight by re-targeting the freshly-identified rascal back to the adult:
012345
15A042
We can prove this is always possible because out of all possible sums of targets of n children targeting withing themselves, there are always exactly 1/n of all such sums which have parity equal to 0, again 1/n of all sums with parity 1, 1/n of sums with parity 2, and so on up to 1/n of sums with parity (n-1). [For clarity: 1/n of all possible sums is 1/n * n^n = n^(n-1). This is the same as the number of snowball fights of the other n-1 children throwing at 'themselves including the rascal' which is n.]
So we can always assign a new target for the rascal such that the final parity of the sum will be equal to the identity of the rascal. Mapping back just requires identifying the rascal (by finding the parity) and re-targeting the rascal to the adult.
Colorful!
while this is a cool concept, I think for many people, the first exposure to most of the techniques you use come after they have been doing calculus, and it feels like if you are promising a proof without calculus, people will assume that you mean using the stuff you learn in school before you get to calculus. (at least at the college where I work as a tutor, students don't generally learn about sigma notation until calc 2, and don't generally encounter sequences and series until calc 3. binomial theorem is introduced as an interesting form for things to take while learning about taylor and mclauren series, also in calc 3.) still an incredibly clever and elegant proof that e is less than 3 (although surely there is a way of defining e that doesn't involve limits, as defining e in terms of limits presents a small problem for giving a proof without calculus: firstly, limits are generally introduced in calculus, and indeed are probably what sets calculus apart from the rest of math.)
Love the original technique!
I almost immediately just went to calculus in my head, but this is without calculus... you might have broken me already, and I’m only just starting the video
This is so good
13:25 I thought we'd just have the adult aim at the first rascal, the first to the second, and so on, while the last rascal gets no balloon. In fact we could imagine taking a balloon from the last rascal and giving it to the adult, so the number of the balloons stays the same. In case there are no rascals at all, the adult gets no balloon and the mapping actually stays the same. This is clearly reversible, we've essentially reinvented the single-linked list. More importantly, it's even simpler than any other method in the video, while using the exact same basic idea. That's why I'm wondering - did I make a mistake? Why use such a complicated method instead?
I feel so sorry for the Palette. All for science. His mum's going to have a lot of washing
Awesome video. I was wondering what a formal expression of one of these injective transformations would look like. Having that, we could verify that it in fact is a valid injection by proving that it's inversible (or maybe there's some other way?)
Very Interring technique ❤
Could we also just have Alice aim at the leader, then have the leader aim at the first crew member, first aim at the second, etc. And have the last crew member aim back to the leader? Not sure if this would work as well but I can't see why it wouldn't, and to me it seems simpler than specifying the leader and having their setup be different.
Great video by the way - so well made!
Edit: I've answered my own question. If we do what I said we can't deduce who Alice's original target was :)
Just a tip, if you want the less than or equal sign with one bar underneath and not two, you type /le rather than /leq ;)
Fixed the title!
I didn't understand any of this, video was so good i watched it all anyway
It was a really fun and relaxing video, thanks !
Also I thought of an other injection for the case when exactly 1 kid aims the adult. You make the rascal aims himself and every otber kids aiming at themselves throw their ballons at the rascal.
I think it works, but I'm not sure. Thanks !
That isn't reversible; you can't tell the difference between someone who originally aimed at themselves and someone who originally aimed at the rascal
I'm a bit confused at the start, how do we know each term of our sequence is rational. When we have( (n+1)/n)^n if n was an irrational number this would be irrational, right?
When you're referring to a *sequence*, the index is an integer. And we usually remind ourselves of this difference by using variables traditionally associated with integers, such as i, k, n, etc. When we want to denote a continuous variable, we tend to use a different set of variables, like x, y, z. Certainly there are exceptions to variable notation, but in general (and especially combinatorics--this channel's focus!) n will stand for an integer. Keep asking questions!
@@enumerable345 Thanks so much for replying. I'm still a bit confused though. If our definition of e is lim-> infinity of (1+1/n)^n, how can we use the the facts that the sequence of (1+1/n)^n is monotonically increasing and each term of the sequence is less than equal to 3 to show e converges to some value less than three? I'm confused on how we can go from a limit over all real numbers to integers so easily?
What if a raskal is hit by two snowballs of other children ? This makes the process of finding the person at the end of the path not unique. Is this creating a problem ?
Not a problem, but you have found a way to make the inequality strict! We get to choose the method of finding the palette, so in the video we just chose the leftmost one, but any would do. Following the throws *forward* has to be unique, which it is since everyone only gets one balloon.
Hey, is the channel this video ruclips.net/video/myKkhVy74V4/видео.html was posted by yours? The videos appear to be exactly the same, and I couldn’t find any mention of this channel in the video.
Yeah, we had a little miscommunication about publishing the video, and posted it both here (where I hope to have more content in the future) and on Liam's channel (he does fantastic visualizations). We decided to leave both up, but thanks for your concern! I did add a mention to this in the description of this video.
@@enumerable345 k
I also saw this video done by Ian Appelbe. Does that happen to be an alternative account of yours?
My collaborator on this. Miscommunication led to double posting. I put a note about it in the description!
Can you do pi being at least 3?
Pi is a very geometry-inspired number, so it's pretty easy to see geometrically. Imagine a unit circle circumscribing a regular hexagon. The circumference (2 pi) is larger than the perimeter of the hexagon (which is 6). This does require that a "straight line" is the minimum length curve between two points--which is a bit nontrivial. But just because it's geometric doesn't mean there's no combinatorial angle--I'll think about it!
n+1
Check your order of operations. The claim is that (n+1)^n < 3n^n, not (3n)^n. 😀
100th like!