Problema de combinación de código de dígitos

Question

Basado en la experiencia de la vida real, yo sólo considera el siguiente problema combinatorio:

En un puesto de trabajo que actualmente se $n$ empleados que cada empleado tiene su propio y único código de 4 dígitos que se utiliza para pasar a través de algunas puertas en determinados momentos del día. Mañana $r$ nuevos empleados comenzará a trabajar allí, y cada uno debe llenar un formulario lo que sugiere dos diferentes 4 dígitos. No tienen ningún conocimiento de cada uno de los otros códigos o $n$ empleado los códigos. Cuando todo el mundo ha presentado sus formas, se intentó asignar a cada nuevo empleado de uno de sus sugirió códigos, de manera que todos los $n+r$ de las personas que trabajan allí tienen códigos únicos.

Por simplicidad, supongamos que los nuevos empleados elegir a sus dos diferentes de 4 dígitos sugerencias uniformemente al azar. Entonces, ¿cuál es la probabilidad de $P(n,r)$ que el lugar de trabajo es incapaz de asignar códigos únicos para todos los nuevos empleados?

Answer 1

He aquí un límite inferior para $P(n,r)$, para empezar. Primero vamos a excluir disparatados y situaciones triviales: El número de $4$dígitos de los códigos de es $10^4$. El número de códigos en uso $n$ es un número entero entre el$0$$10^4$. El número de nuevos empleados $r$ es un número entero entre el$0$$10^4-n$.

Enumerar los nuevos empleados $e_1,\ldots,e_r$. Supongamos que el lugar de trabajo es capaz de asignar un código único a cada una de las $r$ nuevos empleados. Deje $(c_1,\ldots,c_r)$ ser de dicha cesión. Luego de empleados $e_i$ ha elegido el código de $c_i$, y algunos otros $c_i'$, lo que podría ser cualquier otro código. La probabilidad de que esto ocurra para todos los empleados $$\left(\frac{1}{10^4}\cdot\left(1-\frac{1}{10^4}\right)\right)^r.$$ Suma de las probabilidades de todas validez de las asignaciones de códigos de los rendimientos de un límite superior de $$\frac{(10^4-n)!}{(10^4-n-r)!}\cdot\left(\frac{1}{10^4}\cdot\left(1-\frac{1}{10^4}\right)\right)^r,$$ en la probabilidad de que no existe una asignación válida de códigos. Así que la probabilidad de que el lugar de trabajo no puede asignar un conjunto válido de los códigos es al menos $$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.$$