A 1957 Putnam exam problem 

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

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.

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.

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.

I like the way you think! I think the missing piece is specifying _distinct_ points in the problem statement.

Any unit of distance, so 1cm, 1km, 1m, doesn't actually matter

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

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

????? there is no distance with only one point

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