Ramsey TheoryYou are currently
browsing as guest.
Click here to log in
See if you can work out a way that can happen.
At the next gathering you wonder if the same thing has happened. And here's the thing: there are six people, and it can't happen.
Claim: In every gathering of six or more people, there will either be three who have all shaken hands, or three, none of whom have shaken hands.
It seems like proving that requires writing down all the ways you can have six people, but there's a lot of them. Between six people there are 15 potential handshakes, and each may or may not have happened, so there are 2^15 or 32768 possible ways things can go.
That's a lot of checking. But there's another way to see this.
Firstly, let's look at person X, and see who he/she has shaken hands with. It's either 3 or more, or less than three.
If person X has shaken hands with 3 (or more) people, then we look at that cluster. If any have shaken hands with each other, then we have our handshaking triple: person X and the other two. If none have shaken hands then they are a non-handshaking triple, and again, we have what was claimed.
The same goes if person X has shaken hands with fewer than three, we just swap shaking for not shaking, and the whole argument works.
In more colorful language, if you have six points and join every possible pair with either a blue line or a green line, you can always find a green triangle or a blue triangle. Always. But if you only have 5 points it's possible to arrange having no triangles.
Now this is definitely too big to check by hand, so we'll do it by logic.
Firstly, arrange all the points in a line, and look at the first point. Look at the lines going to the right, to the bigger numbers. There are infinitely many of them, so there are either infinitely many reds, in which case color the point red, or infinitely greens, in which case color the point green. If there are infinitely of each, you can choose.
The lines going to the right whose color doesn't match that of the point, delete the destination points. You still have infinitely many left.
Now move to the next point and repeat. Then again, and again, and again. Now you still have infinitely points left, each one colored, and for each point, the lines going to the right are all the same color.
You have infintely many points, and they're all green or red. If you have infintely many green, delete all the reds, otherwise delete all the greens. Now you still have infinitely many points, and they're all the same color. That means all the lines going to the right are all the same color, so all the lines are the same color.
So you have infinitely points, all joined by the same color.
Last change to this page
Full Page history
Links to this page
Edit this page
(with sufficient authority)