I was given a problem today that I believe is way too far over my head to make any progress on. Even the professor who posed the question did not have an answer.
The “Friends” Game
Suppose you have a group of $n$ people standing randomly. Everyone picks two people other than themselves and calls them their “friends”. We call this set of choices a setting. Now, after everyone has secretly chosen their two friends, they all move, trying to be equidistant from the two friends they chose. Once everyone is equidistant from their two friends, and everyone has stopped moving, this is called a stable configuration.
Questions:
How many settings are there for $n$ people?
Does every setting of $n$ people guarantee a stable configuration? Are there settings that have no stable configuration?
I tried solving this with induction (weak and strong), and even attempted a proof by contrapositive and contradiction, but I could not make any meaningful progress.
The only thing we have found so far is that for $n=4$ people, there are $4$ settings. That is, four configurations of ways people can choose friends. We haven’t found a way of figuring out how many settings there are for 5 or more people without brute force.
I thought I’d pose this in hopes someone has seen (or knows an equivalent “translation” to) this problem, or can make more progress than a couple of undergrads and professor could muster.
I believe there are ways tools in combinatorics and graph theory that I do not yet possess, so I hope someone here can solve this.
EDIT: I seem to have not given enough information.
The purpose is to determine whether for all given settings there exists a stable configuration for it. It is not necessary to show how one finds it, however that may be used in a proof for it.
Also, I should clarify that when for n=4, I found a total of 4 groups of settings, each group is isomorphic up to the configuration of people. So a setting of four people is considered the same if you can permute the “names” of each point, as long as the relations stay the same. I will link a picture of all four settings for n=4, where only the relations between people matter, not what you label them. We used a directed graph to represent the settings. The relations stay the same when you permute the “name” of each point.
As an approach to settle the second question, identity the 2D positions of the people with complex numbers in the Argand diagram. Then the locus of points which are equidistant from $A$ and $B$ is $P(t) = \frac{A+B}{2} + it\frac{A-B}{2}$. We can set up simultaneous linear equations of the form $C_k = \frac{A_k+B_k}{2} + it_k\frac{A_k-B_k}{2}$. Then for each $k$ we just need to choose $t_k$ such that we don't get an equation which is linearly dependent on the previous ones. This must be possible unless both $\frac{A_k+B_k}{2}$ and $\frac{A_k-B_k}{2}$ are linearly dependent on the previous equations.
All of this suggests that if you want to find settings with no stable configuration then you should look at settings where lots of people choose the same friends.