Party Problem Applications

Intro to Proofs · Axiom Academy

Invite six people to a party and one thing is unavoidable — three of them already know each other, or three of them are total strangers. Put that guarantee in your hands. Six guests are in a room. Every pair either knows each other or doesn't — and yet, no matter who knows whom, you can always point to 3 mutual friends or 3 mutual strangers . Three moves to feel why. Tap any two guests to set their tie — a green line means they're friends, a red dashed line means strangers. Try to wire up all six so there's no friend-triangle and no stranger-triangle. You won't be able to. Why it's forced — the pigeonhole step Pick one guest, A. A has five ties — and only two kinds. Drag how many are friendships and watch: with 5 split into 2 colours, one colour must reach 3. Those three are where the triangle hides. Five people can dodge it: arrange them in a ring of friends with stranger diagonals and there's no monochromatic triangle anywhere. Add the sixth and every escape route closes. Flip between the two and see the line. What you just proved is Ramsey theory's headline: R(3,3) = 6 — and its slogan, complete disorder is impossible . Make any structure big enough and order has to appear, whether you want it to or not. Erdős joked that we could just about compute R(5,5) if aliens demanded it — but for R(6,6) , we should attack the aliens instead. Guaranteeing a route still exists when some links fail — order you can count on under stress.

This is the written version of the interactive lesson above. See the full Intro to Proofs course.