Rules: A conveyor belt is giving you little boxes. They are labeled for your convenience: Box $1$, Box $2$,... For your inconvenience, though, you can't see the number (from $1...n$) hidden in it. You can sort the boxes into $n$ bins as you like. You may pause the belt at any time to resort the boxes. As soon as one bin contains a minimum of $k$ boxes (or more, doesn't hurt) all with the same number in it, and no other number in that bin, a siren goes off and you are declared programmer of the month. :-)
Here is a very stupid but surefire algorithm: Fetch at least $n(k-1)+1$ boxes and try out all permutations with $k$ boxes in bin 1 and $k-1$ in the rest of bins, in any order.
I guess you can do better than $O((nk)!)$?