Next video (on Odysee): https://odysee.com/@ZachStar:0/max-distance-puzzle:f
My Odysee Channel: https://odysee.com/@ZachStar:0
STEMerch Store: https://stemerch.com/
?Follow me
Odysee: https://odysee.com/@ZachStar:0
Instagram: https://www.instagram.com/zachstar/
Twitter: https://twitter.com/ImZachStar
Support the Channel: https://www.patreon.com/zachstar
PayPal(one time donation): https://www.paypal.me/ZachStarYT
Join this channel to get access to perks:
https://www.youtube.com/channel/UCpCSAcbqs-sjEVfk_hMfY9w/join
2D Graphing Software: https://www.desmos.com/calculator
Animations: Arkam Khan (For contact info go to https://www.arqum333.com/)
Check out my Spanish channel here: https://www.youtube.com/channel/UCnkNu2xQBLASpj6cKC8vtpA
?My Setup:
Camera: https://amzn.to/2RivYu5
Mic: https://amzn.to/35bKiri
Tripod: https://amzn.to/2RgMTNL
?Check out my Amazon Store: https://www.amazon.com/shop/zachstar
Also, the second puzzle is very interesting - might take a shot at that one too!
@siddharthkorivi5537 Says:
My proof is similar, but it deviates after you drew a quadrilateral. First, you need to realise that if you were to have half of the four points labelled one thing and the other half of the total points another thing, then you can ALWAYS connect one of label A and another of label B for both As and Bs without any intersection. But this part only talks about quadrilateral, so I will now prove that it works for any even sided shape. Next, add another A and B pair (from now on I will abbreviate these pairs as AABs). What you must realise is that, if it intersects one of the lines again, you can simply do the quadrilateral trick again. It must be noted that even if, from a group of intersections, you can produce a hexagon or any other shape, you MUST start with a quadrilateral and include the other pairs of points with more quadrilateral. This proof is (I think) correct.
By the way, if this proof is correct then this question absolutely does not deserve to be in the Putnam exam. After all, I'm just a 12 year old who didn't even get over 100 on the JMC.
@harshilagarwal6295 Says:
Proving by mathematical induction🗿
@subhoghosal7 Says:
@ZechStar I have a objection with this proof. The manipulation that has been shown frees a cross by creating two noncrossing edges. But if n>4, this may introduce new crosses with other existing noncrossing edges. Even if we try to say that we would apply the algorithm on those edges recursively, it does not guarantee that on some step of recursion, we would not end up reintroducing the first cross.
@selby545 Says:
xd
@getnopeace Says:
it's weird seeing Zach do anything other than comedy sketches
@quiggaxx Says:
The end question confused me at first because I didn't see the asterisk pop up saying "or equal to" so naturally in my head I was saying "this can obviously be done ! If I arrange 4 points in a perfect square then I'll have 4 pairs at the max distance !" . Should've known that was too easy to be overlooked lol glad I went back and watched it again and saw the equal to asterisk .
@agrajyadav2951 Says:
Proof is that quadrilaterals exist
@gaborszucs2788 Says:
Well, I guess the exact problem description has some extra condition which is not mentioned in the video. Think about the special case of ABCD being collinear, in this order, with AB being red and CD being blue. Technically, two lines that have a common segment (BC) are considered intersecting, and if you swap the ends, the distance doesn't decrease, and BC will remain a common segment as well.
@sebastiana.345 Says:
Bro I found this channel second and the whole time I just think of you being god and being like oh my
@mcwolfbeast Says:
Does this even hold true when the distribution of the points is extremely uneven, i.e. most of the red points are on one side and most of the blue points are on the other? Or of there's clustering of points on either or both sides?
@StephenKarl_Integral Says:
What if you have 4 points, two red and two blue, reds are on the left, blue on the right, and all four points are colinear...
^^ just nitpicking... but that's the first picture that came to my mind when reading the title before watching the video, was more interested in finding an answer to the question than attempting to solve the broad case where there is no colinearity.
@andreujuanc Says:
This is mind-blasting
@Dziaji Says:
I’m going with “yes”
@triffinne Says:
Doesn't this rely on the assumption that the points aren't all in a line like "R R B B" which would be impossible to solve? Or is it that the two line segements are completely overlapping and is different from an intersection?
@lsora12 Says:
Hello. Do you do all the animations in desmos? I want to build up a channel of classic geometry and I wanted to know
@raismin739 Says:
it's not always possible tho... if you put in the same line 3 red dots and then 2 blue dots and the blue dot wherever you want, you notic that is not possible to not intersect. if you generalize with 2 dots (indistinguable from each others) then it's always possible to do it
@Orenotter Says:
That seemed to include unnecessary steps. All you had to say was that intersecting lines can be considered the diagonals of a quadrilateral, and that they can be replaced with two sides of the same quadrilateral. No need for lists or lengths.
@jonwatte4293 Says:
I imagine there's an alternative solution that's constructive, essentially doing ear clipping on the convex hull, as an alternative.
@evannibbe9375 Says:
You could also use the triangle side inequality to determine, given that the longest side of the triangle is the intersection line (when triangulating using the longest pairing line).
@kosterix123 Says:
Two trapezoids can overlap or intersect and what can happen is by switching from diagonals to sides you get another intersection.
Also, you’re assuming there exists such a minimal P.
Either your proof is too short and incomplete or I’m just too dumb to see the triviality.
@asterpw Says:
Cool video and didn't know there was so much support for Odyssey! It's great to have a YouTube alternative.
@arondaftari9427 Says:
Ok Just a question but what if there are 2 sets, both of witch fall on the same axis and such as if a line where to be drawn through any set it would pass through a starting point of another set. I understand that this would effectivly make it a line rather than a plane but lines can exsist in planes.
@Maric18 Says:
my solution was incomplete, i got the "you can resolve a crossing by switching to the outer lines of the quadrangle formed between the points" (without looking at the length) and then declared myself done, because "well it probably can resolve all the cases, even if it produces some new ones" xD been a while since i did math but im still half proud xD
@gianlucatartaro1335 Says:
0:33 Wow, so we can’t let points of the same color get together? That’s very homochromophobic of you, Zach. Some points are just made to want to be paired with points of the same color. Zach also has problems with points pairing with more than one other point? What’s next, he has issues with points changing colors??? We live in 2022. For shame, Zach.
@aPictureElement Says:
The way I solved the problem is that you first number the red dots 1, 2, 3...n from left to right. Then you number the blue dots separately 1, 2, 3...n again form left to right. Now simple connect the Red1 dot to Blue1, Red2 to Blue2 and so on.
I think this solution will work for every n but I don't know how to prove it.
@syzygy6 Says:
checked out odysee and it was overflowing with weird far-right propaganda. i’ll pass.
@Rolancito Says:
I think you can extend this for more colors. Given the same number of green, red and blue points on a plane , no three collinear, show that you can draw triangles with vertices of different colors such that the sides of any two triangles do not intersect
@cowabunka Says:
absolutely beautiful
@Raye938 Says:
Thanks for mentioning Odysee, I wasn't aware it existed and I wanted to move away from Youtube.
@MegaKotai Says:
At 3:32 we need to keep in mind, that our points are colinear. Otherwise the triangle inequality would have a greater or equal instead of strict greater and therfore the length doesn't have to decrease if we swap the connections. (imagine 4 points all on one line, first 2 red and then 2 blue. No matter how we connect them the total length is the same)
@jacksonbittner9337 Says:
Really doesn't work if all of the points, or even a significant number of points exist on a line
@DrMewFoxov Says:
What if I order them in such a way that all points are in one line - three red points on the left and three blue points on the right?
@Soandnb Says:
I suppose you could beat this problem if all points were miraculously placed in a perfectly straight line without any deviancy from any of them. If the points are Blue - Blue - Red - Red, then there would be no way to place the lines in a way that would prevent at least some part of the line from "intersecting" with the other line. Though I don't know if intersect is the right word since fragments of both lines occupy the same "space", as it were.
@konstantinkh Says:
I don't think I would have solved this if I wasn't aware of a related algorithm for Delaunay triangulation. Uncrossing a pair of pairings seems like a move in the right direction, just like in Delaunay, and it's just a matter of proving that you always make progress with each pair you uncross. Having some sort of a net quantity that monotonically increases or decreases is always a good thing to look for, and obviously, the sum length was the first thing that came to mind. I didn't bother with ordered list, just the fact that there is a finite set of permutations, that swapping the pairing on an intersection decreases the sum length, and that there's always a permutation with a smaller length if there's at least one crossing guarantees that a solution exists and you get the algorithm as a bonus. Neat problem. Good video.
@hgu123454321 Says:
I'd be interested in seeing more videos about these kind of approximations of NP-hard problems. There are plenty of videos about NP-hard problems and why they are hard, but I haven't seen so many about the 'pretty good' solutions that get you within a certain distance of the perfect solution. For example, in this case, we know if you keep applying the 'no crossings' rule, you will end up in the upper part of the list, but how close to P1 are you guaranteed to get?
@DukesAPG Says:
One of my friends in high school did his senior computer tech lab on programming a solution to this problem for any randomly generated set of dots. Because we were in high school, we referred to this as the Ghostbuster problem. Think of the red dots as ghosts and the blue dots as ghostbusters (or vice versa), remember you can't cross the streams, and see if you can eliminate all the ghosts in one shot per ghostbuster.
@theCJoe Says:
MaybeI misunderstood the second question, but isn’t it trivial? No line is longer than 1, so all are smaller or equal to one, so the number of lines equal to one is at maximum the number of all lines. Or did i get this wrong???
@theaureliasys6362 Says:
Funny thing is, this problem is trivial with knowledge how to trivialize social cases of the traveling salesman problem.
Any crossing path is subpar, replace by making the other connections.
And since there are stictly less connections here:
Possible.
@majorjohnson8001 Says:
Bonus question:
The only way set m can get bigger than 1, is if all of the points in set comprising m all lie on the perimeter of a circle of radius one half. Any other points in the whole set must lie within that circle. There cannot be points outside that circle, because if there were, there would be a pairing with a length greater than one (and those points would be the set m, rather than the assumed set m).
m=0 only occurs if n=1.
@pelimies1818 Says:
Sure.
Make dashed lines.
@havenbastion Says:
No. On a line you can easily get at least one point of a given color not being able to see a dot of another color. In two dimensions it's less likely but entirely possible. A circle of blue dots with a blue dot in the center and all the red dots behind an external blue dot from the central blue dot is a configuration which does not allow connecting the center blue dot to a red dot.
In three dimensions it's again less likely but entirely possible, using the same configuration as above but with a sphere rather than a circle.
@TheGraemeEvans Says:
So 2 red points followed by 2 blue points in a line doesn't count as an intersection? Eg red points at (1,1) (1,2) then blue points at (1,4) (1,5)
@hooby_9066 Says:
Something seems to be missing from that explanation.
The proof as explained only shows that when *four* points are in two pairs with intersecting lines, you can resolve that one intersection. But is entirely possible, that - for example when you have 6 points in 3 pairs - a new intersection is introduced.
You could of course repeat the process - but doing so could introduce yet another intersection. The important part here is, that every time you do repeat the process, the total length decreases - thus it is impossible to ever get into a loop - because you can never return to a previous configuration - as that would have a greater total length.
So no matter how often resolving one intersection introduces a new one, and no matter how often you have to repeat the process - the amount of possible pairings is finite, and since you never repeat, you must eventually get to the shortest total length. And that shortest total length can't have an intersection, since because if it did, yet another, still shorter configuration would have to exist.
@somniad Says:
Computer scientist, immediately came up with the line uncrossing but had no idea how to prove it lol. Funny what thinking about algorithms too long does to a brain.
@sleekweasel Says:
Interesting problem. It would have been good to briefly discuss how we know that although changing the diagonals for edges might cause two segments to become crossed, it's not possible for that to happen indefinitely.
@finsflexin Says:
No thanks, I would rather shoot my toe.
@Obikin89 Says:
Easy : align 4 dots, 2 red then 2 blue, and that's it : they will intersect. PS : didn't watch before I answered but I guess i broke your logic... And they won't just intersect at a single point but on the whole line between the two closest points... And you can add as many points as you want on the line as long as the blue ones are on one side and the red ones on the other... And all of the junctions will intersect on a portion of the line. "In Euclidean geometry, the intersection of a line and a line can be the empty set, a point, or a line." Guess I win !
@randompast Says:
Really elegant proof, thanks for sharing! Definitely do more of this!
@Buglin_Burger7878 Says:
This feels like the equivalent of titling "How can the boat avoid land?"
Then removing the land and all possible fail states so it by default wins and changes the initial question to:
"If there is no fail state will it always work?"
In other words a video like this is more of a "Why" and less of a "Yes/No"
LATEST COMMENTS