2
$\begingroup$

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)!)$?

$\endgroup$
  • 1
    $\begingroup$ The algorithm you describe already does a bit better than $\mathcal O((nk)!)$, actually -- and of course the order of the boxes in the rest of the bins doesn't matter, so if you avoid repeating the same elements in the bin 1, you get down to $\mathcal O\left(\binom{n(k-1) + 1}{n}\right)$. You could probably do a small bit better (by using other bins), but I would be surprised if you could do much better; the method gives you no 'partial information' at all. $\endgroup$ – Mees de Vries Apr 15 '19 at 13:32
  • $\begingroup$ @MeesdeVries: I think you need $k$ on the bottom of that expression, not $n$. This is much better than $O((nk)!)$ :) $\endgroup$ – j_random_hacker Apr 15 '19 at 15:45
  • $\begingroup$ If the number of all boxes is $n(k−1)+1$, then $\binom{n(k-1) + 1\ \ }{k}$ number of tries is needed in the worst case. That can be shown by a simple adversary argument. $\endgroup$ – John L. Apr 15 '19 at 16:25
  • $\begingroup$ "You can sort the boxes into $n$ bins as you like". What is the significance of $n$? All comments above stay the same if we have only 1 bin. Is the following an equivalent story? "You are given infinitely many distinct boxes. Each of them contains a number from 1 to $n$, which you cannot see. You can select any $k$ boxes to put into a testing bin. If all $k$ boxes have the same number, a siren goes off and you are declared programmer of the month. Otherwise, you can try again with another set of $k$ boxes. What is the minimum number of tries in which you can make sure the siren will go off?" $\endgroup$ – John L. Apr 16 '19 at 1:09
  • $\begingroup$ In my story above, only $k$ boxes are considered since putting more than $k$ boxes in the testing bin cannot improve the situation. $\endgroup$ – John L. Apr 16 '19 at 1:11

Your Answer

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

Browse other questions tagged or ask your own question.