Can you always pair an equal number of red and blue points with no intersection? 

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.

101 people participate in a duel as follows. They will be placed on a flat, open area and each person will simultaneously shoot the person closest to them. (It will be ensured that for each person, the distance to the 100 others will be all different so there will be no ambiguity about who is closest.) Prove that for any configuration, at least one person will survive the duel.

In layman: If there's an intersection, just swap connections to get rid it. So keep doing that until there's none left. There must be an end because total length gets shorter each time.

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)

Zach you're fantastic man , i have watched almost all of your videos and now im gonna dominate the world...

There a dissertation by a guy called Rieger talking about the generalised (cyclic) monotonicity of optimal transport flows which is basically what you are minimising here. He shows that the optimum is always a monotonic flow for ground costs/distances of a certain kind (those which for any four points, the sum of cross distances is higher than the direct distances). Basically, cyclic monotonicity amounts to irrotationality/no twisting/no crossing, so since you know the optimal OT solution (for the right ground cost) is going to get you the right kind of matching, you know you can just look for a minimum OT cost solution.

"We will be ordering the configurations by total length of the line segments" - this was the point when I saw the solution.

Really elegant proof, thanks for sharing! Definitely do more of this!

Super fun problem! I sort of thought initially about switching any intersection pairing, but I definitely lacked any immediate robust logic for the proof of the concept! Great editing as always Zach, keep on uploading!

The fact that this is the same guy that has Zach Star himself is insane to me. Honestly just haven't met very many guys who are both really smart and really funny.

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 !

For the end puzzle, I solved it by thinking about adding points one at a time. Each time we add a point also draw the unit circle around it, so the intersection of the circles shows the region where points can go. Also, only consider points that are at the max distance from one of the existing points, so we can only add points on the edge of the region. The valid region will be like an inflated polygon, with vertices connected by edges which are arcs. The first point gives us no pairs, and the valid region is a circle with one edge and zero vertices. The second point pairs with the first, and the valid region now has two edges and two vertices. These vertices do not contain points from our set, so I will call them unoccupied. From here three things can happen depending on where we place new points: - Points placed on an edge between two existing points add a single pair with the point that generated that edge. The valid region is not affected. - Points placed on an edge between an existing point and an unoccupied vertex add a single pair with the point that generated that edge, call it P. The circle from the new point will shrink the valid region, cutting off the opposite unoccupied vertex and replacing it with an edge and two new vertices. One of the new vertices will be occupied by point P while the other will be unoccupied, so the number of unoccupied vertices is unchanged. - Points placed on an unoccupied vertex add two pairs, since they are on two different circles. The opposite unoccupied vertex will once again be cut off, but now it will be replaced with an edge between the two points that generated this vertex. At this point there are no more unoccupied vertices, so any further points can only be added to edges. The total number of pairs is one for each point placed on an edge, plus zero for the initial point and possibly two for placing a point at a vertex but that can only happen once. So the number of pairs is either equal to or one less than the number of points. It is also possible to have multiple disconnected groups of max-distance points, for example a square with diagonals of length 1. For these we can just use my argument above for each connected group separately and add the results. Finally, we can have extra points in the middle which aren't at the max distance from any other points, but that just adds more points without adding more pairs so the inequality still holds.

In discrete differential geometry there's something called the Laplace-beltrami operator (i think that's the one - i need to check) used in geometry optimization, that basically says when you have two lines that cross you can always redraw those into a more optimum configuration. That would be a theorem that covers this and applies to curved surfaces and higher dimensions.

This is mind-blasting

I was asking myself this exact problem a few days ago, and that answer is so straightforward.

Zack man i was waiting for your videos for months

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?

Another solution. Take a point M inside a convex hull and not lying on any line between two of our points. Draw a line through M and consider one of the half-planes and the difference #red-#blue in this half-plane. As we rotate the line through M, the difference changes by one every time the line passes one of the red/blue point. When the line has been turned by 180 degrees, we arrive at the difference that is minus the initial one. Hence at some moment the difference is zero: on each side of the line the number of reds equals the number of blues. Then if we solve the problem for two (smaller) sets of points on each side of the line, the union of these solutions is a solution for the initial set of points.

Also I'm glad you're on Odysee. I just made an account for that so that works out! I'm gonna subscribe to you there.

Was suprised that this is the funny youtube skit guy. Was EVEN MORE suprised when I noticed that I've already been subscribed to this channel for a long time without knowing that this is the funny youtube skit guy. Thanks Zach for making both educational as well as entertaining content of the highest quality for all these years. ^^

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.

