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.
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.