I know, I know, that parties seem to have become extinct but let us assume that at some point we will again begin to have gatherings of more than just the people in our own households. When that happens, here is a fun exercise you can do. Define as mutual acquaintances as any two people who have met at least once before this occasion, and mutual strangers as any two people who have just met for the first time. It actually does not have to be done at parties but with any group of six or more people.
If the entire group consists of at least some people who do not know every one else, you can take a bet with someone. Let them pick any six people in the group. You bet that that group of six will have a subgroup of three people who are either all mutual acquaintances (i.e., each one has met the other two before) or are mutual strangers (i.e., each person has never met either of the other two people before). You should not actually wager any money on this bet. That would be unfair because you are 100% certain of winning it and you would be taking advantage of the mathematical ignorance of the other person. The result holds true with any group of six people picked at random from anywhere, (say) Facebook or your local community.
Of course, if this is a group of people who all friends and know each other or who are all likely strangers (say people in a café), then the result is obvious. What is not obvious is that this result holds for any group at all that can consist of any combination of mutual acquaintances and mutual strangers. This is because of a theorem from a branch of mathematics known as Ramsey theory. You can see a sketch of the proof of this result here.
Ramsey theory is named after Frank Ramsey who was a mathematics and philosophy prodigy at Cambridge University in the UK who died in 1930 at the very young age of 26, thought to be from a liver infection that he may have picked up by swimming in the river Cam. A review of a biography of Ramsey describes his life and his contributions to mathematics, philosophy, and economics and how despite being so young, he was held in high esteem by already eminent people like the economist John Maynard Keynes and philosophers G. E. Moore and Ludwig Wittgenstein.
I don’t know about it not being intuitive: since the only possible states in relation to another are stranger/acquaintance, if there were fewer than three in both states, at least one person would be in neither state.
Not really like the “birthday problem”.
The only surprise seems to me to come out of a failure to link the two outcomes as dependent. It’s easy to imagine a group without 3 mutual strangers, and easy to imagine a different group without 3 mutual friends. So most people will think there’s a decent chance there could be a group without both if they dont think through it rigorously.
Yeah, in order to get no groups of 3 mutual acquaintances, you would be limited to at most pairs of mutual acquaintances.
So imagine you have 3 pairs of acquaintances
AB
CD
EF
In order not to reach the 3-acquaintance group. then A&B cannot have more than one acquaintance each in the following two groups, AND -- very importantly -- the acquaintanceships of A&B cannot be the same acquaintanceship.
so if AC is an acquaintanceship, then BC is a stranger relationship. Likewise for BD and AD.
and if AE is an acquaintanceship, then BE is a stranger relationship. Likewise for BF and AF
Last we have to consider relationships between CD and EF.
Let’s set things so that if CE is an acquaintanceship, then DE is a stranger relationship. Likewise for DF and CF.
So this is the maximum state of relatedness one can have without meeting the minimum requirements for the first possibility. .With this maximum state of permitted relatedness, can we avoid meeting the requirements for the second possibility, having 3 mutual strangers?
BC is a stranger relationship, as is BE. but CE is an acquaintanceship in our model.
So how about Starting with AD?
AD is a stranger relationship, as is AF. But DF is an acquaintanceship.
Since we can’t include both AB or CD or EF in any stranger groups, this seems to negate the possibility of meeting the 2nd prong. So is the conjecture wrong?
Go back to the acquaintanceships and find that
AC, AE, and CE are in fact all acquaintanceships. Oops! It doesn’t just matter that in each pair of acquaintances, each one of the pair can only know one person in each of the other pairs, it matters WHICH other they know.
If we fix the CE relationship so that these are now strangers and DE are now acquaintances, then DF must also now be strangers and CF acquaintances.
BUT… since we’ve changed the relationships to specifically exclude the possibility of 3 mutual acquaintances we have to go back to the stranger possibility and find that we were originally foiled here…
But we just reversed the CE relationship to that of strangers. Therefore, we have a group of 3 people who are all mutual strangers.
Of course, if we change just a single relationship without changing others (For instance changing the relationship between C and E without changing the relationship between D and E.) then as we are on the bitter edge of disqualifying one and that still requires qualifying for the other, we can only break the qualification for one test by newly satisfying the test for the other qualification.
In other words, we cannot create fewer strangers without creating more acquaintances. We’re stuck. We must satisfy one prong or the other.
The quickest way to see it for me is this; choose any one person, call them 1. Since there are only two relationships, which we’ll call a and b, at least three of their relationships to the other five must be the same, and we’ll say it’s a. If there are more than three, choose any three. Call them 2, 3 and 4. If any one of the relationships between 2, 3 and 4 is a, we’re done (e.g. if 2-3 is a, then we have 1, 2, 3 with mutual a). If none of the relationships between 2, 3 and 4 are a, they all must be b, and we’re also done (2, 3, 4 with mutual b).
This reminds me of the ‘panpipes puzzle’ which I first read in a Martin Gardner book. Take ten tin soldiers of different heights; arrange them in any order; then find a subset of four of them that are in an always-increasing or always-decreasing order, like a set of panpipes.
(To prove this, we can assign each soldier a pair of numbers, ‘u’ and ‘d’, which are number of soldiers in an ‘up’ or ‘down’ order including this one and all the ones to the left of it. So the left-most one must be (1,1), the next one will be either (1,2) or (2,1), the third one is:
(3,1) for 123
(2,2) for 132 or 312
(2,1) for 213
(1,2) for 231
(1,3) for 321
and so on.
Now, next we show that no two soldiers can have the same pair of numbers. Because none of them are the same height, if one had the same numbers as one to its left, it must be either higher than that other one, meaning the ‘u’ number would be one greater; or lower than that other one, meaning the ‘d’ number must be greater. So no two soldiers can have the same pair of numbers.
From there we just invoke the pigeonhole principle: there are only nine possible unique pairs of numbers for which ‘u’ and ‘d’ are in the range from one to three. Therefore, by the time we reach the tenth entry, we must have a sequence of four or more.)
It occurs to me that part of it is linguistic obfuscation.
If the bet were rephrased as “at most two people know each other and at most two people are strangers”, it would become apparent that this is not something that can happen.
Am I incorrect in saying that this is equivalent to:
“If you flip 6 coins, there will be either at least 3 heads or at least 3 tails.”
?
(being acquainted or stranger is a binary state, yes?)
@Owlmirror:
Not correct. Because “acquaintance” is a property of a pair, not of a single. And in the case of 3 mutual acquaintances, it’s a property of a trio made up of 3 pairs of relationships. AB, BC, and AC.
You can, however, create an arbitrary binary state = “Mutually acquainted with at least 2 other people”.
If no one has this property, then the “3 mutual strangers” proposition is true.
My instinct is that if even 3 people do not have this property, the “3 mutual strangers” proposition must be true, but I’d have to think it through.
However, I like my original formulation better. Try to maximize relationships without making “3 mutual acquaintances” true. If you do that, the 3 strangers proposition is true. If you take away more acquaintanceships, then obviously the 3 strangers proposition is true. And since you maximized the number of relationships you could have without having 3 mutual acquaintances, if you add even one acquaintanceship to break the “3 strangers” proposition, you complete the “3 mutual acquaintances” proposition.
Owlmirror @7: Yes, that’s incorrect. Note that if you flip 5 coins, there will also be either at least 3 heads or 3 tails. But among 5 people, there don’t have to be at least 3 who are mutual strangers or mutual acquaintances. Numbering people 1-5, you could have 1 knows 2, 2 knows 3, 3 knows 4, 4 knows 5, 5 knows 1, but every other relationship is a “doesn’t know” (1-3, 1-4, 2-4, 2-5, 3-5). In this case, there is no way to choose a triplet in which everyone either knows each other, or everyone is a stranger.
It’s the relationship between any two people that’s binary, so for six people, that’s 15 coin flips, with each flip associated with a unique pair of people.
I think Owlmirror has it aright, other than I’d have written ‘analogous’ rather than “equivalent”.
—
Interesting that we commenters have all focused on the specific example used to illustrate an use of the featured theorem, rather than on the theorem itself.
It can’t be the case that an odd number of people have a relationship with exactly one other person. (In other words, it’s symmetric.) So, with six people numbered 1-6, suppose #1 & #2 have a relationship while they’re both strangers with everyone else. Also, suppose #3 is a stranger to all of the other five, since that will satisfy the requirement that at least three are not acquainted with at least two others. Then we can let #4, #5 and #6 be acquainted with each other (since we fulfilled the requirement, but this means they can’t be acquainted with #1, #2 or #3).
A summary of that, using “R” for the relation:
1R2 & not R(3456)
2R1 & not R(3456)
3R() & not R(12456)
4R(56) & not R(123)
5R(46) & not R(123)
6R(56) & not R(123)
To make it work, we can only have one from the group consisting of #4, #5 or #6. I’ll arbitrarily pick #4 from that lot. Also, a trio of strangers couldn’t include both #1 & #2. I’ll arbitrarily pick #1 out of that pair. Then, we could only complete a trio of strangers by including #3, which of course works since #3 is not acquainted with anyone. Apparently, #3 didn’t need an invitation (or not one from an acquaintance) in order to attend this party.
Here are the six options, with the setup I just mentioned: (134), (135), (136), (234), (235), (236)
So that does work. However, in order to derive the theorem (the version considered here), you don’t need to assume at least one person must be a stranger to all of the others (or equivalently that they’re acquainted with everyone), although it is a possibility. You can certainly come up with scenarios in which all of the people have a mix of both acquaintances and strangers.
With six people, each person has a relationship (or non-relationship as the case may be) with the other five. (Although it makes no difference, let’s say the first item on the left side of each equation represents an acquaintance and the second is a stranger.) Here are all the possibilities for any given person: 0+5=5, 5+0=5, 1+4=5, 4+1=5, 2+3=5, 3+2=5
They all need to add up to five, because there are five (or more) other people in a group of six (or more). And no matter which one it may be, there is a number larger than 3, either the first item or the second one (but not both, unless there are more than six people). For the sake of clarity, I’ll say that these represent three acquaintances of the selected person, but again, it applies to strangers in the same way.
— If any pair of the other three people are also acquainted (or all three of them are), that means the original two acquaintances plus this new one forms a group of at least three who are acquainted. (If it’s all three of the others, the trio wouldn’t need to include the original person I selected, but it is at least three either way.)
— If, on the other hand, none of them for such a pairing, then that means they are a group of at least three who are strangers. (And in that case, what happens is that the trio doesn’t include the original person I selected, because they were an acquaintance of the other three and not a stranger to them.)
~~~~~~
Owlmirror, #7: It sounds like you’re saying, as I did above, that any given person in a group of six must have either 3+ acquaintances or 3+ strangers, which is true. But the theorem is more or less that you’ll always have a triangle of the same type of connection (acquaintances or strangers), not just that a person must have at least three connections of the same type. You can imagine cases (when there are only 4+ in the group) in which three of the same type of connection do relate a person to the rest, yet it still doesn’t form such a triangle.
Whoops. I meant at least as large as three, greater than or equal to three. I wrote “at least” at least three times, and I needed to write it at least once more.
A public service announcement: Three is not larger than three.
The more you know
……………………….*
The analogous smallest party size in order to be sure of 4 people who all know or all don’t know each other, is 18, and for 5 people it is not known exactly what the smallest party size is — I think it’s known to be between 44 and 48 (or something like that, I don’t remember). And for 6 and beyond, very little is known, even though it’s a purely finite problem that in theory could be solved by brute force computation. It’s just the numbers of possible graphs you must examine-- and then look for the cliques within them — gets super huge, super fast. Google Ramsey Numbers for more.