$n$ people have to be ordered in a line, one after the other. We say that:
- A person X sees a person Y, if X stands behind Y.
- A person X hears a person Y, if X stands at most $k$ positions in front of Y.
Each person has two friends (friendship relation is not symmetric).
An order is good if each person either sees or hears both his/her friends
What is the largest value of $n$ (as a function of $k$) for which a good order always exists?
Here are some examples.
When $n\leq k+1$, a good order always exists, since each person can see or hear all other people.
When $k=1$ and $n\geq k+2$, a good order never exists, since the front person sees nobody and hears at most a single friend.
When $k=2$ and $n=4$. a good order always exists and can be found as follows. Put an arbitrary person (e.g. Alice) in the front. Put her two friends just behind her, so that she can hear both of them. Put the fourth person at the back.
When $k=2$ and $n=5$, things are getting interesting. Suppose we put Alice in the front, and her friends are Bob and Carl. So the order has to start as either Alice-Bob-Carl or Alice-Carl-Bob. But, if Bob's friends are David and Eva and Carl's friends are also David and Eva, then one of them (the one just behind Alice) will not hear both his friends.
We can try to put Bob at the front, then David and Eva. But, if both David's friends and Eva's friends are Alice and Carl, then one of them (the one just behind Bob) will not hear both his friends.
In that case, we can order the agents as: Carl-David-Eva-Alice-Bob; this order satisfies all the requirements.
Apparently, finding a good order becomes harder when $n$ is larger. Hence the question.
UPDATE 1: when $n\leq 2k$, a good order always exists. Put an arbitrary agent (say, Alice) in the front. Put one of her friends (say, Bob) just behind her. Put one of Bob's friends (say, Carl) just behind him. Continue like this until $k$ people are placed. Then, at position $k+1$, put Alice's second friend (if not already placed). At position $k+2$, put Bob's second friend (if not already placed), and so on. So the people at positions $1,\dots,k$ can hear all their friends. Since $n\leq 2k$, the people at positions $k+1,\dots,2k$ can hear everyone behind them. Hence the order is good.
This seems very not tight, since we just picked the front person arbitrarily. Surely we can do better by picking the front person more carefully, right?
UPDATE 2: Based on Kevin's probabilistic argument, I tried the following counting argument. The friendship relation can be roughly represented by a vector of size $2n$. For each 2 positions in the vector, there are $(n-1)(n-2)$ options, so the total number of vectors is $\approx n^{2n}$. On the other hand, the total number of orderings is $n!$. Therefore, if we could prove that each order is good for less than $n^{2n} / n!$ vectors, then this would imply that some vectors have no good orders.
Unfortunately, the latter claim is probably not true. Fix an order, and renumber the agents such that the order is $1,\dots,n$. To construct a vector for which this order is good, we have $k(k-1)$ options for the friends of person 1, $(k+1)k$ options for the friends of person 2, ..., $(n-2)(n-1)$ options for the friends of person $n-k$, and $(n-2)(n-1)$ options for the friends of the remaining people $n-k,\dots,n$. Multiplying all these numbers gives much more than $n^{2n} / n!$. So this counting argument does not work.
UPDATE 3: This question is related: How many nodes do you need? If our friendship graph if $k$-dense (as defined in that question), then a good order does not exist. Proof: regardless of who we put in the first $k$ locations, these $k$ people have together $k+1$ friends besides themselves. So, one of these people will not hear one of his friends. So a lower bound of $n$ in that question implies an upper bound of $n-1$ in the current question. In particular, for $k=2$, there is a 2-dense graph with 7 nodes; hence the largest number of people for which a good order exists is at most 6 (Peter showed a better upper bound: 5).
