Fun geometry problem

Math major here and I got a really fun problem I thought I'd share.

Where [math] n [/math] is a natural number, supose that you have [math]2n[/math] points in space. In other words, you have the points
[math]A_{1}, A_{2}, ... , A_{2n}[/math]

Prove that a plane that does not contain any of these points can go through at most [math]n^2[/math] of the segments that connect these points.

I did a page long proof but it isn't very general and probably too intuitionistic so hopefully someone can come up with a better argument. Still, if someone is interested I can give an outline of what I did.

No fancy math is needed so literally anyone, even a highschooler, can give it a shot.

take the derivative of n^2 segments=2n points in space

there you go

>take the derivative of n^2 segments=2n points in space
w-what?

It's pretty easy to show that at least n^2 connections can be cut.
Start with a plane, put half the points on one side, and half the points on the other. Connect each point to every other.
Now, (2n/2)^2 connections are cut by the plane (n for each of the n points on one side.)

Now, move one point from one side of the plane to the other. Then you lose n connections (the original ones) but cut n-1 new connections (those in the side at which this point originated.)
So you've lost 1 cut connection by doing so.

For any arrangement of points relative to the plane, we can arrive at this arrangement by moving points as above, therefore only reducing the number of cuts.

This process is can be repeated for any plane.


Sorry for the shit-tier proof, but I'm rushing to class and can't give anything more rigorous.

Here's a challenge problem:

Let Sn be the symmetric group on {1,...,n} and let T be a subset of transpositions in Sn. From T, construct a graph where {1,...,n} is the vertex set and {{i,j} : (ij) is in T} is the SFW set.
Prove that this graph is connected if and only if T generates Sn.
Just turned a proof of this in this morning for my grad level algebra class. Pretty easy tho.

Absolutely retarded.

* is the edge set. Not SFW
On mobile, I know, I will kms later

>Start with a plane, put half the points on one side, and half the points on the other. Connect each point to every other.

wouldn't it make more sense to prove that by minimizing it first using basic probability

>Now, move one point from one side of the plane to the other. Then you lose n connections (the original ones) but cut n-1 new connections (those in the side at which this point originated.)

How do you prove this is the case?

Anyways, you are probably right. It is just that if I'd say something like "move" my geometry professor would spit on me.

I did a similar construction to yours.

A plane in the middle with a line of points in each side.

I even proved that if you connect a point from one side to a point of the other, that segment must cut the plane in the middle. Because if I didn't then again, my geometry professor would spit on me.

Anyways, freshman here and all I only know basic algebra. What groups, rings and fields are. No more so I don't think I can do your problem.

Well give a proof and find out

Imagine the graph formed by those points and segments through which the plane goes.
This is a graph with 2n vertices and without 3-cliques (there are no 3 vertices all connected with each other). From this follows that there are at most n^2 edges; or it's just the k=3 turan's theorem.

Try setting up an equivalence relation on the set of points. See how moving an element from one equivalence class to another changes the number of cuts.

I've only done differential geometry so I wouldn't know how to prove it some other way.


Believe in yourself!

desu I was looking for something like this. Like that meme where you prove that root 2 is irrational because if it wasn't then it would contradict Fermat's Last Theorem.

Absolute overkill and I love it. This was a problem given in a freshman geometry class.

don't know how to use latex sorry, and yeah that makes sense now that I think about it, r8 this shit dawg, I'm just starting to do basic analysis and want feedback on my proof

>Consider a plane P in R^3 where 2n is a natural number representing the number of points in space not lying on P, and A1, A2, etc represent the points
>Let s be the set of points A1, A2... A2n
>P divides s into two subsets of s, s1 and s2 for the points facing each side of P
>any segments connecting points within s1 and s2 are frivolous as we are only measuring the segments that traverse through P so only segments linking elements of s1 and s2 are relevant
>consider a case where the number of elements in s1 are greater than the elements in s2, and vice versa
>we will represent this by saying the number of elements in s1 is n+a and in s2 n-a where (n+a) + (n-a) is 2n, our number of points
>the possible number of segments is (n+a)(n-a) which equals n^2 - a^2 which is less than n^2
>thus both sides have n elements meaning there must be an equal number of points on both sides.

Assume the graph is connected. Pick any i, j. Then there's some path in the graph: i, a1, ... ak, j. So T contains transpositions (i a1), (a1 a2), ... (ak, j). But (i, j) = (i a1)(a1 a2)...(ak-1 ak)(ak j)(ak-1 ak)... (a1 a2)(i a1). Hence T generates any transposition (i j), so you can get the whole Sn.

Assume that T generates Sn. Then (i j) = some transpositions from T, it's easy to see that i, j will be connected in the graph

this is the best solution desu

thanks man.

Pretty good user. Where's the probability though? Did you mean combinatorics?

Perfect! Here's another:
Let Surject(X) denote the set of all surjections on the set X. First, show that , where * is function composition and id is the identity function on X, is a right cancellative monoid (optional.)
Then, show that any right cancellative monoid is embeddable in for some X.

I have hints available upon request.

And yet another potentially good thread dies. Fuck you, Veeky Forums, seriously.

OP here, well it was already solved.

But I guess I can revived it, given that no one has yet proven it the traditional way.

Here is how I did it: Induction over n.

For the case n=1 notice that you have only 2 points, therefore only 1 segment that connects those points.

So now a plane will cross at most 1 segment, given that it is literally the only segment.

And because n=1, n squared = 1 so this satisfies the base case.

Now, who knows where to go from there?

Lets see how other people do it because as I said, my induction step was very intuitionistic so probably there is a better way to do it.

If 2 points are on the same side of the plane, there will be no splits, if 2 points are on opposite sides, there is 1 split between them, so to maximise splits we have half on one side and half on the other side of the plane. This forms a bipartite graph, which clearly has maximum segments (and hence, splits by the plane) \[n^{x}\].

How is this the traditional way? This seems a very contrived, un-intuitive and overly complicated way. Surely next you do the assumptive step next, set [math]n = r[/math] and assume the most cut segments for [math]2r[/math] points is [math]r^{2}[/math].

>How is this the traditional way?

The traditional way is any way that does it using only euclidean geometry, no fancy algebra or graph theory as other people have tried it.

I don't get what you think induction is. I think you are wrong.

Bump, can anyone solve it using only geometry and logic?

>number of ways to match 2 sets
>graph theory
Just stop.