Each point is connected to its closest neighbor, how many connections can a single point have (max)?
ฝัง
- เผยแพร่เมื่อ 30 พ.ค. 2023
- To try everything Brilliant has to offer-free-for a full 30 days, visit brilliant.org/ZachStar/ . The first 200 of you will get 20% off Brilliant's annual premium subscription.
STEMerch Store: stemerch.com/
►Follow me
Odysee: odysee.com/@ZachStar:0
Instagram: / zachstar
Twitter: / imzachstar
Support the Channel: / zachstar
PayPal(one time donation): www.paypal.me/ZachStarYT
Join this channel to get access to perks:
/ @zachstar
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:
Camera: amzn.to/2RivYu5
Mic: amzn.to/35bKiri
Tripod: amzn.to/2RgMTNL
►Check out my Amazon Store: www.amazon.com/shop/zachstar
It might be interesting generalize this to higher dimensions as well.
I suspect this even exists in the OEIS already.
It would also be interesting to apply this to other metrics
My first guess is that it'd always be at least 1 less than the kissing number for that dimension
seems related to the kissing number problem, which is unsolved already in 5D
@@leo.simensen I think it is exactly the kissing number for that dimension, unless that number is tight, in which case it's 1 less than the kissing number.
What’s the Kiss9ng number?
Zach Star: Political commentator on how everyone is a moron
Also Zach Star: Math Puzzle Efficianado
5 cause you can't have 6, and 7 is impossible
My bad accidentally replied instead of writing a normal comment
@@briangeer1024 did you know you can delete comments?
@@o5-1-formerlycalvinlucien60 eh I don't think it really matters in the end
Tried at the start doing it "my way":
I started with an unit circle, and started adding points onto it. And as this quickly ""aproximates"" a circle, I found that the "upper exclusive limit" is when the distance between points is equal to the distance from the centre, which immediately draws to mind an equilateral triangle, which draws a hexagon, giving the exclusive bound of 6 :D
I did the same thing for 6 my way :D
i did the same. i thought about it before watching the video so i didn't know about the "unique distance" rule, so i thought of using equilateral triangles to see how many would fit in a circular arrangement around a point.
and then i thought, okay, a circle is 360 degrees and the triangles are 60 degrees, so 360 divided by 60 is 7. got it. answer is 7.
i felt so smart. it's always the stupid arithmetic errors that get you.
Yeah this is exactly how it was for me. Before I clicked on the video I was thinking "it's 6" then he said that the distances are not equal, so I knew the answer was 5.
same here
although if i were to be a bit more accurate, the first thing i did was think of an equilateral triangle, and then from that i got a hexagon
I think it's impossible for me to now enjoy these math videos without thinking his voice is implying a ton of sarcasm. I know he's not, but my brain is telling me he is ahahaha. Keep up the good work Zach, love your content
The sketches have made it really hard for me to take his voice seriously. I keep expecting a joke.
@@alansmithee419 the entire time I was expecting to hear something like "PA < PB which also tells us that (PA + PB)*1000 < The amount of time you've spent with women"
If we only had TH-cam when I was in college in the 90’s. I was a mathematics major struggling with Real Analysis. I had to search thru the stacks at the library hoping I would find a book with a similar proof I was working on. Thank you Zach. Your applications are wonderful.
Its crazy how much high- quality content is present on youtube. Its such a great way to stay interested and learn overall
I thought about this similar to a sphere/circle packing problem so it's pretty easy to see that with 6 you would have everything be the same distance, whereas with 5 it's possible to not have the outside spheres/circles touching. Also works in higher dimensions
Awesome! Please do it in 3-dimensions also. Maybe even n-dimensions. Would love to see the analysis.
I knew when I saw the title of the video, it was gonna be 5. I've worked with hexagons enough to know that the center of a regular hexagon is the same distance away from each vertex as each vertex is to its edge neighbors. If the distances between each point must be unique, that rules out any hexagonal arrangement.
I know it's not a bulletproof proof, but that's how I figured this one out for myself.
I didn't understand please can you explain? I thought of infinity when he said an infinite plain
@@someone.-gi7zr Right, that is intentionally not very relevant.
The infinite plane is often invoked to basically free up the possibility space, from the kinds of strange and unhelpful restrictions that can come with trying to assign an arbitrary bounding space. An unbounded space means we can try anything - It does NOT mean anything in particular will actually WORK.
So, the proof - It's true that if we were just concerning ourselves with how many points a point could connect to generally, the answer would easily be infinity.
However, we have a very specific constraint here - Each point must connect, specifically and exclusively, to the point CLOSEST to itself. We can't just make arbitrary connections.
If that were the only constraint, a hexagonal arrangement, with a point representing the center of the hexagon, would allow us to get one point to have six connections. However, because that introduces some fuzzy arbitrary decision making, the "unique distance" constraint is added. This makes 6 impossible, but 5 is still achievable.
I want you to think about a hexagon - If need be, draw this out on a piece of paper - And really THINK about where you would put a point to go from six points connected to one, to seven.
Keep in mind, any new connection you make will potentially unmake other connections. That's the real trick here. If we put a point INSIDE the hexagon, we'll either connect it to the center and redirect one or more of our initial connections AWAY from the center, or we'll connect to one of the outer points, redirecting it away from the center.
If we put the point OUTSIDE the hexagon, then it will always connect to an outer point, again robbing the center of a connection. If we put two or more points far enough away, they connect to each other, and have no affect on the original arrangement at all.
I hope you see that even with infinite possibilities, by simply categorizing those possibilities and taking note of the properties of the CATEGORIES, we can do finite work to describe the infinite, and solve problems therein. There's an entire branch of mathematics all about that, but in this proof it's practically a tangential, hardly notable thing. At least, to a trained mathematician who's expecting this kind of infinite tomfoolery.
I encourage you to play around with this problem with paper and pencil - Get a feel for various arrangements, see what you can make of it.
Try the hexagon arrangement. Try interrupting it. Try a septagon and a pentagon. Try connecting some random points, by the rules described in the video.
You may find the process more enlightening and invigorating than simply being told about it :)
Btw, for those who wonder about the rule of all lengths being different. It's there to rule out the P=6 case which is ambiguous without the rule.
It's a poorly-posed puzzle because of that.
I'm actually really surprised that I used very similar logic to solve this, though my answer was wrong due to an oversight. I realized that p could never be connected to the hypotenuse. Unfortunately, I also couldn't visualize that without the angle being at least 90 degrees, so I got 4, forgot non right triangles existed.
I solved this one in 10 seconds by imagining first points on triangle, then square and finally pentagon while looking if the points would touch each other before touching center of the shape
sure you did buddy
@@uggupuggu try it, the method works
Another way of thinking about it is how many divisions of 360 deg can you have until the length of edges is less than the distance from the center. Defining it that way gives you a formula for the limit.
I'm pretty sure that the answer is unbounded on the hyperbolic plane, since it has so much more 'room'. The circumference of a circle scales like sinh r, so you could put literally seventy million points around the circumference of a circle with radius 20 and they'd each be more than 20 distant from each other.
yay, my intuition was right! From only the title, I had assumed 6, if same distance were allowed and thought of the unique length restriction and how it would remove 1 from my answer
I was thinking angles important at first. But then you mentioned the 60°, and realized YES. And immediately knew 5, when I initially thought 4 or 5
I only just started the video, but I'm fairly confident the answer is 5.
If you take a point and use as a shared vertex to make the maximum number of equilateral triangles, then placing a point on all the remaining vertexes gives 6 unique points around the initial point. However, since all distances must be unique, each radial point must be nudged such that the distance to their radial neighbors is greater than the distance to the center point. 3 points that are not neighbors to each other can be nudged inwards with no angle variation, but the remaining 3 points would be unable to be nudged such that their closest point is the center without making themselves the closest point to the adjacent points that were already nudged inwards.
If you remove one of the 6 points, and move the remaining 5 points at the vertexes of a regular pentagon with the initial point at it's center, you can nudge each of the 5 points by a small, unique distance, and then you'll have satisfied the conditions.
I was bingewatching you like 2 hours ago, then you upload!
Holy shit, good video!
It's very interesting that I quickly deduced that the answer was 5 because 6+ the points would be too close to each other to connect to the center, but didn't know the proofs to back it up. Neat!
Math used to never resonate with me until your videos explained it in a digestible way
Very interesting stuff!
right i also think about the hexagon so the max amount of neighbours is 6, where distance of points are equal. If you move a vertex of hexagon, either it becomes closer to center or to next vertex
I would say 5 or 6 (with 6 being the edge case where you would have to decide how to define the question), because at 6 you have a hexagon surrounding a middle point, with two adjacent corners and the middle point forming equilateral triangles. Any more corners and the distance between them will shrink below the radius of the circle on which the corners are placed around the middle point.
Ah, a unique distance.
5 then.
An answer is ambigous, if you have a regular hexagon, then all distances are equal between edge nodes and also between the central node and edges. So if we start counting from the central node then it would have 6 connections. To remove this ambiguity you need to introduce the condition that, for example, no two distances are the same (a bit of overkill)
Well, that no two distances are the same was a given. So, you cannot have regular hexagon.
@@AbiGail-ok7fc Probably answered from the title. It was a pretty obvious solution if you know what a regular hexagon is. The "distances must be unique" was only mentioned a minute or so into the video.
this felt pretty straight forward with no fancy math, took like 15 seconds
"3 points all equal distance? equalateral triangle"
"how many of those can tile without overlapping around the central point? 6"
"for it to differentiate closest points the distances can't be equal aka has to be slightly wider than an equalateral triangle, max 5 can fit"
Such an awesome solution 👌
I thpught about it like this
In a regular hexagon the side length and longest radius are equal. If p is the center of that hexagon, there are equal distances, so you have to move the center point, but then the side lengths will be greater that the distance from the other points to p, which will break the connections
In a pentagon that is not a problem, so the maximum number of connections is 5
I assumed the solution would depend on the total number of points that were in the graph, like "n-2" or something. But as soon as he transitioned from "AB must be the longest line in the triangle" to "the corresponding angle must be the largest angle", I *immediately* realized the solution was a hard 5, he hadn't even mentioned that the angle had to be greater than 60 yet.
Very elegant to identify the triangle inequality and apply it!
5 (in 2D euclidian geometry) - now I'll watch the video and see if I am right.
I agree and am doing the same.
[Edited to add] Yay! :)
in the multidimensional latent space for the Zach Star Mathematical Cinematic Universe (MCU), this video's closest neighbors would probably be the disk covering video and Putnam one from a while back
I got this right intuitively! I feel pretty good about that.
Same... 6 connection points would mean that all points are equally far from each other. But since the center one only connects to the closest is must be less than 6, thus 5
Have you ever examined your Myers-Briggs? I’ve been curious as to where most engineers land on the Myers-Briggs
Coincidentally I was just doing something like this a few months ago with NFL stadiums. The resulting graph was not even close to what I expected to see when I started thinking about it.
This ends up being a "circle". Basically how many points can you fit around a central point such that the distance between the outside points is larger than the distance from any outside point to the center.
Looked at the thumbnail and just assumed you could have infinity before the explanation. Once he drew AB above P I shortly realised it was 5. Well, very well, I have two other ideas:
1. Go to hyperbolic space and start drawing points an arbitrarily large distance away from P
2. Go to Hilbert space and just repeatedly add progressively closer nodes to P on every axis
There is an utmost limit based on ((n-2)180)/n=120.
This makes n 6. Any more than that many connections would block further connections by not having equilateral triangles. Given unique shortest distances, 5 becomes the most.
Figured this one out in my head, without all the geometric proofs. Six-doesn't-work and five-does-work are actually rather intuitive.
I got the same answer from a completely different thought process: each point has a circle with it as it's center and the closest point as the point on its edge, such that no circle can have points inside of them. Therefore because the maximum number of points on a circle can be is 6 (hexagons) , and the parameters of the "world" dictates no two distances are the same, the maximum number must be less than 6: 5
I think that the arguments would be simplified a bit if you say that given any three points, out of the three distances between them, whichever one is longest, that one cannot be an edge of the graph. (This is because, for each of the two points it would join, the distance to the third point is shorter.) This immediately tells you that there are no triangles, but it can also be applied directly at 3:30 without having to go through the no-triangles lemma. (And anything with a negation in it has the potential to trip people up, so it's best to say this about a simple edge rather than a while triangle, when you can.)
Zach, could you revisit this question, but on a spherical surface? This seems like a pretty good exercise for transportation routes, or at least a simplified model.
On a spherical surface (or more in general anywhere the curvature of the surface is positive) you get the same result as on a flat surface (max 5 lines) as long as your points are “close enough” to each other.
On a hyperbolic surface (constant negative curvature), on the other hand, you can have as many lines you wish connecting to the central point, provided the points are sufficiently distant from each other.
My guess: 7 circles can be packed into a hexagon with equal spacing, so... maybe 5 to break up the equality? I feel like it would have to be arranged like a spiral around the central point.
Reaction: Interesting, so I was close, but I didn't think of it in terms of angles. So the spiral isn't actually a requirement in that case.
This was exactly how I thought through the problem when I saw the title
Somehow seems related to the six degrees of separation concept.. though I guess it's just a lot of coincidentally similar variables...
with a hexagon with a pint in the middle the middle point would have 6 connections. any other points would rather connect to the outside 6 or would break established connections. in a hexagon the outside points are the same distance to their neighbors as to the center point. in a polygon with more sides the outside points would rather connect to their neighbors than to the center point because they’re closer. because equal distanced points are not allowed the most points possible are 5
Commenting before I watch: I'd think the answer would be 5 since a regular hexagon in 2d is where all surrounding points are equidistant from another point and the main point in the center.
I am curious; how do things change if this puzzle occurs in a non-Euclidean environment? How do things pan out in spherical space? Hyperbolic space? Or in space so irregular that *any* set of distances between each pair of points is valid (for example, AB = 1, BC = 2, AC = 8)?
Or perhaps, what happens in an environment with more than 2 dimensions? Surely you can get more connections in three dimensions. Even more in four.
I think I missed the step that showd why side AB being the longest makes the angle 60°. Where does 60° come from here? Intuitively it makes sense give. The geometry of hexagonal or tiranvular tilings of the plane but I don't see how it follows from the argument layed out here
"There cannot be triangles"
Laughs in equilateral triangles
I have a neighboring question. Given a cloud of N points, the number C of connected components in the graph of “find my closest neighbor” ranges from 1 (line configuration) to N/2 (row of vertical pairs). However, what can we say about the statistical distribution of C in relation to that of the points ?
Thanks
This is so freaking cool. I clicked this from recommendation.
Based on intuition I figured 6 connections would be an upper limit. A single point surrounded by 6 evenly spaced points would create 6 equilateral triangles, and any more points would cause the outer points to be closer to each other than the center.
However, since the problem specifies unique distances, increasing the distance of any of the 6 points from the center would also cause the outer points to become closer to each other, given a 60° angle between them. Therefore, I believe 5 connections would be the most, with each outer point at a slightly different distance from the center point.
My reasoning: If you put x points around a single central point (which is where you try to get as many connections as possible), then if x is greater than 6, they are closer to each other than to the central point. At 6 (where they form a hexagon, or alternatively six triangles with the central point being the node), they are equally close to each other, and to the central point. At less than 6, they are closer to the central point than to each other. As no two distances can be identical, the 6-line option is not valid. Therefore, the correct answer is 5.
This is similar to how your units in Mechabellum select their targets
I solved it this way: draw a circle around P. the distance between the points on the circle must be more than the radius of the circle, otherwise they would connect. Then look at the conversion to radians and you can fit 6 points. With slight permutation of the distances you fit the "no same length" rule. I had no way of proving this solution is unique tho
i guessed 7 points in a spiral shape, where each next point is further away from P
A problem i find here, what if 2 points are equal distance from a point? Like the hexagon.
Wouldnt the answear be an line in form of a circle around a point, infinite points all the same distance away from origo
Before the video goes im gonna put my guess and reasoning
So if its the shortest edge that connects that means nothing smaller than an isometric triangles could be formed from the points since all points are the same distance away in an isometrictriangle, however any triangle with one angle wider than 60° would have at least one edge longer than the other 2 which means any number of of trangles could be formed as long as no single triangle has a center angle of 60° 360/60 is 6 which is all isometric triangles so 5 points would be the maximum before it would all be the same distance away
Somehow my brain immediately knew the answer was 5. I thought, if it was 7, then others would be closest to others, but for 6 every adjacent point could be equal from each other, but equal is illegal, so 5
I'm curious why you conclude 5 instead of 6. The sixth roots of unity for example are all 1 unit apart and 1 unit from the origin, so the origin would have 6 connections. I guess I interpreted the prompt as "Each point is connected to its closest neighbor(s)" since that covers every case where "connected to its closest neighbor" fails when 2 points are equidistant to the third.
The first assumption was that all the distances were unique
Where am I flawed? A triangle is possible... it's called an isosceles triangle (2 equal sides).... Therefore Max connections for P is infinite, Have a circle of dots all equal distance from the origin dot P. Shortest connection for P is to all of them.
No two points are allowed to have the same distance as a different set of points
I enjoyed that
This might sound dumb, but why isn't a triangle possible with the problem, with isosceles or equilateral triangles? Since the distance of two or more sides are equal, and two points are the same distance away, such as an isosceles triangle with lengths 5,2,5 or a equilateral triangle with lengths 3,3,3?
I knew hexagons were going to be important, so my first guess was 6.
You could form a triangle if each side is the same length
there can't be same length thus no
Is it not that the maximum connection a point can have is infinite, if multiple points are the closest? Such that the point is simply the middle point of a circle and the other points are on the line of the circle.
Let’s say you had a system made only of points connected to the single point no matter how much you increase the distance if you don’t change the angle at which the two lines connected to the center form you will not change the connections therefore the maximum number of points would be equal to the maximum number of points on a perfect polygon with points inscribed around a circle centered at the point which we want to max the amount of connections to in which the radius is less than the length of each side which is 6 however due to the fact each set of points has to be equal to each other it would need to be 5 because this rule is broken if it is 6
What about 3 points forming an equilateral triangle? Which points would you connect?
Watch the videos beginning again pls
you can't because the premise is that all the distances within the graph are different
We aren't quite able to do that, since at the start of the video he specifies that the distances are all unique. However, if we throw that constraint away, then we can sneak in a 6th point and make a regular hexagon by using similar reasoning to the video.
I took an easier way. I remember that the regular hexagon is formed of equilateral triangles, which means that the length of the lines that connect the central point and vertexes is the same as the lengh of the lines that connects those vertexes. That means that 6 is the borderline and less than that can work for our situation which means the answer is 5. Idk if it's rigorous enough but seems like a nice solution.
To use this though you would need to prove that a hexagon is comprised of equilateral triangles. To prove that would probably look a bit like the proof in the video which uses more geometric primitives
Could we add another 5 points? Closer to the centre point then the outer points?
Like if the radius of the initial circle is 5, at 2.4999..?
So we will have the degree 10.
Edit- the distances are different, say by 0.01
Now i know how snow work :)
4:39 Why not? A is the closest to P, P is the closest to B, and B is the closest to this other point.
Just by feeling it out a bit I think it’s 8? Just my gut feeling
Yes! I managed to reason my way to the correct answer
Graph theory is one of those surprisingly interesting field that has applications everywhere. Nice video.
That's not graph theory, that's geometry.
Equilateral triangles. 'Nuff said.
this was uploaded while I was in school.
Nice, now do this in 3d
So confused to discover the guy who does wacky zany skits is the same guy talking about interesting maths puzzles.
giving it a go: in a hexagon of sidelength 1,the distance between the corners and the center is less than 1 ( sqrt(3) /2 i think?) but for 7 its more than 1, so 6 (inverse? :D ) closest neighbours to a single point
ah yeah, math mistake, sorry :D i dont know why i remember sqrt(3)/2 for hexagons
1:21 Trying to make a triangle is the same as AB > BC > CA > AB, which is a contradiction.
Great exam question, lol
My best guess before I watch is < 3.14 connections
Ok but what happens when P is equidistant from every other point? As in every point on the graph is along a circle with its circumcenter at P.
If every point connects to its closest neighbor, that must mean that either every point chooses another point at random if there's two with the same distance from itself meaning the maximum is still 5 points, OR it chooses BOTH equidistant points, meaning that the maximum connections is infinite so long as every other point maintains equal distance from the infinitely connected central point.
He stated in the beginning of the video that all distances between points are unique. There are no equidistant points
Fun fact:
The answer would be infinity on a non-euclidean plane.
5 is incorrect. Right answer is 6. Regular hexagon with point in center, each corner has shortest distance to center. Of course same distance to adjacent corner, but choosing the center point gives the maximum.
I'd expect 5 or 6
Isn't this a question from IGMO 2020 or 21? I have had proved it using circles and not inequalities 🤔
Can you cover Animation vs Math?
My first guess was 3 because _mumble mumble_ π, or 6 because _mumble mumble_ τ.
Oh damn I didn’t know this comedian was also a mathematician
You sound like the guy that always plays as god on that one comedy channel
What about N dimensionnal version of this then ?
Trying without watching the video, the limit will be when a chord of a circle between two points on the boundary is less than the radius, which napkin math doesn't give an easy answer with my skill
.... this feels like a 10 second problem
Meanwhile me spending minutes to solve it with the law of cosine instead of realizing that omega is the greatest angle 🤣🤣
5, cuz hexagon -1 point as they can't be the same distance.
Sneaky of you to assume a Euclidean plane.
make equilateral triangle
I still dont understand where you got 60 degrees. Cant you just put A on PB, but just closer to P?