A 1957 Putnam exam problem
Вставка
- Опубліковано 27 кві 2022
- Visit brilliant.org/ZachStar/ to get started learning STEM for free, and the first 200 people will get 20% off their annual premium subscription.
Previous Video: • Can you always pair an...
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
I just want to swing by and say that I just discovered that you do both comedy and science and I'm super impressed. Keep grinding okay
id say 7 points
Construct a circle with radius 1
Add diameters bisecting the circle an arbitrary number of times.
Each endpoint of each diameter is now a point.
Each opposing point from a diameter has the max distance of 1.
You can have N number of lines of distance 1 with none exceeding 1, and roughly N^2 lines with a distance less than 1.
I just wanted to see your main channel, and didn't know it was this, pretty neat
3:14 This part is easy. Add up all the numbers of max-distance pairs that each point is a part of. This should be twice the number of max-distance pairs since each pair is counted twice. So by assumption it's greater than 2n. But that would be impossible if each of the n points were part of at most 2 max-distance pairs. So at least one is part of 3 (or more) max-distance pairs.
I still prefer my trivial version more (from last video)
The maximum number of max length segments would be if the points are equally spaced on a circle and you have two lines per point, but you have two points per line so you get max lines= n*2/2= n so no more lines than points.
A slight thing (at 2:00) you are stating that if we have 2 line segments of length 1 that are not crossing we can form a quadrilateral with intersecting diagonals. But that are missing not coverint e.g. the pairs {(0,0), (0,1)} and {(1, ½), (2, ½)} for which we can connect every point with every other one without any interactions.
To resolve these we can note that if the convex hull of our 4 points form a triangle with a base of 1 with the corresponding height of at least 1. Thus one of the 2 remaining sides have to have a length > 1 and the statement that the segments must cross are still true!
I feel this proof would have been simpler by drawing two points, a circle around each point that has a radius of the distance between the two points, then showing that the two points where the circles intersect have a greater distance than between the two original points.
With just that, you'd show that 3 points can have 3 max distance lengths, but any more points added to the system cannot increase the number of max distance pairs by 2, which would be necessary for m to become greater than n.
This simple construction was the entire basis of the response I left on the previous video.
That's exactly how I tried approaching it. To add on, once you have 3 points all 1 unit apart from each other and you draw a circle with radius 1 around each, there is no point where two of the circles intersect at a point inside the 3rd circle. The 4th point added has to be at an intersection of 2 circles in order to add an additional two pairs to surpass n, but the 4th point also has to be inside the 3rd circle or else it would be greater than 1 unit away from that point, which would contradict the greatest distance being 1 unit. But because no such point exists and every additional point will add a max of 1 pair, n will always be greater than the number of pairs of points 1 unit apart.
Same here, I just noticed your comment after I posted my proof, I think we just all worded it differently.
This doesn't prove a thing. I could have 5 closely placed points on a circle of radius 1, then by adding the next point at the center of the circle, I increase max distance pairs by 5.
In addition, you attempt to construct a counter example by starting with the triangle formation, and argue that it is not possible; but maybe there is a counter example without that triangle formation in it, so you couldn't have reached it anyways.
@@saidmoglu starting with a triangle formation? No, I'm starting with 2 points and calling the distance between them the max distance. Where the circles centered on those points with a radius of that max distance intersect are the locations where more than 1 max distance pair can be made by placing 1 point. The circles intersect at 2 points, so if those 2 intersections are farther apart than the max distance, there is no way to add more than 1 point that increases the max distance pairs by more than 1.
A triangle could be constructed within my proof, as it's basically just a statement away from being proved to be necessary for points and max distance pairs to be equal; however, that's not necessary for showing that the number of max distance pairs will never be greater than the number of points.
Sure, you could place some arbitrary n points on some small arc length of a circle, and then adding the point at the center of the circle would give that many max distance pairs so you have n pairs and n+1 points; but then what? You try to increase the amount of max distance pairs by more than 1 with 1 point, which as I've shown, you can do exactly once with a point that increases max distance pairs by 2, bringing max distance pairs to a quantity equal to the number of points in the system (n+2 pairs and points).
Just because I didn't explicitly address every case in my explanation of the construction doesn't mean they aren't addressed by the construction itself. Every point added to the system that increases max distance pairs must fall on at least one of the circles and within or on the other circle. The circles in my construction implicity address every point that can be added to the system.
Nice proof! What would happen if the points, instead of being on a plane, were on some surface with positive or negative curvature? How would the argument change?
Well this whole proof relies on the fact that the diagonal of a trapezoid is greater than the side lengths, which isn't always necessarily true on a surface with curvature, meaning the proof no longer works.
For a simple example, in hyperbolic space the perimeter of an object is greater than in euclidean space, so there's likely some amount of curvature where the diagonals of a square are equal to the side lengths, so you'd have 6 pairs of points a distance of 1, with only 4 points
@@CalebTerryRED your example isn't valid. The triangle inequality still holds in hyperbolic space, so the sum of the lengths of the diagonals of a quadrilateral being greater than the sum of its opposite sides still holds.
A regular tetrahedron with its vertices on a sphere has 6 maximal pairs with 4 points.
@@nagrajan777 they were asking about non-euclidean 2D space, not 3d spaces
@@actualperson1971 Yes, but to my understanding spherical geometry allows you to construct a quadrilateral whose diagonals are the same as its side lengths since they sort of "wrap around" the geometry.
Re 3:20 is proved by the pigeonhole principle.
For each n points there are m pairs with the largest distance. OK I got it.
We must prove that
m
Question: Can every proof by 'descent' (like this video's proof) be rephrased as a proof by induction? And is one more 'aesthetic' than the other?
It's kind of the opposite of a proof by induction, right? Since with induction you assume the base case, here you're disproving its existence
Yeah they're logically identical.
For induction, we have to prove that if we *know* the theorem in the question is true with n points, then its true with n+1.
Now assume that was false, i.e., its true for n, but its false for n+1.
Well that's not true, because Zack showed that if its false for n+1, its false for n. But we know it _is_ true for n, because induction.
And so we have a contradiction, meaning our assumption was false and the theorem is true for n+1.
Boom, induction proved.
This is all very similar to the Well Ordering Principle, if you want to know more.
Yes; that's what a "descent" argument _is,_ in disguise:
1. S(n+1) → S(n)
2. not(S(n)) → not(S(n+1))
3. manually show not(S(x)) for initial x
@@codegeek98 I like the proof of infinite primes as an example.
Assume there is a finite number of primes.
Given the list of all of these primes, multiply them together and add 1 to get a prime that is not in the list.
The set of all primes does not contain all primes, therefore there are an infinite number of primes.
Or:
Given any set of primes, you can always construct a number by multiplying them all together and adding 1 that is either a prime not in the list, or divisible by a prime not in the list. Therefore every finite list of primes can always have a new prime added to it, therefore there are an infinite number of primes.
It's the same proof, it's just that one doesn't start from a contradictory position.
first two make shape from overlapping cirlces, whenever corners are saturated two maxes added but you can only make 2 corners twice, the rest of the time corners are formed by cutting off other corners so corners
Hey Zach,
Thanks for the cool problem and solution! I think there might be a slightly easier and more intuitive solution though.
Think of this whole system as a graph in the following way: every point is a node and nodes have a vertex between them if they have the maximum distance( =1) between them.
Now just consider the connected graphs, say G_1…,G_n with n_1,…,n_k number of nodes in total. Now, by induction each G_i has at most n_i nodes with max distance between them. So adding up, there are at most n_1 + …. + n_k = n nodes with the maximum distance between them.
(You can check the base quickly)
Jigsaw frantically watching this in the background, trying to get a machine to work
Dude that‘s actually cool
The statement at 3:32 is easily shown via the pigeonhole principle. You know that there will be >2n line segment ends, then if those ends are evenly distributed among the points, after 2n are distributed, each will have 2. Thus, at least 1 must have 3.
Could you do a video on the usages of abstract vector spaces from linear algebra?
Maybe i'm getting something wrong, but is there any rule that doesn't allow for several points to be located in the same place? For instance, when it is reduced to x, a, c; if there where two points in location a wouldn't you have pairs a-x, a2-x, a-c, a2-c, and x,c. Those will be 5 max distance pairs with four points.
Me watching this video knowing full well I suck at geometry:
"Mmmm yes, very true."
Cool as hecc
Thats one of the questions a mathematician thought of while high that eventually turns out to have a use in 4 different fields of science
Question: If all of the points were in the exact same position, wouldn't that mean that they would all be the same distance away from each other? I mean, if you have 10 points all at the same x-y coordinates, wouldn't every pair distance be at the maximum? You said at 1:11 that if there are ten points, there are 45 possible pairs. As, in this situation, every pair would be the maximum, with 10 points wouldn't it possible to get 45 maximum distance pairs? Or maybe I just understood the question wrong, idk lol
I like the way you think! I think the missing piece is specifying _distinct_ points in the problem statement.
What would happen if instead of being on a plane, the points were on a boat?
Niice
This is so different coming from the skit channel
pog
I'd like to see this for n dimentions
sometimes i forget that this guy is really fucking smart and not some frat bro
What does it mean " 1 away" ? What is "1" in this case? Like 1 point away, 1 cm away? @Zach Star
Any unit of distance, so 1cm, 1km, 1m, doesn't actually matter
Why can't theta > 60deg, and dist(a,c) > 1? That's ok, as long as all the other distances are 1 then (a,c) doesn't have to be 1, no?
EDIT: I'm dumb, then (x,a) and (x,c) wouldn't be max distance. Stupid stupid.
at least 3
nice vid! Now do it in 3d _-_
Isn't there a simpler proof? Start with 3 points. They must define an equilateral triangle, it's the only case. Label the points 1, 2, and 3. Imagine the 1st point is the center of a circle, the connect the arc of that circle between points 2 and 3. Do this same procedure for points 2 and 3, connecting circular arcs between the other two points with that point as the center of the circle. Now the only places you can add new "max distance pairs" is anywhere along these arcs. Except that each time you add a point, it ONLY pairs with the point at the center of the circle of the arc you placed it on, and does not form pairs with points on any other arc. Because geometrically that distance would be less than 1, even if only infinitesimally. Therefore you can never form more max distance pairs than points you add, because each point can, at maximum add only 1 new pair. Correct me if I'm wrong.
You are using a greedy algorithm to try to get the maximum number of pairs in every point. You haven't proven that you can't get more pairs than points by first intentionally placing points suboptimally before managing to create pairs so fast it exceeds the number of points.
I think that you can't be sure that, starting with the max number of pairs for three points, and only adding points when that increases the number of pairs, this will give you a configuration with the max number of pairs for n points. For all you know, there might be a completely different configuration that you can't do with only three points but that gives you more pairs at max length for large numbers of points
@@Miju001 Drop a single point. Now where can you drop another point that's max distance? It's the circle defined by that point. Now you have 2 points. Now where you can drop any point? Anywhere that's on the radius on a circle but still contained within the intersection of the other point's circle. All infinitely many of these points will only add 1 pair with the exception if you drop the point forming the equilateral triangle, because that's the only point that will form 2 pairs (with the 1st and 2nd original points). I think it will help if you draw it on a paper, you will see that this is the only procedure possible, there are no other configurations.
@Miju I guess I mispoke by saying the equilateral triangle was the "only case" the 1st time. It's not the only case, it's just a case that's giving you the maximum number of pairs to start with. This is not really a proof, since I'm not good at those yet. But it would be a proof if I worded it correctly. :D
OK, seeing it like that, it makes more sense. I still have a few doubts about it, but tbh I think it works
97 points
I never knew this channel existed until someone pointed it out on your other channel. Dang that’s impressive.
5 points
This is surreal lol
Im expecting like a punchline because your voice sounds like its a joke but no, serious. LOL
Another way to prove:
Just think about the maximum number of pairs possible. All points have to fall on the perimeter of the circle. Each pair will fall in its diameter (max distance between them). Any point outside will not be possible as it will exceed the diameter or our maximum distance. This will be true for every Even number of points. Number of pairs=n/2.
Now, an odd number of points will also fall into a circle, but not in diameter. Just like 3 point maximum distance shown in video. In this case maximum 2 pairs are possible from 1 point. Number of pairs=n
Why exactly do they have to fall on the perimeter?
@@konqrentm0ps980 anything inside circle will not have max distance.
@@gauravagrawal9265 Not Necessarily. If you take an equilateral triangle and put a fourth point on the perimeter of a larger circle which has a center in one of the vertices of the triangle and passes through the other two you will have an arrangement of four points with four maximum distances that don't lay on a single circle
@@konqrentm0ps980 the 4th point and the point of vertices on larger circle will have maximum distance between them larger than the previous maximum.
Any point outside of the circle would exceed the radius, not the diameter
How about n=1?
????? there is no distance with only one point
What happens if you make a circle though? And I mean a full circle, not just a bunch of dots roughly in the shape of a circle. A circle has an infinite amount of points on it (which is relatively easy to prove, but not the point right now, so I'm going to skip over that). The longest distance between any given two points can be found between one point and the one point on the exact opposite side of the circle. Since all the points are on a circle, this logically goes for every single pair there is; no point has more than one partner, and no point has no partner at all. Thus, there would be exactly half as many pairs as there are points. But we said that there are an infinite amount of them, and half of infinity is still infinity. So... there would also be an infinite amount of pairs, correct?
the infinite series of points on the circles perimeter is less than the infinite series of points int he area of the circle.
@@aminyapussi4740 The cardinality of the ball and the sphere are actually the same
The only problem is that infinite is not a number. As you increase the number n of points, the number of line segments still remains at n/2 if n is even and at n if n is odd. So it never surpasses the number of points. The ratio is 1 if n is odd and 1/2 if n is even
The set of all points on a circle and the set of all diameters are infinite sets, the usual way you think about numbers don't work with them. Since you can find a bijective 1 to 1 function mapping between them, their sizes are said to be equinumerous which basically means cardinality (size) of sets are equal.
x^2 + y^2 = r^2
Is it possible the universe doesn’t end or we find someone to cheat it and the death of the sun btw screw Conrad Murray worldwide, Michael Jackson the greatest
Yooo had no clue u were a student.Most utubers r untalented
madguitargenius 🎸