i was literally just thinking about this, i mess around a ton in scrap mechanic and hate when i can't see what gates in a line are connected or not, and this is literally the problem that would solve that issue
7:07 this is probably the nicest or say most tangible example in my memory so far why knowing of primes is useful. it gives u anchor points about divisibility & divisibility comes up a lot in maths.
In 2002 or 2003 I did a summer REU (research experience for undergraduates) on a variant of this problem with triangle grids instead of squares. A few weeks in I had a nice culled-branch search program coded up in C, but other than that I wasn't making any progress so we switched to a different topic.
That's a great video! Pretty easy to follow, interesting and simple problem, not super handwavy, but also not extremely advanced. I'm sure you'll be featured in grants video. Great work!
If I understand correctly, based on this video and Wikipedia, no N is known for which we definitely can't place 2N points. And for n ≤ 46 there are 2N solutions. I feel like the answer might be just a clean 2N but it's too tricky to prove.
Very nice, but the over usage of stock photos and footage is distracted IMO. You can trust your explanations and the maths itself to keep the user engaged.
I included the stock footage because that's what I usually do in my other videos. I wanted it to feel like something I created myself rather than just a knockoff of 3b1b. That being said, I recognize that it's not everyone's favorite style.
@@SignoreGalilei Fair enough. It definitely has a fun "HalfAsInteresting" kind of vibe that I generally liked, there was just a bit too much of it. For my tastes anyway.
Great video. My math skills are pretty poor but I followed easily enough until at about 5:00 when the video changes from the visual representation to the algebra. I didn’t realise that the point was comparing the two slopes (from i to j and i to k). I think it would’ve been a little clearer if the algebra was done alongside the visual, with both on screen at once and in different colours. But I think I’m alone in having had this difficulty
You're probably not alone in having that difficulty. I think I decided against showing both at the same time because it would have made the screen too cluttered, but as with everything there are tradeoffs. I'm glad you enjoyed the video anyway.
@@SignoreGalilei Agreed with @myfootsitchy. I'd have liked to have seen a little clarification of what the contradiction was actually contradicting, as it got kind of lost along the way, and I had to do a bit of scrolling back to double check. A small gripe in an otherwise good video, though.
Ok I kind of want to try my hand at this. One idea I had was to extend this to the general “No-K-in-a-line” problem. So far for the maximum number of points you can fit on an nxn grid I got F(n,k) = 0 if k=1 (no way to not have 1 in a line) 1 if k=2 (counting any diagonal angle, any two points would be a line) n^2 if n>k (you can fill the whole grid) n(n-1) if n=k (this is the only other case I can prove generally so far, basically just fill the whole grid minus one diagonal, and then swap the corners if n is even) just messing around on a chessboard I was able to find at least one solution for every case up to n=8 for f(n,k) = n(k-1) Which would fit with the 2n upper limit for k=3 I don’t really have much insight yet but my idea is that if I’m able to show that you can take a solution to f(n,k), remove n points, and have a solution to f(n,k-1), you could find a general solution by induction, but I’d need to do a lot more work to maybe get to that point
I know this comment is over a year old, but the line of: "n^2 if n>k (you can fill the whole grid)" had me stuck for 20 minutes trying to figure out how you could fill the whole grid if when n > k. Like a 3x3 wouldn't be able to be filled as you would easily get 1 or 2 in a line. But then I figured out it was probably meant to be k > n (/ n < k), however, I might just still be confused, so correct me if I am wrong in assuming it was a typo that n is greater than k. Edit: also the one below it says "n(n-1) if n=k" should this also be "n(k-1) if n=k" ?
Kind of a random question for a comment box, but one I've been wondering about and I've had a hard time vocalizing to fellow mathematicians. How would you approach something you're not sure is an open problem or not? I've attempted to search up the topic or related terms, and struggle to find much more than the basic information. But I feel like the topic I've now written 20 pages about is definitely something that has been answered before.
I assume you've tried searching MathSciNet or similar if you have access? I think the worst case if you keep working on it is just that you've got a good sense of what one researcher can do in the area, if it turns out to already have been solved.
@@SignoreGalilei That's pretty much been my mindset while working on it. I have tried looking for related things on databases, but nothing comes up--at least with the wordings I've used to describe it.
You can also potentially ask someone in the field that the problem is in, whether they know if it is open, and if they don’t know, they might suggest someone else who might know? (If you are concerned that, if it is open, this might lead to someone else working on it and putting time pressure on you... idk, I don’t have enough experience to confidently say that the risk of that is negligible, but my impression is that there are norms of politeness to not snipe problems like that? )
It's hard. In physics I've sometimes spent weeks working on something thinking it was new, only to find a whole community working on exactly the same thing, but with a different nomenclature. It's hard to know how to search for something if you don't know what others call it!
I thought about doing this in a continuous space rather than a discrete one. In [0,n]² you can choose a circle which has no three points lying on a line. That circle has τ/2*n "many" points which is surprisingly larger than 2*n. I was hoping that this would have some similarity to the limit as n goes to infinity in the discrete case. But that doesn't seem to be the case and arranging the points in a circular shape doesn't seem to be all that good for n>4.
I found a link somewhere saying that if you use convex polygons for n=10, for instance, you can only place 17 points instead of the 20 you can get if you add some in the middle.
In R^2, one can show (using axiom of choice; e.g. transfinite induction) that there exists a set S that intersects every line in the plane in exactly two points. Similarly, there exists a subset of R^2 that intersects every circle exactly 3 times. I think that a similar claim can be made for bounded subsets of R^2 (may need to impose nonempty interior to not fall into the discrete case). There are still unsolved problems in the continuous case, namely what kind of properties such a set has. In any case, this video was pretty good, and I had never considered the discrete case. Definitely enjoyed watching.
@SignoreGalilei I have simple and generic solution for this problem to get 2n points. Consider grid on X-Y axis. for N+1 x N+1 grid and no K+1 points in line, 1. For 1st column, Start putting points from (0,N) till (0,N-K+1) 2. Now 2nd column, start from (1,N-1) till (1,N-1-K+1) 3. Now 3rd column, start from (2,N-2) till (2,N-2-K+1). 4. And so on. 5. If you hit at bottom of column, i.e. 0th co-ordinate of Y-axis, then start remaining points from top of the column. 5. For N-1 th column, you will have points from (N-1, K-1) till (N-1, 0). 6. Now for last column, you will have one point at (N,0) and rest points will starts from (N,N) till (N,N-K+2). I think this is the easiest generic solution.
What about a circle (2d space) or sphere (3d space) of r=n/2? Bigger graph size, bigger circle/sphere. It would be impossible to add points inside or outside of those shapes because then you'd always have 3 for any given angle, but otherwise you'd be at 2 points or less (tangents).
@@gaopinghu7332 Well, for n=10, the biggest convex polygon you can fit is a 17-gon but by including some extra points in the middle (like in the thumbnail) you can get 20 points with no-three-in-line. I found the 17-gon bound on the post "Big convex polygons in grids" on the blog "11011110".
i love how we call something educated guess, and the educated guess has its own proof. i know it makes sense, but i can't stop feeling it is a little funny that in math the vibe check is a "simpler" "easier" proof.
Before watching, my initial guess is: Pi*D, where D is the side length of the grid. The image is of course inspiration, but I think is make logical sense. Taking the case of a continuous "grid", the best way to make sure a line drawn in the box meets at most 2 points is to have a continuous convex shape. This way there aren't any inflection points, which cause 3 point intersections or straight lines, which are ruled out by default. It makes sense to me that the grid density would affect the "resolution" of the circle, which is why a continuous has infinite points, and a circle on a 2x2 grid has 4 points. So Pi*D, where D is the grid size.
The only issue I have with the educated guess method is that it doesn’t matter if the chance that you could get 2n points with no three in line by chance is low. Just that there is one. The odds of rolling all sixes as you add more dice goes to zero as the number of dice increases, but the answer to the question “is there an arrangement of n dice with n sixes” is still yes. Likewise, as long as there is at least one way for there to be n points with no 3 in a line, it doesn’t matter if there is practically a zero chance of getting it randomly, it’s still there
The way I understood it is that you don’t know what the actual chances are. They’re measuring their uncertainty ABOUT uncertainty. Imagine you asked the same question but instead of n 6-sided die, you had n random DnD dice. For all you know you have a d4 in there and the probability of n 6s is zero. So you factor in the probability of all n of your die being d6s first, then the probability of their faces all being 6.
It's true that you only need one way, but it's not just that the chances of getting it on each specific try go to zero, it's that the chances of getting it on each try **times the total number of tries you get** goes to zero. In your dice example, that product stays at 1 no matter how many dice you add.
An interesting check would be, for any given solved n x n grid, look at how many dots must be removed from any two edges to shrink it to a n-1 by n-1 grid. This may suggest a general solution. This problem may be easier to solve it in reverse - how many points must you remove from a grid so that no three points are in a line. Solve for odd number n, solve for even number n and come up with a generalisation and odd/even modulus (ripple) should have a repeated effect on the outcome. The answer will likely be iterative permutations that add up in a similar fashion to triangle numbers, but including quirks of 2D. Then tackle the harder cases of n x m, n x n x n (a cube) and m x n x o. Comparing with 1 and 3 in a row might help. Algorithm-wise, you could either attempt it via (1) a deterministic branching walk according to rulesets, or (2) by using a random filter (flood the grid, pick random x,y and remove a point if it has two neighbours in a north, south, east or west direction, repeat n x n times (at maximum), and save the first 10 or 100 solutions for each n for further analysis, but only for the highest (and lowest?) number of dots. There are many ways to speed this up (e.g. iterate all x,y and if turning the point on won't break the three-in-a-row rule, turn the point on according to some random factor. e.g. working with coordinate lists or multi-linked arrays/lists).
That would be a cool check to run - if you end up coding it, let me know! I'm not super familiar with making efficient algorithms, but I'd love to see what people come up with. There was another commenter wondering about the reverse problem as well.
@@SignoreGalilei Yea, but by then I might find a patern, and if I suspect a number of points I only need to brute force 2 amounts of points - One that's possible x and x+1 that's impossible.
Nice walkthrough. It's intriguing that the conjecture involving pi over the square root of 3 is substantially broken for n = 52 with that solution of 104 points. Maybe the max ratio drops off very slowly as n grows?
I feel like theres some way of conceptualizing this using similar principals to valence electrons where you have general inner patterns which appear for larger N (e.g. an inner pattern for n=8 might appear on n=16). But I'm an engineer, not a math guy =P
I feel like this question would be much easier to solve on a nxn toroidal grid, just like how considering the n-queens problem on a toroidal grid takes its difficulty from almost impossible to solvable in about 1-2 hours.
Ok, I haven't watched this yet but, it seems pretty clear that the design at the start should be the maximum. At least it seems to meet the requirements to me and there are two dots on every horizontal and vertical line. And while there might be some diagonal where that isn't the case it would be easy to test for each unique position. So I'll try watching it but at first blush it seems obvious the answer in the grid shown is (at most) 20.
Just a couple seconds in and I already feel a little silly: I misunderstood the problem and thought "couldn't you just make a circle to have an infinite number of points? That would make it so you have at most two collinear points for any given line". I initially missed the statement that they had to be on the intersections of the coordinates lol.
I just found this. I took two hours to code up a brute force solution and it took over an hour for a 9x9. The 8x8 takes less than a minute. There's too much freedom for brute force. Though, looking at the problem. Is every 2N solution always decomposable into two Latin squares?
For a moment I thought "hey, of course you can always fit p points on a p^2 grid" but then I remembered diagonals. I wonder how the solutions change if diagonals are ignored?
I believe you can always get 2n if you ignore diagonals: place n points along one main diagonal, n-1 points on the line right below it, and the last point in the opposite corner.
I guess this variation is much harder to solve*, but it's what I thought the problem would be before you explained it properly: Fill the grid with as many points you can without any three points on the same line be placed such that the middle point isn't exactly in half way between the two other points. (There's a sequence in OEIS with this property, so that no 3 points will make up a "symetric" line in a 2d plot) *(Though you never know. Sometimes problems that seem harder are easier to solve than those that seem easier.)
@@jamesdavis3851 I've tried to find it, but haven't succeded yet. I'm like 98% sure it was featured on Numberphile with Sloan himself, and I think it had quite and interresting graph. I'll let you know if I find it.
1:48 that’s Professor Mathrülz, not General Mathrülz, his sister. They are oft mistaken for the way they both lean back casually while explaining with a stick.
"How can this still be open?". For most questions of this kind I don't see how they would not be open. First, what do you expect. There are infinitely many grid sizes so you cannot just try all ways in all grids. I would be much more intrigued if there would be a finite problem that is still open (like the existence of the missing Moore graph). So what you probably want is a formula in, say, n. But there is almost never a formula for anything, so I am not surprised. Keep in mind, there is not even a formula for the product of the first n integers... we just make up the notation n!. So you are probably looking for an asymptotic formula. But now we enter regimes that many people are not too familiar with and that many non-mathematicians would be reluctant to count as "solving the problem". And then I also always though these combinatorial problems are so generic, that once solved I can just tweak it minimally and get a completely new problem that is now again "surprisingly" open. For example, consider 3D grids, or no 4 points on a line, or no 4 points on a circle. Finally, for this particular problem in the video I don't see why it should be easy to solve. No three on a line in a grid is connected to number theory which is intrinsically hard. Having said that... I will watch the video now and it will surely be interesting :D
"There are infinitely many grid sizes so you cannot just try all ways in all grids" What? That has never been an issue in any area of mathematics. No one who has done even a bit of math expects brute-forcing to work. It's pretty much the first thing you'd learn in a proofs course, e.g. when learning induction or any other proof method.
@@sk8erJG95 Have you read the rest of my answer. I am building up an argument, and that is merely the first piece. Admittedly, it's a very weak one (and I maybe should have dropped it).
Manim Community Edition for the geometry animations, OpenShot for the video production. Both have good documentation and Manim has a discord server. Manim is easier if you've already learned Python programming, though.
Very interesting conjecture, do the current best known results confirm that? Like is there anyone who has tried to find optimal choices for n=1000 or so and maybe they managed to fit in 1800 points?
11:15 in the exponent, is that supposed to be -3nk³ or -27nk³ (with the cube outside the parentheses)? Either way the form written in the video is rather unnatural which made me have doubts
oh i watched a little more and i guess p is a chosen prime between n and 2n, im not sure if u had mentioned that before introducing p but that makes sense
How is it that modulo is distributive? For example, 1 mod3 - 2 mod3 != (1-2) mod3 Does it only work in that particular case where i and j are nonnegative and also j > i?
((1 mod 3) - (2 mod 3)) mod 3 = (1-2) mod 3 - as I recall, this more complicated relationship always works. Then since i, j, and k are whole numbers less than p, we can make the appropriate cancellations.
Right, I remember something like that, though can't really prove that in head, but I think it worked at least for positives. Anyway, that's a pretty good video, even though it took me two attempts. Maybe that was because of the voice, I had a bit of trouble understanding sometimes. One thing which would also be nice to add, is a combined animation at the end to remind how the U&L bounds changed throughout the vid.
"Mod" isn't exactly an operator in that case, it's more like a different environment we're working inside where everything is constantly being taken mod 3. Which is essentially saying that (1mod3 - 2mod3)mod3 = (1-2 mod3) At a higher level, you can prove that the "mod p" map is a ring homomorphism, which means most algebraic properties of Z will be preserved when looking at Zmodp. The way you wrote the equation has Z on the lefthandside but Zmodp on the righthandside, which is your issue.
Yeah, I kinda handwaved the difference between the operator of taking a remainder and the idea of modular arithmetic. It feels like a topic for another video, not this one.
I'm still confused about 1 thing. Around 8:30 It was shown that there are at least 1.5n points for an n that is twice a prime number, how is that true for all n
It's not going to be exactly 1.5n for every n, but it will be fairly close as long as there's a prime number not too far below n/2. The prime number theorem tells you about how far off you'll be - it becomes a smaller and smaller proportion of n as n gets bigger.
I offer an alternative problem. What is the least number of points that can be placed on an n-by-n grid, no three in a line, such that the addition of one more point must contain three in a line? Enjoy
Fine... 7:10 the halved theorem is not true that's why we all remember it by n by 2n :). Lower boundary. There is no prime in between 2/2 and 2 for a simple 2>1
Surely infinite, right? If you throw in all transcendental numbers? Then, again, if all transcendental numbers could be placed on such a grid, there would be countably many of them, and transcendentals are uncountably many.
The problem here is specifically if you restrict it to the integer grid points. I think even if you only expand that to rational numbers you can fit infinitely many.
@@RoderickEtheria I may be misunderstanding your point. There are indeed as many rational numbers as integers, but integers are all a certain distance apart where as rationals can get as close together as you'd like. Would this not mean you could place a (countably) infinite number of points on the grid if the points' x and y coordinates are allowed to be any rational number?
@SignoreGalilei Precisely. Rational numbers are countable infinite, so you can place them all on an infinite grid. You can give each of the infinite rational numbers an integer value, and there would be no difference in the grid besides the distance between points. It wouldn't change the problem. Throwing in any irrational numbers prevents the grid. There is both countably infinite many integers and countably infinite many rational numbers. Their infinites are the same size, and so a grid could be made of either and solve the same problem. There is no difference in the size of the grid if you have a space between .0001 and .0002 or 1 and 2. Or any other degree you label the rational vs. integers. Irrational numbers couldn't be labeled on such a grid, nor transcendental numbers. You already posited a grid with countably infinite points the moment you specified all integers. The issue arises between countable infinite to uncountable infinite, not between integer and rational.
Explanations in this assume the viewer knows things most people don't. For instance, you don't explain why finding a contradiction isn't just proof your math is wrong.
That is true. I've gone over the ideas of proof by contradiction in other videos, so I didn't feel the need to do it again in this one. There's always a balance to be struck between getting straight to the point and making stuff more accessible.
@@danielyuan9862 When you want N = Infinity, I wonder why you don't give Infinity time complexity too. If you want to run on low time/memory complexity then next time specify that in the problem.
I think the issue is the definition of "solved". For any specific large n, brute force will eventually get you the answer, but if you want to know the answer for every possible large n at the same time, brute force will literally take infinite computations.
9:58, you said odds. Did you mean probability? Odds is the ratio of winners to losers. Probability is the ratio of winners to total. They are similar but not the same. Hope it helps!
You are correct, the probability (not the odds in that sense) is indeed what the authors calculate. Technically (pushes up non-existent glasses), since you can calculate odds from probability and vice versa either one would get you the answer you need. But yeah, probability would be more accurate.
@@deleted-something There definitely is an analogy in three dimensions - and higher too. For lines with more than three points, the pigeonhole principle bound still works, but I'm not sure what else is known.
