Party Mutual Recognition Issues Brief.
This is an automatically translated post by LLM. The original post is in Chinese. If you find any translation errors, please leave a comment to help me improve the translation. Thanks!
A few days ago, the first "Game in Chang'an" event organized by four rotating chairpersons officially came to an end. There was a grouping problem in a small game during the event, and I will record it here.
Background of the Name Calling Game
Here's the situation: the event was organized by four rotating chairpersons, who invited their first-degree friends (direct friends) and second-degree friends (friends of friends) to participate. Therefore, for each participant, there were always some people they didn't know. And the number of unknown people for each person was different. The total number of participants in the event was about 14.
Therefore, we used the following process to help everyone remember each other's names:
- All participants were divided into two groups equally.
- The name calling game was played within each group.
- All participants were divided into two groups equally again.
- The name calling game was played within each group.
Name calling game1:
- Choose a wide and flat game field.
- The team members stand in a circle as a group. Each person is about an arm's length apart. You, as the training instructor, are no exception.
- Tell the group that the game will start from you. Shout out your own name and then pass the ball to the person on your left. The teammate who receives the ball should do the same, shout out their own name, and then pass the ball to the person on their left. This continues until the ball returns to your hands.
- After you get the ball back, tell everyone that we are going to change the rules now. The teammate who receives the ball must shout out another teammate's name and then throw the ball to that teammate.
- After the game ends, before disbanding the group, invite a volunteer to walk around the group and say the name of each person.
Initially, we hoped that by optimizing the grouping in these two rounds, everyone would get to know each other. However, during the optimization process, we found that this problem was not as simple as we expected. Therefore, in the practical process, we added another step: all participants played the name calling game together to achieve the goal of getting to know each other.
The Name Calling Problem
The problem described above is what I call the "name calling problem" during the gathering. It can be abstracted as a graph theory problem in mathematics, described as follows:
Given an initial graph with \(2n\) vertices, we can perform a \(\Gamma\) operation (dividing the \(2n\) vertices into two parts and fully connecting the \(n\) vertices in each part). If we want to fully connect the \(2n\) vertices after two \(\Gamma\) operations, how should we group them in these two \(\Gamma\) operations?
Does a Solution Exist?
Of course, the above description is a mathematical description of the problem we encountered. Obviously, whether this problem has a solution depends on the initial graph formed by these \(n\) vertices. Therefore, we need to explore the existence of a solution:
Given an initial graph with \(2n\) vertices, we can perform a \(\Gamma\) operation (dividing the \(2n\) vertices into two parts and fully connecting the \(n\) vertices in each part). If there exist two \(\Gamma\) operations that fully connect the \(2n\) vertices after the two operations, what conditions should the initial graph satisfy?
Firstly, a fully connected graph formed by \(2n\) vertices contains \(\frac{2n(2n-1)}{2}=2n^2-n\) edges. Each \(\Gamma\) operation establishes a full connection between the \(n\) vertices divided into two groups, which means adding no more than \(\frac{n(n-1)}{2}*2=n^2-n\) edges. Performing two \(\Gamma\) operations adds no more than \(2n^2-2n\) edges. From this, we obtain a necessary but not sufficient condition for an optimal initial graph:
- The initial number of edges should be no less than \(n\).
If Two Operations Are Not Enough, How Many \(\Gamma\) Operations Are Needed at Least?
In addition, in this scenario, due to time constraints, only a small number of games can be played to establish edges in the graph. If there were no time constraints, it would be worth discussing how many such games are needed at least to establish a full connection among any arbitrary graph:
Given an initial graph with \(n\) vertices, we can perform a \(\Gamma\) operation: dividing the \(n\) vertices into two parts and fully connecting the \(n/2\) vertices in each part. How many \(\Gamma\) operations are needed at least to establish a full connection among these \(n\) vertices?
How Are the Groups Formed in Each \(\Gamma\) Operation?
Finally, the fundamental problem is the algorithm for solving this:
Given an initial graph with \(n\) vertices, we can perform a \(\Gamma\) operation: dividing the \(n\) vertices into two parts and fully connecting the \(n/2\) vertices in each part. How many \(\Gamma\) operations are needed at least to establish a full connection among these \(n\) vertices? And provide all the groupings in each \(\Gamma\) operation.