Can you always cover 10 points with 10 equally sized (non-overlapping) coins?
Вставка
- Опубліковано 22 лис 2021
- Sign up with brilliant and get 20% off your annual subscription: brilliant.org/ZachStar/
STEMerch Store: stemerch.com/
Support the Channel: / zachstar
PayPal(one time donation): www.paypal.me/ZachStarYT
Paper seen in video: 2012.cccg.ca/papers/paper13.pdf
Another paper on this topic: arxiv.org/pdf/1101.3468v1.pdf
Join this channel to get access to perks:
/ @zachstar
►Follow me
Instagram: / zachstar
Twitter: / imzachstar
2D Graphing Software: www.desmos.com/calculator
Animations: Arkam Khan (For contact info go to www.arqum333.com/)
Check out my Spanish channel here: / zach star en español
►My Setup:
Space Pictures: amzn.to/2CC4Kqj
Magnetic Floating Globe: amzn.to/2VgPdn0
Camera: amzn.to/2RivYu5
Mic: amzn.to/35bKiri
Tripod: amzn.to/2RgMTNL
Equilibrium Tube: amzn.to/2SowDrh
►Check out my Amazon Store: www.amazon.com/shop/zachstar
Alright there's some confusion in the comments, so let me just say THIS is the real question I'm posing in the video. "Prove that for any arrangement of 10 points in a plane, you can always cover them with at most 10 non-overlapping unit circles."
I think my use of coins caused the confusion and I tried to emphasize this by saying the size of the coins is FIXED, you cannot just pick whichever size coins you want for some configuration, that would make this problem very boring and trivial. They are all the size of unit circles, they cannot be changed, and THEN we must show for any configuration of ten points you can do the covering. I don't think I was clear enough on that so my apologies. Rest of the video still stands though! I know it's a surprising proof but I thought it was a really beautiful one.
I think the issue here is subtle: the problem (in its actual intent) generalizes to coins of radius r, but when the problem is restated more generally, it introduces an importance of how the quantifiers are presented.
_"Can any configuration of n points be covered by n unit circles?"_ Is the original.
_"Can n circles of radius r cover any configuration of n points?"_ is a generalization of the statement that captures the intent.
But _"Can any configuration of n points be covered by n circles of radius r?"_ reads as though the constant r is local to one of the "any configurations" being considered. It's rather like if I asked: "can you always cover two natural numbers with two intervals of real numbers?" I'm not asking for two intervals of real numbers which on their own cover all of the natural numbers.
@Zach Star A simple example to show that the dice analogy is wrong. If the tosses of two dice are not independent you can make the expected value of the sum to be different from 7. We make the second roll dependent this way: say the second die rolls 6 for all values of the first dye roll. What's the expected average? 7 or maybe 9.5?
Now you might say that this second dependent roll no longer has its expected value of 3.5. But then what makes you think that in the video the chance of the second point being covered is not "dependent" on the result of the first point's "covered" status exactly like in this my counterexample?
I am trying to highlight a subtlety of the definition "dependent". It can be a correlation that does not change the expected value (but statistically speaking is still a dependence), or it can be a dependence that does change the expected value, and thus the proof in the video is incomplete. So, for a proper proof you need to show that if the first point is covered then for any other position of the second point the expected value of its "covered" status stays the same 0.907. And this is probably hard.
It almost felt too simple to be true.
@@ahr2g6 I think I broadly understand what you're getting at, but I'm not sure about your dice example. In what sense is the second dice roll "dependent" in your scenario? It seems to me that if the second dice rolls 6 for all values of the first roll, then this is an independent event, no?
It also seems like your concern about dependence is addressed in the section about linearity of expectation - I don't pretend to fully understand why this linearity holds, but it seems to mean that we can sum the expectations regardless of whether the events are correlated. (maybe my understanding is naive, I have never been good at statistics).
I came to understand it, Zach, so no worries from my corner. :)
I wonder if you would provide a link to the paper you showed? I wanted to look for it and read it.
Me 10 seconds ago: "BUT WHAT IF YOU PUT THEM SO CLOSE TOGETHER THAT YOU CAN'T PLACE THE COINS CLOSE ENOUGH TO COVER THEM"
Me 10 seconds later: "You'd just cover them all with one coin..."
haha block me i dont like you
@@Timmysthirdbirthday k
Yep
The 'at most' is what's lacking in the title.
Same
The linearity of expectation of _dependent_ variables is the heart of the proof and gets zero explanation in this video. (There is only a brief example of linearity of expectation of _independent_ variables.)
You have to rule out that there can exist a particularly evil configuration of points that "finds" the holes in the lattice more easily (even slightly more easily) than a random configuration. Linearity of expectation of dependent variables basically asserts, out of nowhere, that an evil configuration is impossible. Thus it's not obvious - i think half this video should have been about that.
I tried to construct examples where the linearity of expectation breaks - read my comments under Zach's post. They certainly look convincing, but not necessarily true. In statistics there are very subtle things one can miss. I agree with you that this point must be addressed thoroughly.
I have just written about this above so I will just copy-paste it here. You can also read the proof of the linearity in the video where it briefly shows on the Brilliant site if you understand the mathematical notation.
Copy-pasted text:
There is no missing point in the proof. It is all covered by the linearity of expectation proof of which you can see briefly on the Briliant page in the video.
If the position of two points is dependent (which in our set-up basically means that they are a fixed distance from each other) then if you position the circles randomly, there is about 0.907 probability that any point is covered. There is therefore 0.907 probability that point 1 is covered and a probability of 0.907 that point 2 is covered (you can just imagine we removed one of the points for a moment and you will see that it is the same case as if there only was one point).
Notice that this does not mean that these points are independent. In general, there are 4 possible situations:
1) both point 1 and point 2 are covered (let's assign probability P12 to this),
2) point 1 is covered but point 2 is not (probability P1),
3) point 2 is covered but point 1 is not (probability P2),
4) neither point is covered (probability P0).
We don't generally know all of these probabilities but what we know is that the probability that point 1 is covered is P12 + P1 = 0.907 and the probability that point 2 is covered is P12 + P2 = 0.907. Therefore P1 = P2 which is also apparent from the interchangeability of both points (there is no way to tell them apart).
Now let's calculate the expected value of covered points:
E[covered points] = sum for all possible cases (points covered in a given case)*(probability of the case)
E[covered points] = 2*P12 + 1*P1 * 1*P2 + 0*P0 = (P12+P1) + (P12+P2) + 0 = 2*0.907 = E[point 1 covered] + E[point 2 covered]
If we have three points:
E[point 1 covered] = P123 + P12 + P13 + P1
E[point 2 covered] = P123 + P12 + P23 + P2
E[point 3 covered] = P123 + P13 + P23 + P3
E[covered points] = 3*P123 + 2*P12 + 2*P13 + 2*P23 + 1*P1 + 1*P2 + 1*P3 + 0*P0 = E[point 1 covered] + E[point 2 covered] + E[point 3 covered]
and similarly for any number of points.
I hope this clarifies things a bit.
POSSIBLY SIMPLER, BETTER RESPONSE FROM BELOW:
Edit: Red Storm in the replies to this comment gave a really good proof, which I will repeat here for anyone else confused:
First, label each point 1-10. Now, if you imagine all of the possible coin tilings, 9.3% of them will miss point 1. Similarly, 9.3% will miss point 2, and so on. Now, even if none of the "miss" coin tilings overlapped with each other, a maximum of 93% of coin tilings will have been eliminated, since there are 10 coins. But that still leaves some tilings left over! Therefore, all point arrangements have a solution (actually, this also proves each one has an infinite number of solutions too!)
@@martinvitvavrik9417 Thanks. I didn't want to imply that the proof was wrong or merely that the video was incomplete, but that the video was incomplete right at the key moment where the surprise happens and (my) intuition is violated.
It's this part that lands home best with me: 3*P123 + 2*P12 + 2*P13 + 2*P23 + 1*P1 + 1*P2 + 1*P3 + 0*P0 = E[point 1 covered] + E[point 2 covered] + E[point 3 covered]
With that equation I can almost see the "evilness" melting away from a configuration of points, as inequities in the values are forcibly evenly distributed.
he literally says it works for dependent events at 6:09
@@tweekin7out And Martin Vít Vavřík took the time to _show_ it. Do you see how one is better than the other, especially at the crucial point in the argument?
Holy I've literally never thought about expected value like this before
Yeah there's similar problems to this with clever uses of linearity of expectation and
Greetings from Houston , Compliments of the season i know this information might not be for everyone , but beneficial to some , i will say start Eth mining / cryptomining . with this money you can earn $12k-$18k in a month depending on the signal strength .
i got into cryptomining few months back but i was not this profitable because i was doing it all with my knowledge
@@floydchusset3143 Who mentors you in the market?
@@sandrawilson1966 Helen Howard Pratea mentors me
I get that the argument in the video works _given_ that the expectation value of dependent variables is linear, but as someone who didn't know that before and has no intuition as to why that should be true, I've gotta say it still feels like the video's saying "Yes, it's possible, just trust me" rather than an actual proof since that's basically all that was said about such linearity.
The argument in the video also only works for someone who knows what the number 10 represent. If someone doesn't know what the number 10 represents and has no intuition about what counting even means, the video would be like telling him "Yes it's possible, just trust me".
Expectation has properties. Linearity of expectation isn't anything fancy or whatnot, it is most likely the first property of them anyone encounters when they get introduced to expectation.
While I understand that one may be unsatisfied by linearity of expectation has not been proven in the video, the author has to choose a level of basics to reintroduce, because knowledge is based on knowledge. Someone else could be unsatisfied that the author didn't explain what 10 is, or what is a number, and their unsatisfaction would be just as valid as yours. In the end, a choice was made. The author has to assume a prerequisite level of their audience when they write their video, and this choice cannot be anything else than arbitrary.
If you really want a proof about it, just get the definition of expectation of E[X+Y], then separate the Xs and Ys in the summation, and you get E[X] + E[Y]. It's like 3 lines of basic algebra.
@@ApiolJoe Of course the author has to assume a prerequisite level of their audience and it's unreasonable to explain everything. But the way the expectation value was presented in the video already set the level of basics at the point of 'going over what the expectation value is' at 5:37, albeit briefly - it's essentially assuming the audience either doesn't know what expectation value is or needs a refresher on what it is.
Given that, it seems silly to me to _also_ assume that the audience knows expectation value is linear, which (certainly for me at least in the case of dependent variables) feels nonintuitive to someone who's just learnt about it/been reminded of what it is for the first time in years. For those people, to whom this video clearly caters, it really is a case of 'just trust me'.
Now I've looked up the proof and understand it, the answer's more satisfying, but the fact that the proof is indeed only about 3 lines of basic algebra just makes it even sillier that he didn't include it in the video.
@@ApiolJoe in that case it's seperating the X's and Y's in the integral since it's continious. Still 3 lines of proof though.
Well yes, but actually no
Saw it on r/maths and that was the same proof iirc, can you explain why do you think it's wrong ?
I don't think it's wrong. The proof uses the fact that expectation is linear even if the variables are not independent. That is, E(X+Y) = E(X)+E(Y), even if X and Y are not independent.
Doesn’t it just prove that it is possible to cover them all for some configuration, but not for every placement?
It is not ALWAYS possible to cover them with a certain amount of points
We want some placement to cover them all
It sais that for any 10 points, it exist a toss of unit circles that cover them all.
He should have insisted more on the Arbitrary 10 given points at the beginning of the demo
He showed that with any configuration of 10 points, there is always a scenario where you can cover all 10 because the average covering was 9.07
it is placement of coin lattice that changes each attempts for any given configuration of points, hence it works for any configuration
Great video but I think it would have been a good idea to mention that this specific proof doesn't work for numbers higher than 10, since the expected number of points covered isn't > n-1 (thereby requiring some instances of n to pull the average up) for n>10. IMO it's not immediately obvious why this logic doesn't extend to the 45 coin example.
It differs from n>=11 onwards because the expected value drops below n-1. For example E(11)=9.9758... which means if you were throwing a lattice at random you no longer have the guarantee that you'll ever cover all 11 (because you can hit that average with a combination of 10s & lower than 10s *only*).
@@danielm.1441 That's what I said
@@xereeto I think I saw the old comment? Either way, yes.
@@xereeto but he said it better
@@NoNameAtAll2 this is true
There is one problem though: The tossing of that lattice may be random, but the points are not. I has to work for EVERY configuration of points and you would have to prove that there is no configuration that doesn't always leave one point in one of the gaps. The lattice has a regular pattern, so if you also place the points in a regular pattern, they are no longer independent and therefore there is not an easy way to find the expected value of the number of points covered by coins.
I don’t think this needed to be explained with randomness, it just helps to understand the expected values this proof relies on.
Say you want to disprove this proof by maliciously and intentionally placing points, one by one, so as to miss as many potential lattice positions as possible. There are an infinite number of coin lattice positions, all of which are as densely packed as possible (so they mostly vary on the exact x and y positioning of the lattice). So with your first point you’ve discounted *at most* 9.3% of possible lattice positions from including that point, which is 1-.907, or 1-the packing density, or the ratio of empty space between coins. This is because in 9.3% of lattice positions your point will be in the empty space. The second maliciously placed point can further decrease the possible lattice positions, looking solely at the lattices that contain the first point, but again it can only remove at most 9.3% of possible lattice positions. The proof lies in the fact that these events, here being the placement of each point, can be linearly combined so that after you’ve placed 10 points you’ve discounted, at most, 93% of all possible lattice positions as not containing your 10 points. That leaves 7%, or at least one lattice, which *do* contain your 10 points.
Also note that placing your second point outside the range of the densely packed lattices of coins containing your first point actually makes it easier to cover, then we can just take one of the coins and move it to cover that second point (you’ll just get 10 disjointed coins if you keep doing this, like the initial visual in the video). Better is to try to get the coins to overlap, and that’s why we focus solely on lattice coin structures. In a sense the lattice arrangement is a “worst case scenario”, as it represents an attempt to cover as much space as possible within its range while *baaarely* not overlapping.
This was the exact same issue I had with this proof. I thought "To show that this proof is true then wouldn't you have had to assume that the expected value was 9.07, which is only known true in the random case?"
@@samueltukua3061 no, it comes from the non random packing density (.907)
Just copy-pasting my response from above:
There is no missing point in the proof. It is all covered by the linearity of expectation proof of which you can see briefly on the Briliant page in the video.
If the position of two points is dependent (which in our set-up basically means that they are a fixed distance from each other) then if you position the circles randomly, there is about 0.907 probability that any point is covered. There is therefore 0.907 probability that point 1 is covered and a probability of 0.907 that point 2 is covered (you can just imagine we removed one of the points for a moment and you will see that it is the same case as if there only was one point).
Notice that this does not mean that these points are independent. In general, there are 4 possible situations:
1) both point 1 and point 2 are covered (let's assign probability P12 to this),
2) point 1 is covered but point 2 is not (probability P1),
3) point 2 is covered but point 1 is not (probability P2),
4) neither point is covered (probability P0).
We don't generally know all of these probabilities but what we know is that the probability that point 1 is covered is P12 + P1 = 0.907 and the probability that point 2 is covered is P12 + P2 = 0.907. Therefore P1 = P2 which is also apparent from the interchangeability of both points (there is no way to tell them apart).
Now let's calculate the expected value of covered points:
E[covered points] = sum for all possible cases (points covered in a given case)*(probability of the case)
E[covered points] = 2*P12 + 1*P1 * 1*P2 + 0*P0 = (P12+P1) + (P12+P2) + 0 = 2*0.907 = E[point 1 covered] + E[point 2 covered]
If we have three points:
E[point 1 covered] = P123 + P12 + P13 + P1
E[point 2 covered] = P123 + P12 + P23 + P2
E[point 3 covered] = P123 + P13 + P23 + P3
E[covered points] = 3*P123 + 2*P12 + 2*P13 + 2*P23 + 1*P1 + 1*P2 + 1*P3 + 0*P0 = E[point 1 covered] + E[point 2 covered] + E[point 3 covered]
and similarly for any number of points.
I hope this clarifies things a bit.
POSSIBLY SIMPLER, BETTER RESPONSE FROM BELOW:
Edit: Red Storm in the replies to this comment gave a really good proof, which I will repeat here for anyone else confused:
First, label each point 1-10. Now, if you imagine all of the possible coin tilings, 9.3% of them will miss point 1. Similarly, 9.3% will miss point 2, and so on. Now, even if none of the "miss" coin tilings overlapped with each other, a maximum of 93% of coin tilings will have been eliminated, since there are 10 coins. But that still leaves some tilings left over! Therefore, all point arrangements have a solution (actually, this also proves each one has an infinite number of solutions too!)
Yeah, I agree. If you're throwing the points randomly, then there's an independent 90.7% chance each point is covered. But if you fix the points and then throw the lattice... This proof is incomplete.
Edit: even if X and Y are not independent events, E(X+Y)=E(X)+E(Y), so I suppose that completes the proof... I'll need some time to accept it though lol.
Did anyone else come from his second channel expecting more sketches and was completely thrown off by him being actually kind of a mathematical genius
definetly
No
I went the other way around.
Hold on... This "proof" assumes that which it is attempting to prove.
Things are fine up until 4:05 -- up until then the probability analysis for randomly placing the packed-circle grid onto one point is perfectly valid. HOWEVER, the following statement is, "Now with ten points, we just multiply this by ten -- each point has a 90.7% chance of being covered, so the expected number of points covered by our lattice is 9.07."
No, not necessarily. The condition of "with ten points" is ambiguous, and implicitly smuggles in the desired endpoint of the proof.
"With ten points" in this experiment can mean one of two very different things:
A) What's the expected number of points covered by the packed-circle grid when it's randomly placed upon all possible (or at least a vast number of) permutations of ten points randomly positioned? In this case, yes, the correct answer is ~9.07, because randomizing the ten points every trial makes the individual point positions independent trials, you're just "batching" your single-point "hit" counts (and the single-point hit probability of 0.907).
B) When randomly throwing packed-circle grids over and over again, can at least one carefully chosen arrangement of ten points violate the re-scattering point trials' ~9.07 expectation because (at least) one of the points in your fixed (and importantly, non-independent) arrangement is always guaranteed to "dodge" part of the circle grid (like the 45-point construct does)? Well that's what you're trying to determine, isn't it? If such a point arrangement does exist, ITS expected random-grid coverage is NOT 9.07, it's some number 9.0 or below and the video "proof" falls apart. (There could also be point arrangements that cluster in a way that's *more* likely to score hits in the circles.) Put another way, do we know that each and every possible 10-point configuration itself strictly adheres to the same 9.07 expected value? That critically depends upon exactly the question we're attempting to resolve.
[Edited to delete a simplified example that was too simplified to be analogous]
I went and looked at Naoki Inaba's original proof, thinking I must have missed something or that it included a step you had not clarified, but no, it's even less rigorous than yours, it leaves many more steps unstated.
In this comment I want to show why I think that the proof in the video is correct, and it relies on one key fact from probability theory.
The proof with the probability theory behind it: First we fix a configuration of 10 points, we don't assume anything about it.
Then we lay a coin grid that we shift and rotate the coin grid uniformly randomly on top of it.
We can make a random variable X_i for each of the points that is 1 if the coin is covered and 0 if the coin isn't covered.
Such Random Variables are called indicator variables. For any X_i the expectation can be calculated like E(X_i) = 0*P(X_i=0)+1*P(X_i=1) = P(X_i=1) = P(point i gets covered by the coin grid) = 0.907..,
because the (good area)/(total area) = 0.907, and the grid is uniformly rotated and shifted. This probability is independent of where the point was placed because the coin grid is infinitely tiling and does not cover any position "more often" than another position.
Now the probability theory part: It could be that the X_i's are not independent, for example if the configuration was really evil and always had one point not being covered. But here's the trick: E(X+Y) = E(X) + E(Y), EVEN if the X and Y are not independent. So E( sum (X_i) ) = E(X_1) + E(X_2) + ... + E(X_10) = 10* 0.907 = 9.07.
And now with the same observation as in the video, we can conclude that a shift and rotation of the coin grid must exist such that sum (X_i) >= 9.07, and as the sum of X_i can only take on integers and is bounded by 10,
a shift and rotation must exist that covers all 10 points.
Now for why your 0.8 square proof is wrong:
Say you fix an arbitrary point in the unit square. Then you place randomly a square of side 0.8 inside the unit square.
The probability that the arbitrary point is covered by the smaller square is NOT always P = 0.8^2. Say for example the arbitrary point lies at (0,0), then the P(point is covered) = 0 (only one position out of the infinitely many positions of the smaller square covers it).
So your proof simply doesn't work as you can only conclude E(X_1 + X_2) >= 0*2 = 0, (if you give X_i the same meaning as above) which doesn't buy you anything useful.
Concluding, it's really important that the probability in this kind of proof is independent of where the arbitrary point is placed, and the whole trick is that E(X+Y) is always E(X)+E(Y), even if X and Y are not independent.
Have a nice day!
The proof is fine. Let X be the number of points hit and Xn be 0 if the nth point is missed and 1 if it is covered.
Then X = X1+X2+...+X10.
The expected value of X is the expected value of the sum of Xn but expectation is linear (even for dependent variables) so we can equivalently find E[X1]+E[X2]+...E[X10].
But all these individual expectations are 0.907...
There is no gap in the proof. However you don't need expectations to prove it, you can also just talk about probabilities as I've seen in another comment.
You're basically not trusting that linearity of expectation holds for dependent variables. It does, this style of proof is used all over the place and is also valid in this video.
Further, you're clearly not an authority on the subject but your writing style suggests you are, that is dishonest.
Copy-pasting response from above:
There is no missing point in the proof. It is all covered by the linearity of expectation proof of which you can see briefly on the Briliant page in the video.
If the position of two points is dependent (which in our set-up basically means that they are a fixed distance from each other) then if you position the circles randomly, there is about 0.907 probability that any point is covered. There is therefore 0.907 probability that point 1 is covered and a probability of 0.907 that point 2 is covered (you can just imagine we removed one of the points for a moment and you will see that it is the same case as if there only was one point).
Notice that this does not mean that these points are independent. In general, there are 4 possible situations:
1) both point 1 and point 2 are covered (let's assign probability P12 to this),
2) point 1 is covered but point 2 is not (probability P1),
3) point 2 is covered but point 1 is not (probability P2),
4) neither point is covered (probability P0).
We don't generally know all of these probabilities but what we know is that the probability that point 1 is covered is P12 + P1 = 0.907 and the probability that point 2 is covered is P12 + P2 = 0.907. Therefore P1 = P2 which is also apparent from the interchangeability of both points (there is no way to tell them apart).
Now let's calculate the expected value of covered points:
E[covered points] = sum for all possible cases (points covered in a given case)*(probability of the case)
E[covered points] = 2*P12 + 1*P1 * 1*P2 + 0*P0 = (P12+P1) + (P12+P2) + 0 = 2*0.907 = E[point 1 covered] + E[point 2 covered]
If we have three points:
E[point 1 covered] = P123 + P12 + P13 + P1
E[point 2 covered] = P123 + P12 + P23 + P2
E[point 3 covered] = P123 + P13 + P23 + P3
E[covered points] = 3*P123 + 2*P12 + 2*P13 + 2*P23 + 1*P1 + 1*P2 + 1*P3 + 0*P0 = E[point 1 covered] + E[point 2 covered] + E[point 3 covered]
and similarly for any number of points.
I hope this clarifies things a bit.
POSSIBLY SIMPLER, BETTER RESPONSE FROM BELOW:
Edit: Red Storm in the replies to this comment gave a really good proof, which I will repeat here for anyone else confused:
First, label each point 1-10. Now, if you imagine all of the possible coin tilings, 9.3% of them will miss point 1. Similarly, 9.3% will miss point 2, and so on. Now, even if none of the "miss" coin tilings overlapped with each other, a maximum of 93% of coin tilings will have been eliminated, since there are 10 coins. But that still leaves some tilings left over! Therefore, all point arrangements have a solution (actually, this also proves each one has an infinite number of solutions too!)
@@martinvitvavrik9417 Regarding that proof by red storm, I don't understand how adding up 9.3% (x10) guarantees some "left over" tilings which are necessary solutions to the problem. It seems to me that 9.3% is the probability for the *average* scattering of points, not *any* scattering of points. It isn't clear to me why for a specifically selected scattering the probability can't drop well below 9.3%. Would love any additional explanation!
I think the problem statement is not clear or precise enough. A better problem statement would be
Can you always cover N points with N equal and constant sized (non-overlapping) coins?
or
Can you cover all possible arrangements of N points with N equal sized (non-overlapping) coins?
or
Can you always cover N points with N unit circles that don't overlap?
The current problem statement implies that you can choose the size that all the coins are equal to *after* a single set of N points is presented. Which would be trivial: just make the radius of the coins equal to half the distance to the nearest two points, and place every coin centered directly on a point. These variations make it more clear that resizing the coins after seeing the points is not an option.
I think the problem is more easily solved by specifying a coin, rather than saying “coins of some uniform, predetermined size.” Eg:
Can you always cover 10 points with 10 (non-overlapping) dimes?
i dont see how you get the implication that you can choose arbitrary sizes? I thought the problem was pretty clear
@@ed_iz_ed We're talking about the title, which is "Can you always cover 10 points with 10 equally sized (non-overlapping) coins?". Nothing in that sentence makes it obvious that the size of the coins is fixed.
@@TheBasikShow ah yes, you are right with that one, but as you say, it is trivial for any n like that so it kinda implies the other constraint
I feel like the minimum number of points to force a "no" for the always covered case is a more interesting problem.
From what I can tell, you need an arrangement of points that is just barely sufficient to force two coins/'unit circles' to act as blockers for some of the points.
But that's much more tedious to show, because it's not that easy to force coins to not cover some points.
Such a cool little problem. Thanks for going through both why it's hard, and the awesome way to solve it.
Love that proof. Thanks for explaining it!
How do we know that the expected value for every configuration of 10 points always will be 9.07? Basically how does one know that the linearity of expectation holds?
Mathematicians have proved it... (duh?)
Because linearity of expectation allways holds.
If you know, or look up, the definition of "expected value" for continuous random variables, it pretty much directly boils down to the linearity of integrals. Of course, if you want to go further and prove that too, you'll have to first learn about how an integral is defined.
This is the proof of linearity of expectation:
Let X and Y be random variables (they could be dependent or independent it doesn't matter).
let S be the set of all possible events. For every event s in S let p(s) be the probability event s happens and let X(s),Y(s) be the values X and Y get in event s respectivly.
Now for notation whenever I'll write sum_s{...} I mean sum over every event s in S of ....
Now the proof:
E[X+Y] = sum_s{(X(s)+Y(s))p(s)} =
sum_s{X(s)p(s)} + sum_s{Y(s)p(s)} =
E[X]+E[Y].
@@tomerwolberg37 Note that your proof applies to discrete probability distributions only, while the random variables in the video had a continuous distribution. The proof for the continuous/general case looks similar, but the sums become integrals, basically.
Hold on, doesn't that only mean it is possible to cover 10 points? It doesn't mean it is ALWAYS possible, just that it is possible period. Am I missing something?
Edit: Red Storm in the replies to this comment gave a really good proof, which I will repeat here for anyone else confused:
First, label each point 1-10. Now, if you imagine all of the possible coin tilings, 9.3% of them will miss point 1. Similarly, 9.3% will miss point 2, and so on. Now, even if none of the "miss" coin tilings overlapped with each other, a maximum of 93% of coin tilings will have been eliminated, since there are 10 coins. But that still leaves some tilings left over! Therefore, all point arrangements have a solution (actually, this also proves each one has an infinite number of solutions too!)
Yeah I'm confused?!
The point is that the statistics are not based on how you placed your points on the plane. So no matter the configuration you will on average cover 9.07 points using the packaging seen in the video, but therefore it must cover all 10 at some point using that packaging. Since these are not overlapping we can just remove all coins afterwards that does not contain a coin and voila. At most 10 coins needed.
That would be the case if the lattice were fixed and the points moved, however we have fixed the points and are moving the lattice. So each value from which we calculate the expectation value represents the same configuration of dots but different lattice position. As stated in the video, there must be one of these lattice positions where all 10 are covered to get an average of 9.07. So we have proved there is an answer to this configuration. Because we didn’t state anything about the configuration other than that it has 10 points, we can apply this proof to any configuration of 10 points. So it is true for every possible configuration.
So happy someone else noticed this
always = regardless of the positioning of the points
I'm now extremely curious as to how they can prove 11 and 12 can also be done (according to the paper) since this proof only works for 10 and below
This was really satisfying considering I just finished a stats course this semester where we learned about Expected Values.
But a proof like this doesn't guarantee every arrangement of 10 points can be covered with 10 coins, right? This just guarantees that the probability of being able to for a random arrangement is 1. Subtly, this allow for arrangements with probability = 0 to be impossible to cover. For example, the counterexample of 45 points is impossible to cover with 45 coins. However, the probability of getting exactly that arrangement when randomly placing points on the plane is zero. Otherwise, you could give a similar example to the one provided for the counterexample of 45 points; assuming the placement of each point is independent, any given lattice has a 90.3% chance of covering any given point. Thus, the probability of any given lattice covering every coin is .903^45, which is unlikely but not impossible. Since we can try infinitely many lattices, by your argument 45 should be possible too.
Thank you for the great video @Zach Star; really got me thinking.
I appreciated the "nonobvious" explanation at the start, as that was one of the first questions I had
It depends upon if you have a fixed "size of coin" where the dots are chosen afterwards, or if the "size of the coin" depends upon the points you pick first. In the case where the "size of the coin" depends on the points you pick first, it's always possible . Just make the "coin" less than half the smallest distance between 2 dots. Finite number of dots means that you have a finite number of distances to check, and is therefore doable.
That's what i said before reading your post lol
Hell, just make one coin big enough to cover all 10 points!
That doesn't exclude the existence of one special configuration(P=0) of points that can't get covered by ten coins.
I think for any given single point the expected value of a random max density pack covering it is 0.907.
So, since sum of expected values is always, no matter if the events are dependent, is the expected value of the sum, the expected value of any given 10 points covered is 9.07.
We are working with any given fixed configuration of points at that moment.
It literally does. And I can't see your thought process on why you think otherwise.
We are not averaging over configurations of points. We always use that one configuration.
We are averaging over positions and orientations of the mesh grid. (As I think of it, we only need to average over positions and can keep the orientation fixed.)
Yes it does. The proof works for any configuration of points. Note that the tiling of coins is random not the cofiguration of points.
Insane insights right there
Fixed size for the coin but no information on what that size was made me think more than the video itself... I learned nothing from the video but it inspired me to think more about the area of a circle in a square
Thanks Zach, your videos are amazing at every level. Hug from Portugal.
might have been worth noting the expected value is probably why the previous best lower bound was 11 (since .907 * 11 = ~9.97, i.e. less than 10)
That proof was totally unexpected but we expect unexpected things a lot in math.
For any set of n points:
a) It is always possible to chose a coin size small enough that each coin covers a single point.
b) It is always possible to choose a coin size large enough that a single coin covers them all.
What did I miss?
the coin size is fixed, not arbitrary. the problem formulation didn’t really make this clear enough.
@@jonathancangelosi2439 I figured out fairly soon in the video that he changed (as he said) the “unitary circles” to “coins” precisely to get rid of the confusion of getting to choose the size of the circles. ITS COINS. We dont get to choose the size lol
@@jonathancangelosi2439 how is the fixed size of that coin chosen?
@@principal_optimism it doesn't matter as long as you place the points after picking a size. If you fix the points and then pick a size, you can always use the listed tricks, and the problem becomes trivial. But if you pick the size first, it's just equivalent to scaling the plane by that size and using unit circles
Thank you Zach. I love your videos from Morocco 🇲🇦❤️
Here is a perspective on the Monty Hall problem:
Imagine you pick one door and stick with it. It does not matter what Monty does to the other doors (but he opens a door that is not your door and has a goat/nothing/zonk/whatever). The door you pick has a 1/3 chance of being the good door. That is equivalent to choosing to not switch. Since winning by staying has a 1/3 chance and it is guaranteed (probability of 1) that one choice leads to a win, then switching has a 2/3 (1 - 1/3) chance of winning.
Here is my simple explanation: which door is your first door does not change; which door has what behind them does not change. 2/3 chance your first door is bad so you should switch; 1/3 chance your first door is good so you should stay. (2/3 of the time, switching is good.)
@Zach Star this packing density reminded me of material engineering lattices (BCC, FCC...)
My money is on 26 dots.
The first dot invalidates 0.093 (1-p) of the field(unit square)
Every consecutive dot eats another .907(assuming p is the yellow area in a unit square) less of the field since you can't invalidate twice
At ~26 dots the field will not have space, all 0.907(.912) percent of the field will be covered so the next dot will be somewhere outside a coin.
What
@@cubing7276 the general problem, "how much points(the minimum amount) is necessary to have a point, not underneath a unit circle", using probability as a rough estimate. If you cover more space than a coin(the coin lattice!? Ignoring the specifics of rotation and translation) has, then there exists a case where a coin doesn't cover a point since there is just not enough space. Lowering the maximum from 45 to around 26 without an example (which would be necessary)(which is also near the middle of the missing space (45-13) covering my ball park estimate check)
So close to one millions Zach
For me, that doesn't work out. Either I'm missing some crucial information here, or there is some flaw in the argument.
Basically, the proof with the expected value goes as follows:
There is an E(p) = 0.907
With P_n = {p_i | where 0 9
Therefore, there must be at least one occurrence of 10.
But that requires the points to be independent, which they are not. They don't even have to be random, as the question is, if this holds for *any* set of 10 Points. So I could deliberately choose a set. So I don't see that used linearity here.
I absolutely can place the points as densely as I wish, recreating the situation of just one point: I'll hit or miss all coins together or none of them. Therefore, the points aren't independent.
Two dice are independent. Linearity holds for that Szenario.
If I'd draw ten random points on the lattice each time, that would be linear too.
With a fixed set of dots and only the latice moved I only see one random variable and no linearity whatsoever.
Conclusion is probably true.
But I can't follow that argument.
He quickly mentions that expected values are linear (he really should have explained more about this).
That means that the expected value of a sum is equal to the sum of the expected values. It works even if they are not independent.
So the expected number of points covered is really equal to the probability to cover a point multiplied by the number of points, even if they are not independent.
(and you are right, they are really not independent)
@@isaz2425 ohh, yah! Because of the integral nature of expected values! Thank you for pointing that out ^~^
real interesting stuff
1:22 Cant we use 45 smaller coins? Just bigger than the points themselves? Or did i miss something?
we are bound to coins of one size
@@bot24032 ohh, unit circle, i see, tnx
The coin is size fixed but the points can be arbitrary close together but a bit larger than a coin so that the coins cannot cover all at once
0:43 The coin size is fixed. Then using the diameter of that specifically fixed coin, you can create this 45 shaped point which can never be covered. edit (without overlaps)
0:05 actually he doesn‘t say the coins have to be the same size in every configuration, only that the coins all have to be the same size. so i dunno, but the paper apparently phrased it with unit circles which would make more sense. if you could decide the size however you could just always make the circles so small that the centers of them could be on the points without overlap and then it wouldn‘t really be a puzzle anymore, so he probably meant to say they have a fixed size.
if I understood this right then with this method you can't show that it will always be true with the case n = 11. But it says up until
This is Lemma 3 in the article. It's a little more complicated, but it goes something like this. They take the hexagonal packing S again and consider all translations S + (x,y). Let (x_i, y_i) be the points we want to hit. Then they observe that:
S + (x,y) fails to cover the points for all (x,y)
if and only if
every point of the fundamental hexagon is missed by some S - (x_i, y_i),
Now they consider the vertical line segments (or cross sections I guess) of the fundamental hexagon, and show with some algebra largely left out that no matter how we choose the points, some of the vertical lines will always be partly covered by the sets S - (x_i, y_i). Specifically, some vertical line will have at least a fraction of 1 - 0.942809 > 0 of its length covered.
Loved this problem but that video title confused me all the way to Mars at first until you explained what the problem was
Nice!
Thanks
The question iso not well make. In a métric space you can cover any enumerable quantity of distinct points by disjoints neighborhood, that means open bolls. I think you must remake your question in appropriate manner. For instance, if I have n points so a take a disk with radios 1/4 of de infimo of the distance between all pair of points. In this way it is possible separate points with disjointed disks. This is called a Hausdorff space.
Hey Zac! I would really love it if you could make a video on the engineering physics degree and compare it to a pure physics degree. Thanks!
Provided there is no limit to the number of points that can be placed under each coin, and given the points are infinitely small, the proof of this is trivial. If the argument was that you would need to have one point and only one point per fixed size coin, you might have to allow for coins that do not lie entirely within that plane, because you could otherwise have all points but one surrounding a middle point, where all points would be able to fit under a single coin. If you can have more than one point per coin, then if there would be an overlap between two coins to cover different points, you should just use that overlap, and reduce the number of coins required.
We can take this inelegant shortcut for N
Good thing this whole video aimed to answer the n=10 case and didn’t claim anything beyond
@@Untoldanimations Yeah, it's almost as if that was intentional.
If size of coin can be any fixed value than for finite set choose the minimum of finite Euclidean distances between points center that minimum distance sized coins at each point.
fun thing about it is that this prove actually only works for 10 points max, as the average covering for 11 points is below 10
That was an interesting proof
It took me some time to really understand what the statistics are trying to tell you so here it is:
Let delta = area of a hexagon in the grid - area of a coin.
Now it's worth mentioning that the proof works even if you have a random shape, the same for each hexagon with the same area as the coin instead of the coin.
So let's say we want to move the grid such that the first point is inside a given hexagon on the grid. We have an area of delta where we can't put the point. The second point will also have an area of delta where it can't be (I can explain that if needed), so for both points in the worst case there is an area of 2 * delta where the first point can't be. For 3 points in the worst case there is an area of 3 * delta where the first point can't be and for 10 points an area of 10 * delta (worst case) where the first point can't be. Now since the area of the hexagon is still a bit greater than 10 * delta, it means there is still a place where you can put the first coin inside that given hexagon so that all points are on a coin.
If you want me to clarify some stuff just ask, I know I didn't explain every step properly
Are the points decided before or after the coin size is decided?
Coz like. If its a unit circle coin I can arrange the points in a unit circle of 1.01 unit radius and it wud not work
if the 10 dots are drawn on this circle regularly, then by shifting and rotating the coin grid you can cover these points with much less than 10 coins.
I'm glad to see that all my questions and ill feelings about this proof were already brought up in the comments! Perhaps we can hope for a part 2 in the future that goes into more detail? As it stands this presentation of the proof is very unsatisfying.
When i hear your voice my head goes instantly to comedy, so I’m always waiting for the punchline, and it never comes 😭
Wow you are alive
couldn't you us the same trick from the 45-point configuration: a placement of points that rules out that all can be covered without overlap?
Yes, if such a configuration existed. The proof shows no such configuration exists
Uh no offence, but what Austin said was inaccurate because this proof for 10 points actually works. The reason why it doesn't work for 45 points is that if you multiply 45 by 0.907 you get a number less than 44, so if it were the case that every lattice covering on a given configuration is between 0-44, we can't reach a contradiction like we did with 10 points.
Uh no offence, but what Austin said was inaccurate because this proof for 10 points actually works. The reason why it doesn't work for 45 points is that if you multiply 45 by 0.907 you get a number less than 44, so if it were the case that every lattice covering on a given configuration is between 0-44, we can't reach a contradiction like we did with 10 points.
Uh no offence, but I don't know what Austin is saying. The proof for 10 points actually works. The reason why it doesn't work for 45 points is that if you multiply 45 by 0.907 you get a number less than 44, so if it were the case that every lattice covering on a given configuration is between 0-44, we can't reach a contradiction like we did with 10 points.
Rly wondering how they proved it for 11 and 12 points, as the expected value is off by more than 1 for them.
There is a part about it in the linked paper, but I'm not smart enough for that.
Nice
why couldnt this proof be extrapolated to find the first integer n where .907n < n-1 to find the first value where the question is not true?
First off, the number where it stops working is just 11. 0.9069*11 is 9.976, which is less than 10. However, just because this one particular proof no longer works doesn't mean that NO proof works. In this case, the people that wrote the paper likely found a proof for 11 and 12 coins as well.
I didn’t know this guy did this instead of comedy, damn.
Just an all around wonderful video. Well done.
what do you use to make your videos?
Paused right before the “this is not obvious” to try to prove it and failed; I assumed that there was nothing special about 10 and tried induction.
Can I have your suggestion ,Zach ? I'm really interested in studies of mechanics ( statics and dynamics ) chemistry , and cslculus. And at this time I'm self learning all those topics above .what major should I take ,Zach ?? Thx..
This is a great problem!
edit : I am Wrong. I thought that the configurations of points were changing and the coins were constant but its the opposite.
Here is what I thought before:
The proof only shows that there exists atleast one situation where all 10 points are covered but it's didn't prove in all configuration of points.
To make it more clear, when you randomly placed the points, there were some configurations where the points were not inside the coins right(5:29, there are # pt covered with values 8,7,9,4. what about these configurations )
Configuration of points is arbitrary. What we are changing is position of coins. So in one of the position of coins, all 10 "arbitrary" points are covered.
So for any configuration of points, you can find one arrangement of coins where all 10 are covered
@@mantratrambadia3063 Thanks
Not obvious to my why linearity of expectation holds here. Are the probabilities of covering each point really independent?
It doesn't matter. Linearity of expectation holds even for any dependent variables.
No they are not independent generally.
But as pointed out above, it does indeed not matter.
I need some explanation :( The two dice, as you said, are independent events. So the expected value adds up. But one particular point will affect weather some other point is covered.
You didn't "really" explain how this worked.
Read through a few of the other comments around here. The video does a poor job of explaining or at least highlighting (and only briefly mentions/cites around 6:06) the fact that expected value is linear even for dependent events.
I think the true reason this proof doesn't hold is not the linearity of expectation, thats fine, the problem is the "tossing latices" argument and the limit of relative Frequencies.
Okay, my first instinct is to try and find or describe a configuration of points where it's not possible, just to get a feel for the problem at hand.
If I do find a configuration like that, I've proven it's not always possible, and I'm done.
If I can't just find one, I'd try to list some properties that a hypothetical impossible configuration would have, then find contradictions between two properties or between properties of the configuration and properties of the "environment", or anything we know is true that applies here.
That approach works by itself, but sometimes it helps to look at it from the other side, and try to find patterns that would try to prove the theorem true, and to see how or why you aren't able to prove it and possibly use that proof to prove that the original problem was actually false.
And what about cases where 10 < n < 45? We have proven this holds up to n = 10. We know the counterexample for n >= 45. But what about in-between? Is there another proof or is there another counterexample for n = 11?
He literally said that it's unknown between 12 and 45, so there's your "answer". There is probably another proof for n=11 but it doesn't work the same way as the one in the video for n=10.
Really interesting use of probability to prove geometry
the assumption "For all sets of 10 points, and all values of R, the average number of points covered between all offsets of lattice of R = 0.907" feels... slighly unearned? Like it sorta makes sense but should be worked towards
Just when I said to myself "seem obvious.." 1:01 lol
Not sure how high up would this comment goes, but here's my best attempt to explain to a layman: yes, the proof is correct, and it is perfectly rigorous. The statement I'll be using would be "there exist a non-overlapping arrangements of 10 unit circles that covers any 10 distinct points on the plane", and I'll call the theoretical most-dense unit circle packing the "perfect packing".
I think the one point part is perfectly reasonable to anyone, so I'll begin with 10 points. Select any 10 distinct points, now it only remains to show that we can cover these 10 points using 10 unit circles. Why? Because no matter what kind of points arrangements you come up with, I can always repeat the same proof on them, since the proof in no way restrict the set of 10 points.
Now we cover the plane using the perfect packing. The expected number of points that will be covered will be 10x0.907... = 9.07... .Many people seems to confuse expectation with probability. If we take the example of using only 2 points, and calculate the expectation, it will be 2 times .907. The probability that both points is covered is of course more complicated due to dependence but we do not care about that, all it matters is that the expectation is 10x0.907.
Now, the cool thing about expectation is that you could think of it as an average, i.e. what is done in the video. Another cool thing is you could always guarantee a member that is at least as large as the expectation (or average). But since the number of point that is covered is always an integer, this implies there is a member of at least 10, and we're done.
Finally, bear in mind that this is an existence proof, we only need to find a member that satisfy the statement. It doesn't matter even if 99.999999999% of configuration could not do it, as long as one could do it then we're done.
I only understand halfway. You said "... you could always guarantee a member that is at least as large as the expectation (or average)", but isn't this "member" you refer to selected from *some* random scatterings, not necessarily *any* random scattering?
@@gershommaes902 Recall that we fixed the scattering of points at the beginning. The experiment we're doing is covering the plane with perfect packing (and changing it by rotation and translation). Hence this "member" is a particular rotation/translation of the perfect packing that could cover at least 9.07... points, or simply 10 points.
@@Windz0508 Thanks for the reply! :) How do we know that the 9.07 figure occurs for *every* scattering? It seems to me like it only occurs for the *average* scattering.
@@gershommaes902 Because we have chosen a random scattering at the beginning. The 9.07 figure is calculated by taking the average of points covered by tossing on a perfect packing. A simpler to to put this is: for any scattering of 10 points, a random toss of the perfect packing will, on average, cover 9.07... points.
@@Windz0508 I don't understand why an average of covering 9.07 points entails that every scattering will have more than 9 covered points. Averages hide information (e.g. my class average could be 90%, but it's possible there are some assignments on which I received 0%), and it seems to me that having a high average covering could hide the fact that for some scatterings there is no full covering.
I don't deny what zach star is saying; he's way more knowledgeable than I am. I just feel I'm missing some critical insight.
Well, the proof that a closed loop in 2d Euclidean space has a bounded inside and an unbounded outside is also obvious and not obvious.
That was really clever! Linearity of expectation has to be one of the most OP tactics in math
OP? I don't know about that, but it does sometimes work when nothing else does. :)
Topology in the plane
I have a question: the problem asks us to prove for all possible arrangements of the points, but doesn't this proof prove for only a certain number of possible arrangements? Please clerify..
Nope, because you can use linearity of expectation for any given configuration of points, so you only randomize the coins, but the points are given to you. And the expected number of points is ~9.07 for ALL configurations.
He doesn't make any assumption about the position of the points in the proof, so it means for all possible arrangements of points, using this reasoning will lead to the conclusion that it's possible to cover them.
Are you suggesting that every configuration of points has that "toss" that covers all of them? To make the proof works. Isn't it proof by itself? Okay, if we talking about some random configuration it works, but for every configuration? I think it requires elaboration.
Surprisingly easy, you dont even need any math for this
Hey man. I would love your advice on this: I like to build stuff, make things work, what engineering would you recommend me? Is EE the answer?
Thanks man🙏🏻 I really appreciate your answer or anyone else🙏🏻
I don't know if you'll read this, but here goes:
I'm confused about why this proves that ANY configuration of 10 points can be covered by 10 coins or less. What stops me from using the same method for 45 points? There are many configurations of 45 points that can be covered by 45 unit coins or less. In fact, we only know that this works up to 12 points, everything else from there is a mystery until 45 points which we know is impossible, which should mean that any number of points above 45 is impossible too, if I'm understanding this correctly.
My point (heh) is, how does this prove to us that there isn't any possible combination of 10 points that is impossible to cover? What's the proof for 11 and 12 points? And why does this method stop working at 13 onwards?
My only guess for 45 is that, if we used this method to get the average, we'd get an expected value of less than 0.907*45, meaning there was some configuration that couldn't be fully covered. But if this worked, then we'd know if 13 was possible or not, there should be no question. Yet there is. That's why I don't get how this proves the original proposition.
It seems to me that as long as n-1/n is lower than piV3/6 there is always a case where all points will be covered. In which case 11 points would not always be covered because 10/11 = 0.90909 which is slightly higher than piV3/6. Does that count as proof that 10 is the maximum?
Zach Star's pinned comment I think clears a lot of confusion up ^
Because I was thinking: "whatever configuation of 10 points you have, you can just make the coins small eanough to fit the points and not overlap"
but the key constraint in this problem is that you can't control the size.
Simple example to show that the dice analogy is wrong. If the tosses of two dice are not independent you can make the expected value of the sum to be different from 7.
Say the second die rolls 6 for all values of the first dye roll (we make the second roll dependent this way). What's the expected average? 7 or maybe 9.5?
The second die is still independent of the first die in your case, just that the second die has expected value of 6
@@cubing7276 not true. This is also a dependence, just a constant one.
@@ahr2g6 OK if we replace the second die with another one that has all 6, it's the same situation but they're independent so your scenario should be 2 independent dice
@@cubing7276 Go read my comments under the top post by Zack, to spare me discussing trivial things.
@@ahr2g6 I don't think you understand what dependence means, elaborate
The probability of dice 2 rolling 6 doesn't depend on what dice 1 rolls and the probability of dice 1 rolling any particular number doesn't depend on what dice 2 rolls (at least not in a meaningful way), therefore the 2 dice are independent
then what about a table l*l m with a square fabric l*0.75l m. the expected value of the number of points being covered is 0.75 for one point, for 2 it's 1.5 yet two coins in the opposite corners can't be covered. I think something doesn't add up
In your settings there are other constraints that change the problem. Namely the cloth is constrained to remain wholly on the table. If you take an infinite number of square tables arranged touching side by side, and an equally infinite number of square fabric cloths that make a lattice and they are no longer constrained to remain on their original table, you can see you can cover both coins, by shifting the cloths over the corners.
Ur 2K away from a milli, I just subbed to help out!
6:08 how would I do it if I wanted to find what the chance of rolling a specific number at least once is for multiple dice? For a single die it's 1/6, but it's not 2/6 for two dice is it? Because then you'd end up with a 100% chance at rolling 6 dice which isn't true.
Not, it's not 2/6 for two dice. Your logic is applying the "linearity" argument to a probability. But the proof relies on linearity of expected value, which is a different calculation than probability.
The parallel is with the number of dice that show a specific number. For 1 die, on average 1/6 die will show that number; for 10 dice, on average 10/6 dice will show that number. That works.
@@landsgevaer Okay, thanks.
You said that if we could change their size it would be trivial but what if we take away 1 coin? Or 2? That is what I was expecting you to say because I didn't hear you say we couldn't change their sizes.
Please make a video about mining engineering
God I love how this proof works
Wow so 12, 13 and 14 proofs and lack thereof is where things get really interesting obviously 🤯
Yes
Couldn't you have essentialy the same setup as the 45, but with ten?
Apparently not :-)
The gaps in that outer ring are big enough for the gaps in the grid to squeeze between them.
A point is 0 dimensional.
A coin is 3 dimensional.
No matter the number of points, a sufficiently large single coin will suffice.
For 10 points, as they don't have any length, it will always be possible to cover all with a maximum of 10 coins in all cases.
You can’t just arbitrary choose the size if your circle every time that completely defeats the spirit of the question
@@Untoldanimations o did I get the question wrong? What does the question exactly mean? Please elaborate.
I thought there would be a proof involving pigeonhole principle but I was wrong.
2:58 it makes no difference if we're placing the point randomly on the plane or the lattice is landing randomly on the plane. Does it also make no difference if we randomly place both the point and the lattice? I believe so, but this isn't proven.
As long as it works for one or the other, we prove it for the entire problem. So even if you assume that these cases are different, the fact that it works for one case proves it for the general case, which can then reduce back to the other case.
It doesn't make a difference, but when we have 10 points, we can't choose where the points go, but we _can_ choose where the _coins_ go, which is why we are throwing the coins onto the points.
My reaction while reading your thumbnail.
Easy!? Hmm... Yep! Wait... Hmm... Hmmmmmmmmmmmmmmmmmmm
Since the average of 9.07 is grater than 9 and they can only be integers some of the lattice tosses must be 10. This wouldn't work for 45 because
45 times 0.907 is 40.815 which is less than 44
Would you call the necessity for one of the numbers to be 10 (given an average of 9.07) a type of pigeonhole principle. It feels like it but i don't know if it is.
Forgive me brother for I have sinned.