Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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|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

 
discard

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.