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

Next video (on Odysee): odysee.com/@ZachStar:0/max-di...
My Odysee Channel: odysee.com/@ZachStar:0
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

[@DukesAPG]

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.

[@kangmoabel]

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

[@johnchessant3012]

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.

[@randompast]

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

[@wenzhengli6716]

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.

[@JoeCMath]

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!

[@cmilkau]

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

[@MegaKotai]

At

[@Obikin89]

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 !

[@christiananderson3192]

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.

[@johanngambolputty5351]

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.

[@FarSeenNomic]

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

[@liltrashpanda174]

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

[@Reddles37]

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.

[@justsomegoosewithinterneta4199]

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.

[@andreujuanc]

This is mind-blasting

[@notn0t]

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.

[@md.adnannabib2066]

Zack man i was waiting for your videos for months

[@hgu123454321]

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?

[@siegfriedstow]

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.