I immediately went into the fact that you can always bisect the plane into two parts with the same number of points since no 3 points are collinear. Judiciously choosing the bisection, we can always get either maximally one coloured on one side or maximally evenly split between both sides. If we get a pair of sections where each side has only one colour, we can pairwise link up each point from these two sections and we're done. Otherwise, we then invoke recursion and bisect each section into subsections and repeat. Eventually we will get to the subsections of only one point on each side where each side is a different colour, and therefore you can pair them up without overlapping the line with any other line.

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

Solution to the problem at the end [some details skimmed over]? -Consider the counterexample with the minimal number of points. -We prove that any 2 maximum distance segments must intersect (possibly including an endpoint): - If all endpoints are on the convex hull, we use the fact that the sum of the diagonals of a quadrilateral must add to more than the sums of 2 opposite sides, so one of the diagonals must be greater than the max distance. -On the other hand if say our segments AB and CD say are such that A is inside the triangle BCD, let E be the foot of the perpendicular from B to CD and at least one of C and D (say C) has BA. -For a counterexample to exist, some point A must be the endpoint of at least 3 segments AB, AC, AD say. (The total number of endpoints is twice the number of segments, which is more than twice the number of points). -At least one of these points (B,say) is such that C and D are on the opposite sides of the line AB. No other segment of endpoint B can intersect both the segments AC and AD, so AB is the only segment with endpoint B. -The same configuration without the point B and without the segment AB forms a smaller counterexample, violating our assumption of minimality.

Also, the second puzzle is very interesting - might take a shot at that one too!

One thing that does not seem to be answered by the proof is what happens if the new pairing causes intersections with OTHER lines? It is possible that new configuration simply cycles with the original one, with both configurations having intersections.

absolutely beautiful

proof by reasoning: so, take the simplest crossing: the 2x2 there isn't a way you can have it cross with checkerboarded reds&blues, so there has to be a red side and a blue side. in this case, you can have the red side and blue side connect the other way, (can't really explain with words, so here's a diagram.) r--b r--b instead of, r\/b r/\b so you can add in more pairs and see that there come more of these 2x2 areas, which are all solvable. if you find something that proves me wrong, type in a reply.

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"

Really nice, I enjoyed the video.

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.

I imagine there's an alternative solution that's constructive, essentially doing ear clipping on the convex hull, as an alternative.

You can easily find at least a configuration that does not allow to link red and blue. Put all the points on a line, and label them as RRBB. Then, it is easy to see that you can never link all red and blue without intersections.

holy fuck i was uniquely prepared to solve this problem. i got it in like 2 seconds! that felt amazing after such a stressful week.

Found this through your skits channel and I am unable to hear your voice without feeling like there's gonna be something funny coming up

I love that you give us a non youtube alternative.

Odysee huh! Appreciate to hear that. Also, didn’t know how many other channels were on there.

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 .

Can you do the same thing with sentence structures? Words being blue, spaces being red? Important to note there's always one fewer space than there is words, but one might sub punctuation for the required/missing space! Cheers!

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

What if there are 4 points total, and they are all on a line, with the 2 blue on one side, and the 2 red on the other side?

Sure, just take the shortest set of lines connecting red to blue.

Points in plane can by chance arrange in a way that they are all on the same line and all red and all blue bots are all sequential thus making them impossible to pair without going over the previous line. That proves that you can not allways match them

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

Could you do a video about electronics engineering and also the difference between electrical please

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.

My thought before watching: connect randomly, then if lines intersect, take the points they're on and connect them so the lines are pararell, then repeat the process till there are no crossing lines left.

Supercool, I love this!!

Sure. Make dashed lines.

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.

That's so cool. I didn't watch that other video so I couldn't guess :)

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.

Cool video and didn't know there was so much support for Odyssey! It's great to have a RU-vid alternative.

Hello. Do you do all the animations in desmos? I want to build up a channel of classic geometry and I wanted to know

It literally took me 2 seconds to think of an example where they can't pair without overlapping.

I’m going with “yes”

Bro I found this channel second and the whole time I just think of you being god and being like oh my

that's amazing

0:19 Thought about it for a bit, what about the case where you have your dots constrained to a line, 2 red dots followed by 2 blue dots? -----R-----R----------B-------B------ Red must connect to blue. The inner red and blue connect. But the outer red and blue must "intersect" The alternative is first red connects to first blue and second red to second blue, but they still "intersect" Could go a step further with that configuration and have 2 of those parallel: -----R-----R----------B-------B------ -----R-----R----------B-------B------ There is no other case I can think of to allow connecting them such that no lines intersect.

