Can you always cover 10 points with 10 equally sized (non-overlapping) coins? 

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.

haha block me i dont like you

@@Timmysthirdbirthday k

Yep

The 'at most' is what's lacking in the title.

Same

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 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?

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.

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.

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

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.

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

definetly

No

I went the other way around.

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

But that's much more tedious to show, because it's not that easy to force coins to not cover some points.

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

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!

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.

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.

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.

That's what i said before reading your post lol

Hell, just make one coin big enough to cover all 10 points!

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

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)

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.

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 ^~^

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.

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.

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.

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.

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.

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.

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.

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.)

The strongest proof you said in this comment is ironically the easiest to prove, because you actually know more about what you are trying to prove if what you are trying to prove is stronger.

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.

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

OP? I don't know about that, but it does sometimes work when nothing else does. :)

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.

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.

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.

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.

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.

Its not exactly up to mathematics per say, more about personal preference. Let's say you have 100 eggs and you want to move them from point A to point B. You can only move one basket at a time, and you have a 10% chance of dropping the basket and breaking all the eggs. Let's examine two extreme cases. Case 1: you move all 100 eggs in basket in one go. Theres a 10% chance that you break every single one, and a 90% chance that you have all 100. Case 2: You move every egg in its own basket. Each egg has a 10% chance of breaking, so on average the amount of eggs should be close to 90. Which is better? Well, they both have the same expected value, so I could imagine situations in which either or is better. If ending up with 0 eggs at point B is total disaster, but ending up with 90 is ok, then it's probably best to take them one at a time. If ending up with anything less than 100 eggs is a disaster, then you should take them all at once, as otherwise taking them one at a time is almost garruenteed for you to lose at least one compared to only a 10% chance to lose them all.

No, 45*0.907 gives 40.815 which only guarantees an arrangement that covers 41 coins but doesn’t guarantee a 45 coin case

Apparently not :-) The gaps in that outer ring are big enough for the gaps in the grid to squeeze between them.