There is a party with 37 people. Every pair of them is either friends or not friends. Alice and Bob are the only two people at the party with the same number of friends. Alice and Bob are not friends with each other.
How many people are:
- friends with both Alice and Bob?
- friends with Alice and not Bob?
Say a "perfect extrovert" is someone who is friends with everybody. and a "perfect introvert" is someone who is friends with nobody.
Lemma 1: no party can have both a perfect extrovert and a perfect introvert.
Proof: by perfect extrovert property, they are friends, but by perfect introvert property, they are not, a contradiction.
Lemma 2: There can't be a party of n people such that they all have different numbers of friends.
Proof: The most friends someone could have is n-1. If everyone had different numbers of friends, the distribution of friend-counts would be 0, 1, 2, …, n-1. This would mean the simultaneous existence of a perfect introvert and extrovert, a contradiction by Lemma 1.
Lemma 3: If a party with ≥ 2 people has exactly one pair of people with the same number of friends, then either the party has one perfect extrovert or one perfect introvert. It may not have more than one of each.
Proof: Existence follows from the pigeonhole principle. If there is no perfect extrovert and no perfect introvert, then there are only n-2 possible friend-counts, and n people to have them.
If a party had exactly one pair of people that had the same number of people with the same number of friends, and both were perfect extroverts, then removing one would lead to a party with all unique friend counts, contradicting Lemma 2. Similarly if there were two perfect introverts.
Definition: given a friend-graph G, denote by I(G) what you get by adjoining a perfect introvert to G, and by E(G) what you get by adjoining a perfect extrovert to G. Define
E₁ = I₁ = • (the one-person graph)
Eₙ₊₁ = E(Iₙ)
Iₙ₊₁ = I(Eₙ)
Lemma 4: If a party G with ≥ 2 people has exactly one pair of people with the same number of friends, then
- If G has a perfect extrovert, G is isomorphic to Eₙ
- If G has a perfect introvert, G is isomorphic to Iₙ
Proof: By induction. For the base case, observe that any two-person graph is either two friends (E₂) or two strangers (I₂). For the step case, assume the lemma holds for n. Consider the friend graph of n+1 people.
-
in case it has a perfect extrovert: Let e be the extrovert, and consider G \ e. Because G could not have had two perfect extroverts, (by lemma 3) we conclude that
- G \ e has exactly one pair of people have the same number of friends
- G \ e has no perfect extrovert, so must have a perfect introvert So by induction hypothesis, G \ e must be Iₙ, and G ≅ E(Iₙ) = Eₙ₊₁ as required.
-
in case it has a perfect introvert: Let i be the introvert, and consider G \ i. Because G could not have had two perfect introverts, (by lemma 3) we conclude that
- G \ i has exactly one pair of people have the same number of friends
- G \ i has no perfect introvert, so must have a perfect extrovert So by induction hypothesis, G \ i must be Eₙ, and G ≅ I(Eₙ) = Iₙ₊₁ as required.
Corollary: If a party G has 2n+1 people (n ≥ 1), and G has exactly one pair of people Alice and Bob with the same number of friends, and Alice and Bob are not friends, then Alice and Bob have the same set of n friends.
Proof: By induction. In the base case, examine
I₃ = Alice----Bob Carol
E₃ = Alice----Carol---Bob
In I₃, Carol is the most recently added introvert, and Alice and Bob are friends, contradicting the assumption that they're not friends. So we must consider E₃, in which Alice and Bob have the same set {Carol} of friends, as required.
In the step case, observe that I₂ₙ₊₃ has Alice and Bob friends because I₂ₙ₊₁ does, so we reject it. In E₂ₙ₊₃, we have recently added an extrovert (who is friends with both Alice and Bob) and an introvert (who is friends with neither). By induction hypothesis, Alice and Bob have n friends (all in common between the two of them) in E₂ₙ₊₁, and so in E₂ₙ₊₃ = E₂₍ₙ₊₁₎₊₁, they have n+1 (still held in common) as required.
Therefore the answer to the puzzle is: 18, and 0.