Based on real life experience, I just considered the following combinatorial challenge:

In a workplace with currently $n$ employees each employee has its own unique 4-digit code used to pass through certain doors at certain times of day. Tomorrow $r$ new employees will start working there and each must fill in a form suggesting two different 4-digit codes. They have no knowledge of each others codes or the $n$ current employee's codes. When everyone has filed their forms, it is attempted to assign each new employee one of their suggested codes so that all $n+r$ persons working there have unique codes.

For simplicity, let us assume that the new employees choose their two different 4-digit suggestions uniformly at random. Then what is the probability $P(n,r)$ that the workplace is unable to assign unique codes to all the new employees?

  • 3
    $\begingroup$ If you have no information about how primary and secondary codes will try to be assigned, then your question is ill-defined. Also, if you assume there is some weird unknown distribution as to how employees choose their desired codes, it's ill-defined. If you assume that the 2 codes chosen by a new employee are independent draws from the 4-digit possibilities (without replacement, i.e. they don't choose the same code twice), and that a satisfying assignment to employees' 2 choices is always made if possible, then probably you can get tight asymptotics on your overall desired probability. $\endgroup$ – user2566092 Aug 6 '15 at 22:01
  • $\begingroup$ @user2566092: I have tried to clarify a bit, but what I mean is your last suggestion, namely two 4-digit codes chosen without replacement. How can I make that become clearer? $\endgroup$ – String Aug 6 '15 at 22:23
  • $\begingroup$ now your question seems more tractable. Since the 2 employee suggestions are now uniform at random (without replacement), and there is no policy about how to assign "first choice" vs. "second choice" for an employee, your answer will now solely be a function of how many codes have already been assigned and how many new employees there are. An interesting problem, and I'm not sure if there will be an exact formula for you, maybe just "asymptotics" that explain how the success probability grows as a function of the number of taken codes and the number of new employees. $\endgroup$ – user2566092 Aug 6 '15 at 22:40
  • 1
    $\begingroup$ Concerning the protocol: Are codes assigned in the order the new employees show up, or does the person assigning the codes see all $2r$ new proposals before assigning any codes that day? $\endgroup$ – Christian Blatter Aug 9 '15 at 15:14
  • $\begingroup$ @ChristianBlatter: Oh my, what a relevant question! All $2r$ codes are collected first. $\endgroup$ – String Aug 9 '15 at 16:06

Here's a lower bound for $P(n,r)$, for starters. First let's exclude nonsensical and trivial situations: The number of $4$-digit codes is $10^4$. The number of codes in use $n$ is an integer between $0$ and $10^4$. The number of new employees $r$ is an integer between $0$ and $10^4-n$.

Enumerate the new employees $e_1,\ldots,e_r$. Suppose the workplace is able to assign a unique code to each of the $r$ new employees. Let $(c_1,\ldots,c_r)$ be such an assignment. Then employee $e_i$ has chosen code $c_i$, and some other $c_i'$ which could be any other code. The probability of this happening for all employees is $$\left(\frac{1}{10^4}\cdot\left(1-\frac{1}{10^4}\right)\right)^r.$$ Summing the probabilities for all valid assignments of codes yields an upper bound of $$\frac{(10^4-n)!}{(10^4-n-r)!}\cdot\left(\frac{1}{10^4}\cdot\left(1-\frac{1}{10^4}\right)\right)^r,$$ on the probability that there exists a valid assignment of codes. So the probability that the workplace cannot assign a valid set of codes is at least $$P(n,r)\geq1-\frac{(10^4-n)!}{(10^4-n-r)!}\cdot\left(\frac{1}{10^4}\cdot\left(1-\frac{1}{10^4}\right)\right)^r.$$

  • $\begingroup$ While I like this answer and upvoted it, I still believe it to be a rough estimate/bound and as such not merely a full answer to the question. Perhaps if you could convince me that this bound is tighter than I might have thought, I would consider awarding you the full bounty. If not, you will be awarded half of the bounty when the grace period ends. I like your answer, make no mistake about that :) $\endgroup$ – String Aug 16 '15 at 20:25

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.