I did actually see that you could "untwist" intersections but didn't realise that that could be extended to a full proof. Also, I now think that if you started with a random field of points and paired those up randomly, then progressively untwisted them (also in random order) you would eventually arrive at a P that had no intersections, but there's no guarantee that you'd have the shortest possible length of lines (no guarantee you're at P1)

I watched Mathologer's shoelace video recently, so I immediately knew the argument.

The pairing corresponding to the optimal transport map w.r.t. squared Euclidean distance has this property, because of cyclical monotonicity. Done.

Once you mentioned the lengths of the lines everything snapped into place.

make a line... reds on one side blues on the other

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.

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?

Zach is back!

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.

it's weird seeing Zach do anything other than comedy sketches

I think this may be wrong the top most configuration could be choosing from 2 intersection Or in other words some points may require intersection to be connected ??!

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.

I always just thought he was zach star himself

You don't really need the list, you can just say that there are finitely many connectivities, thus infinite decent is impossible.

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.

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?

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.

The last inequality doesnt hold always, its quite simple geometrically. Lets say we have n points. Starting from n= 1, it always holds, n =2 always holds, n = 3 always holds. This is because no matter If you make an equilateral triangle(the case that would have most possible pairs) you would still have 3 pairs and 3 points. But from n = 4 there would always be at least one configuration would not satisfy that. Because you always can add one point so that it forms an equilateral triangle triangle with two previous points. Effectively adding 2 new pairs and only one point. So if you had the case the 3 first points form an equilateral triangle, 3 pairs and 3 points basically you would have 5 pairs and 4 points forming a new equilateral triangle. Is there more configurations than those? for n = 4 there isnt because the only case that has 3 points and 3 pairs is the equilateral triangle case. And the number of combinations you have with 3 points is 3. You cant get more than 3 pairs. After that you can add at least 2 new pairs per point, in many ways you could add more than just two like adding more than one equilateral triangle at a time but that requires specific configurations. At n = 6 you would have infinite configurations just form because given the case with most pairs at n = 5 would be 7. (basically the max quantity of pairs is 3+ 2*(n-3) at least for an small n else you could have more) So you have an extra point to put wherever you want and still would be 6 points and 7 pairs or 8.

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.

So how would I go about proving that if two lines cross there is going to be two sides of the corresponding quadrilateral that satisfies the original condition?

Recursively flip any case where beams intersect (flip blue to blue for example) The process is garanteed to end because each flip will shorten both beams (see: pythagoras. the sum of the diagonals of a quadrilateral are greater than the sum of any 2 opposing edge). The only case in which you could indefinitely keep shrinking beams without moving points is where you have points infinitely close to each other, in which case the problem is undefined. saved you 7 minutes edit: lol this is actually pretty much the solution you suggested. gg me

Proving by mathematical induction🗿

yes because any 3 points are not in a line. Nice way to find the pairings.

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

That's all well and good, but can you prove it for red and GREEN dots?

Obviously.

I have yet to see the video, but my hypothesis is that, choosing the closes blue point to a red point should always lead to segments not intersecting. Drawing intersecting lines requires you to choose the furthest blue-red pair of points to be connected. I supposed that a parsimony approach on total segment length, where you add the length of all segments, and you choose the arrangement of connected points that have the least total segment length would always lead to segments not intersecting, no matter how many points you have. Edit: 2 min in and I guess I was right...? My idea was reducing the problem to 4 points --- 2 pairs. Drawing a rectangle with those points, and drawing the two lines that intersect, one can see that lines drawn can be equivalent to the hypotenuse and the other two sides of a triangle -- the two hypotenuses intersect. No mater how much to deform a square, you will always end up with a line that is the longest one and it will end up intersecting another. My conjecture/assumption comes with the fact that adding the longest line with any other line, will always yield you a bigger number than if you chose the other pair. If you add more squares, the solution is clear: choose the total sum length of lines that is the smallest.

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

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.

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)

what if the blue and red points are all on the same line, in a configuration that makes it impossible for lines not to overlap?

Thanks for mentioning Odysee, I wasn't aware it existed and I wanted to move away from RU-vid.

red and blue and connecting dots… as a fellow EE all I see is PCB layout

My proof is that it's intuitively true

feels counterintuitive that the fact that changing the connections which can create a new intersection does not break the proof. well it just doesn't

The solution and proof are immediately obvious, but I couldn't for the life of me state a rule to follow. It's just self evident.

So, stupid question: how do we know that by freeing up intersections we don't create new ones and we cant get into a circular infinite loop of states?

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

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.

I've got an Odysee question. Anyone have thoughts on whether it actually has advantages/disadvantages to RU-vid?

Actually bro i got that idea before you said it but I don't know how to prove it mathematically 😶