Unsolved Math: The No-Three-In-Line Problem  

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

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.

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.

As far as lower bounds go, you can always place at least two points. That’s my contribution. Hope it helps.

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!

inb4 the next step to this puzzle is some equivalence to an incomprehensible conjecture about modular forms

I may be a lowly engineering student, but it would be cool to solve one of these smaller problems one day

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.

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

This is a good submission to SoME3 and a great video. Good job!

at 0:44 the point with the checkmark is in line with points 6 and 8

I honestly can't believe how complicated this got! It seems like such an innocent problem...one that would have a really convenient solution or trick.

Oh my God, this video is a masterpiece, what a beauty!! What genius!!! Thank you from the heart

Great video! I never knew about that rule for dividing in modular arithmetic

Amazing video! Never heard of it before...

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.

Great video! Many thanks

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

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

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?

Instant subscription just for the name of the channel

Awesome video!

there's something very orderly and symmetrical about the results of the dots. I wonder if this could be a jumping off point to finding the solutions.

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.

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

Nice video explanation! Must’ve taken a lot of work.

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

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

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

so 1.8138n + o(n), with o(n) probably still being quite significant at n=1000 I imagine

Very rational problem, simple definitions and explanations and the intended puns about Galileo :). Is this connected to the Riemann hypothesis?

I asked that kind of question on Quora for fun four years ago! I didn't know that the general problem was unsolved, lol. I just solved it upt to n=6.

Has anyone tried to tackle the generalised version for higher dimensions? This one would be a special case, d=2, s=3

Is it possible to apply the stimulated annealing technique to get a lower bound empirically?

don't mind me being a D&D DM who uses math problems like this this one to create puzzles for my campaigns.

nice animation

So does the conjecture then say that there is a largest n such that 2n is achieved? I imagine the conjecture is that the limit of the ratio (number of points)/n converges to k = pi/sqrt(3) ? Hm... This brings to mind another question: suppose we look at (max number of points for n) - kn, and look at how large a range of values that can be in, and like, rescale it to keep the range independent of n, and then we take a “random large n”, would the distribution over this rescaled difference, converge to some nice distribution? (Where by “random large n” I mean like, the usual way of pretending there is a uniform distribution over the natural numbers, even though there isn’t.) Could the same approximation used to justify the conjecture be used to come up with a heuristic estimate of a distribution for what the max number of points that fit in an n by n grid is? Like, if we pretend that for any 3 points in an n by n grid, the probability that they are co-linear is independent of the chance for any other 3 points, So, for the n by n grid, there are (n^2 choose 3) independent random variables, each with a probability (the function of n described in the video) of being “yes, these 3 are co-linear”, then, hm, there is a random variable associated with this setup which is “what is the size of the largest subset of the n^2 points such that no 3 among that subset has their associated random value be “yes, these 3 are co-linear”. This seems like a distribution that would be difficult to characterize... Maybe it could work to say, after those random values for co-linearity have been picked, independently, randomly select a subset of size j of the n^2 points, and then estimate the probability that all subsets of size 3 of that subset have an answer of “not co-linear”..? And I guess then the task is evaluating, what is the probability that the values of “which triplets are co-linear” are such that [given these values of which triplets “are co-linear”, the probability that the randomly selected subset of size j, contains no “co-linear” triplet] ? Does that make things any better? Hmm.. Well, P(A or B) \le P(A) + P(B) so... if adding points to the subset one by one, the chance that at least one of them is “co-linear” with two that were previously added, is at most the sum of the probabilities of each of them individually being that way, and... hm, this line of thinking seems to us the joint distribution though, not the “probability under one distribution that the probability of another thing under a distribution depending on the value from the first one, being non-zero”... Well, I guess P(X is s.t. P(f(X,Y) | X) > 0) is, greater than or equal to P(f(X,Y)) (where f(X,Y) is a predicate) so it should give a bound in one direction.. So, continuing... the chance of a newly added point being “co-linear” with a previously added two points (where, again, all the “co-linearities” are independent) should be bounded above by (the number of pairs amongst previously added points) * (the chance of a triplet being “co-linear”) and so, \sum_{i=3}^j ((i-1) choose 2) * (probability for a given triplet being co-linear) gives an upper bound for probability of a randomly selected j points, containing a “co-linear” triplet. (i-1)(i-2)/2 summed up to i=j .. well, it will be a cubic in j, for j=1,2,3,4,5,6 it is 0,0,1,4,10,20 should have (j-1)(j-2) as a divisor, so what ratio remaining? 2,6/4,12/10, 20/20 wait what? That’s not linear.. (1/2),(2/3),(5/6),1 ... I’ve made a mistake somewhere... Anyway, I should stop working on this and get to work..

