Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose I have an alphabetized list of n people, and I want to choose k from the list such that any two people are at least g away from each other on the list

(E.g if g=2, then none of the k people are next to each other on the list).

Is there a formula / general way to solve these types of problems, for any k,n, and g?

share|cite|improve this question
up vote 1 down vote accepted

The problem has a solution only if \ceiling$(n/g)>=k$.

Form a directed graph with each of the $n$ people a ode. Put a directed edge $(u,v)$ whenever $v$ is at least $g$ positions after $u$ in the dictionary. Run a graph traversal algorithm starting at each one of the first $g$ nodes. Each resulting path with length $k-1$ is an answer.

share|cite|improve this answer
Thanks! Is there a closed form solution for this? – user1526710 Dec 13 '12 at 22:28
Yw, Glad it helped. I don't think there is. It is a recursive solution. The algorithm would be the solution "formula" itself. There is a lengthy closed form for its count though and I haven't figured it-- yet. – ashley Dec 13 '12 at 23:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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