19
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

Note: This is NOT a full answer; just two upper specific bounds.


Let $f(k)$ denote the greatest value of $n$ for which a good order is guaranteed to exist. Then:

We have $f(2)<6$, since the friendship graph consisting of three pairs of people: {0,1}, {2,3} and {4,5}, where each person from each pair is friends with each person from the next pair (with last pair wrapping back to the first one) admits no good order. More explicitly:

  0 => [2,3];  1 => [2,3];  2 => [4,5];  3 => [4,5];  4 => [0,1];  5 => [0,1]

This graph is nicely regular, which simplifies the analysis considerably. Without loss of generality, the first person in line is person $0$. Its two friends, $2$ and $3$ must be placed right behind (their relative order doesn't matter; it can be $2$ without loss of generality). However, this means at least one of their friends ($4$ and $5$) would be too far to be heard.


We also have $f(3)<9$, as demonstrated by the following friendship graph (with persons numbered $0$ to $8$) in which every person is friends with the next one (wrapping back from $8$ to $0$), plus the following friendship relations:

  0 => 5; 1 => 7; 2 => 0;   3 => 8; 4 => 1; 5 => 3;   6 => 2; 7 => 4; 8 => 6

Unfortunately, I have not managed to represent this graph in a very neat, regular structure like the previous one (although it can still look relatively nice if represented as a $3\times 3$ grid). As such, I have not managed to produce an easy proof of its desired no-good-order property; having only verified it via computer-based exhaustive search (which, of course, could have been implemented incorrectly; feel free to verify it independently).


A wild extrapolation might suggest $f(k)<3k$, although this is only a very wild guess.

$\endgroup$
2
  • $\begingroup$ I also thought of writing a computer-based search program to check the simple cases. Is your program easy to extend to other test-cases? $\endgroup$ Commented Aug 16, 2016 at 14:37
  • $\begingroup$ My current program works by performing exhaustive search over possible orderings (for a chosen friendship graph), so its complexity is super-exponential in $n$ and thus can't get much further than $n=10$ or $11$. I will see if I can do something smarter and get further bounds on the values. $\endgroup$ Commented Aug 16, 2016 at 15:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .