A Well-Planned Party
Mid-terms are over, final-papers are submitted and all grades are fantastic. So what should a Williams student do on a Saturday night? Naturally organize a memorable party where students can share their success stories. Six students in Gladden, commonly known as the “G6 of math and science”, plan to organize a party in their dormitory. Before organizing the party they carefully plan all the details.
One of them says: “We should plan the party so that some students know each other and others don’t. This way we can strengthen old friendships and create new ones. There should be mutual acquaintances and mutual strangers.”
Another responds: “ Come on, Williams College is a small community, everyone knows everyone else.”
A third jumps in: “Okay, this is clearly not true. For instance, I am sure that there exists at least one, but likely many more students that I don’t know.”
The fourth says: “This debate is pointless. Get your papers and pencils, we should figure how this mutual acquaintance and stranger problem works.”
The following questions occurred as G6 attempted to solve their party organization problems:
[Excluding the G6 kids…]
- (i) How many people must necessarily be present at our party so that there are 2 mutual acquaintances or 2 mutual strangers?
- (ii) How about 2 mutual acquaintances or 3 mutual strangers?
- (iii) How about 2 mutual acquaintances or any k number of mutual strangers?
- (iv) How about 3 mutual acquaintances or 3 mutual strangers?
- (v) Can you generalize and prove the idea for any n mutual acquaintances and n mutual strangers? More formally, find the minimum number of guests that must be invited so that at least n will know each other or at least n will not know each other?
- (vi) If you still feel unchallenged… generalize and prove the idea for any n mutual acquaintances and k mutual strangers.
Help out the G6 and your solutions (if correct) along with your name will not only be recognized on the math department’s webpage, but the Gladden Kids may invite you for the next well-known G6 party.
Congratulations to Benjamin Demeo for submitting correct solutions to part (i)-(iv) of the November Mathematics Conundrum. Moreover, congratulations to everyone else who took time to work on the problem and submitted solutions.
Solution [Due to Benjamin]
(i) 2 mutual acquaintances or 2 mutual strangers
Two people must necessarily be present. If the two are friends, we have two mutual friends. If the two are not friends, then we have two mutual strangers. [[Works.]]
(ii) 2 mutual acquaintances or 3 mutual strangers
In this case two people would be too few. Consider the case where the two do not know each other, giving neither two acquaintances nor three strangers. Let us consider the case of three people. We have two cases:
- there is a pair of mutual friends in the group of three; or,
- there is no pair of mutual friends.
In the first case then, we have two mutual friends and we are done. In the second, we have three mutual strangers and which means that we are done.
(iii) 2 mutual acquaintances or any k number of mutual strangers
The answer is k. Here we use a similar argument to part (ii) of the problem. Consider a group of k people. If there is a pair of mutual friends in the group of k people, then we have two mutual friends and we are done. If not, we have k mutual strangers and we are done by fulfilling the other part of our argument.
(iv) 3 mutual acquaintances or 3 mutual strangers
6 people is the minimum. Consider one person in the group of six, call him A. Of the remaining five people, we can either choose,
- a group of three people that know A; or
- a group of two people that do not know A.
In case 1) we have two sub-cases:
- There is a pair of mutual acquaintances in the group of three that know A. If this is the case, than A and the two people form a group of three mutual acquaintances and we are done.
- There is no pair of mutual acquaintances in the group of three that know A. If this is the case, than these three form a group of mutual strangers and we are done.
Case 2) Using a very similar argument to case 1) there are either two people of the three that do not know also do not know each other, or all three of them know each other. In either case we are done.
The general solution for part (v) and (vi)as of today remains an open problems in Ramsey Theory.
For graph theory fans:
Part (iv) may approached using the two-coloring of the complete graph on 6 vertices. Since we are looking for three mutual acquaintances or three mutual strangers from all possible coloring arrangements the complete graph on 6 vertices come useful. Let’s take a look at such graph and call it K6. We want to color K6 with blue and red and show that such two-coloring on K6 always results in either a blue or a red triangle.
Proof: Pick any vertex vi in K6. We know that vi is connected to all the other five vertices with five distinct edges. From those five edges of vi at least three are of the same color. For example, suppose that there are three blue edges connected to vi. Since we are in K6 these edges are also connected to another set of three edges, which implies that: (i) All of our three edges are red or (ii) there is at least one of them which is blue. In case (i) we have a red triangle. In case (ii) we have a blue triangle.
Note: This is a classic application of the pigeonhole principle.