0
$\begingroup$

In the circle, groups are chosen randomly and secretly by each person, *only rule being that no one chooses either of the two people standing directly next to them in the original circle. No planning or direction by vocal communication, only allowed to move and see who moves to stay equidistant from you. Will there always be an optimal distribution so that all are equidistant from the two others in their randomly chosen group?

EDIT:

Mees De Vrees has pointed out an easy solution is just for each person to pick the two people two slots away from them in the original circle. But I am more interested in if there will always be an optimal position for each person so that, even with the random initial choices, everyone can choose a spot equidistant from their two choices.

$\endgroup$
  • $\begingroup$ For clarification: "A is in B's group" does not generally imply that "B is in A's group"? And, do the people actually get to choose or do they pick/get two others in the circle (besides their direct neighbour) randomly? $\endgroup$ – Mees de Vries Sep 20 '16 at 20:51
  • $\begingroup$ Yes to the first point. The group are chosen individually by each member, secretly. Only rule being they can't choose the person next to them in the original circle $\endgroup$ – D. W. Sep 20 '16 at 20:52
  • $\begingroup$ Each person chooses two others while standing in the original circle, but the people they choose do not necessarily have to choose them too $\endgroup$ – D. W. Sep 20 '16 at 20:53
  • $\begingroup$ So they can just all choose the two people who are two away from them in the original circle? $\endgroup$ – Mees de Vries Sep 20 '16 at 20:53
  • $\begingroup$ Yes they could do that $\endgroup$ – D. W. Sep 20 '16 at 20:54
0
$\begingroup$

This is not always possible. Suppose that the people have picked groups such that we can number the people $1,\ldots,k$ in such a way that for $1 < i < k$, the group of $i$ contains ${i-1}$ and ${i+1}$; such that the group of $1$ consists of $k$ and $2$, and the group of $k$ consists of $k-1$ and $2$. That is, they almost form a kind of circle, except $k$ has chosen $2$ instead of $1$.

Now suppose towards a contradiction that an optimal solution exists: then the distance of $k$ to $1$ should equal the distance $1$ to $2$, which should equal the distance $2$ to $3$, and so on, which should equal the distance $k-1$ to $k$, which should equal the distance $k$ to $2$. But then $k$ is equidistant from $1,2,k-1$, which is impossible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.