[Combinatorics] The “Loving Circle” — What size is the final group most likely to have?
I came up with this problem while thinking about random directed graphs and recursive selection processes. I’m particularly interested in whether there is a clean pen-and-paper solution rather than brute-force enumeration.
PROBLEM
There are 10 people in a room. One person, A, is chosen as the initial person.
Whenever a person is asked, they choose exactly 2 distinct people from the other 9 people. Each of the 36 possible pairs is equally likely.
Initially, only A is asked.
The process then works recursively:
- The two people chosen by A are asked next.
- Whenever a person is chosen for the first time, that person is subsequently asked to choose their own two people.
- A person who has already been asked may be chosen again, but is not asked again.
- The process stops when no new person is discovered.
Let K be the total number of distinct people who have been asked, including A.
For example, if A chooses B and C, and eventually the only people ever reached are A, B, C, D, E, then K = 5.
QUESTION
Determine the value of k for which P(K = k) is maximal.
In other words:
How many people is the final group most likely to contain?
Give a rigorous proof.
CLARIFICATIONS
- The two people chosen by any person form an unordered pair. Thus choosing {B,C} is the same as choosing {C,B}.
- A person cannot choose themselves.
- Choices made by different people are independent.
- A person is asked only once, namely when they are first discovered.
- The order in which newly discovered people are subsequently asked is irrelevant.
- The initial person A is fixed for the purpose of the problem. Since all 10 people are symmetric, choosing the initial person randomly would not change the distribution of K.
- No computer or simulation should be necessary.
INTENDED LEVEL / CHALLENGE
I am aiming for this to be around USANMO-level combinatorics, or at least to require comparable problem-solving and observation rather than routine counting.
I’m especially interested in whether there is an elegant way to attack the probability distribution without simply enumerating every possible configuration.
Please try to solve it with pen and paper before using computational enumeration.
No LLM-generated solutions, please. I’d much rather see a genuine human solution or approach, even if incomplete.
Suggested time limit: around 2–3 hours for a serious attempt.
I’m also interested in feedback on:
- whether the problem is actually at the claimed level;
- whether the statement contains any ambiguity;
- whether there is a substantially cleaner solution than brute-force enumeration.