As a programmer my initial idea was to create a program that checks every possible combination and hope that I will have enough computing power.

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.

Is there a known size for which it's not possible to place 2*n pieces?

haha. nice! been watching SoME entries. seems like a lot this year which is great. wondered if anyone would put up something I've spent time thinking about. flammenkamp's stuff is visually mind-numbing! the written docs have some accessible nice arguments, parrticularly around the symmetric possibilities.

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?

Cool

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?

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.

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

How about the question of n×n grid with no m points in a line (rather than just no 3 points)

5:50 It's (15 mod 5)/3=0 not (15 mod 5)/5=0. It doesn't change anything but I wanted to tell you. Also great video.

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?

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.

Great video! A small suggestion though - the stock clips are tacky. The next video would be better without them.

when we got the 1.5 lowerbound i thought we were heading towards e

"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

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

7:18 That 1974 font. 🤣

A pigeon hole is not a dirt hole with pigeons xD.

0:12, isn't collatz conjecture solved last year already?

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

Ai:am about to run 3billon 900millon simulation to find this out in 3months max

How does this chnage if grid is size n by n+c

isnt there a typing error at 5: 51 in the bottom line it should be 15 mod 15 / 3(not 5)

So there is no explicit example where the number is smaller than 2n?

at 6:10, why is p prime? i thought p was the size of the grid

3 points in a row is too difficult. perhaps start thinking about the same problem with 2 points?

Ladies and gentlemen, I am extremely pleased to say, that solution of this problem for a given n exists.

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 had subtitles on at the start information overload

dont you just have them go diagonally from one side to another? edit: ohhh also in diagonals

why did you say that we haven't made progress on the collatz conjecture? didn't terence tao prove something that's like 99% there?

3:12 how? how did you insert a flag meme

Where can I get more data about this You know I am gonna prove this

if its been solved that there will always be for a prime, you know its always possible since you can never get an end to primes.

Where should one start digging? (other than googling the question😂)

10:35 AAAAHH MY EYES

this sounds somewhat similar to sudoku

A simple tiling shows that the maximum number for a grid of size m×n is 4mn÷9. Ah. Any straight line. We can solve this algorithmically...

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.

dynamic programming

Doesn't the statistical argument provide a new upper bound? A subset of a finite set with zero probability must be empty.

Well, I can surely say that you can put 2 points

5:50 you forgot to put 4 in (4+1)mod15. it is not 4 + 1mod15

Unsolved? Let me introduce you to Brute force and Computer.

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

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

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!

Sō

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.

Might need to fix the subtitles, buddy.

Oh wow

The volume is way too low man

not anymore. i just solved it

The thanks for watching gives Vsauce vibes

way too many ads

10:21 And pi pops in out of nowhere. Again. (Actually, it doesn't. There is a circle in there somewhere.) Edit 10:31 Fair enough.

Why did you have to use "i" as one of the dots when talking about mathematics? It make it needlessly confusing seeing -i and i^2 when were not talking about the square root of -1. 🤦

Please…don’t use visual puns. Just because you say the word “pigeon hole principle” doesn’t mean you literally put a picture of a pigeon, and a hole…