¿Debo tener un dígito repetido en un $4$ -¿Código pin de un dígito?

Question

Una pequeña discusión que teníamos mi colega y yo...

Digamos que tengo un $4$ -de seguridad de mi alarma antirrobo, y soy demasiado vago para cambiarlo. Con el tiempo, los dígitos correspondientes se desgastan.

Si he utilizado $4$ diferentes dígitos (como es común, por ejemplo $1357$ ), entonces un atacante, sabiendo que esos son los dígitos del código, necesita (¡si estoy en lo cierto!) $24$ va a probar todas las combinaciones.

Si he repetido una cifra (por ejemplo $1317$ ), el atacante sólo sabe $1$ , $3$ y $7$ se utilizan (se supone que todo el desgaste es indistinto). ¿Cuántos posibles $4$ -¿son posibles los códigos de dígitos, utilizando cada dígito al menos una vez? Yo digo que es más que $24$ Pero mi colega está convencido de lo contrario.

Un premio extra por generalizar el problema para saber $k$ dígitos en un $n$ -de dígitos. ;)

Answer 1

Si el ladrón sabe qué dígito se repite, tiene \begin{equation*} \dfrac{4!}{2!} = 12 \end{equation*} códigos para probar. Como no sabe qué dígito se repite, tendrá que probar $3 \cdot 12=36$ diferentes códigos.

Answer 2

Me gusta mucho ese problema, es muy visual y fácil de entender. Voy a mostrar el caso de una longitud de código de $n$ donde $l<n$ Los dígitos se repiten exactamente dos veces. Esto hace un total de $k = n-l$ diferentes dígitos. (es decir, para su pregunta en particular, por favor, establezca $n=4$ , $l=1$ .)

Dado $n$ diferentes dígitos sin repetición, tienes $n!$ formas de ordenarlas. Es un problema bastante básico.

Ahora suponga que todavía tiene $n$ dígitos, pero $l$ Los "marcados" se repiten dos veces. (es decir, el atacante sabe qué dígito duplicas) Esto reducirá sus posibilidades en un factor de $2^k$ .

¿Por qué? Su conjunto de números parece $\{1_1,1_2,2_1,2_2,...,l_1,l_2,l+1,l+2,...,n-l=k\}$ . Eso es todavía $n$ porque el primer $l$ se duplican. Al ordenar los que tenemos $n!$ opciones, porque podemos ver esos pequeños índices. Pero la alarma antirrobo no puede, ¡estamos contando demasiadas posibilidades! Tenemos que calcular la frecuencia con la que se ha contado cada posibilidad y ajustarla. Cada par de números duplicados $j_1, j_2$ (aquí $j\leq l$ ) podría colocarse como $..,j_1,..,j_2,..$ o al revés, como $..,j_2,..j_1,..$ lo que le da dos posibilidades en total. Como el cambio es independiente, tenemos que multiplicar todos esos dos juntos.

El último paso tiene en cuenta al ladrón, que no sabe qué dígitos se duplican. Tendrá que probar cada posible subconjunto con $l$ elementos. Esto se conoce como el coeficiente binomial $n\choose l$ . En total esto nos da:

$${n \choose l} \cdot \frac{n!}{2^l}$$

Tenga en cuenta que $2^l$ crece más rápido que $n \choose l$ Pero los últimos comienzan con una cantidad inicial más alta. En conclusión: Un pequeño número de llaves duplicadas es sensato, dependiendo de su $n$ . Pero asegúrate de no duplicar demasiados.

Answer 3

Tu pregunta de "usar cada dígito al menos una vez" es un poco confusa, porque deberías enfatizar que no obstante hay $3$ diferentes dígitos involucrados, todos los cuales son conocido al atacante.

Habiendo enfatizado esto, el atacante tiene un total de $36$ posibles combinaciones:

 Digit #1 occurs | Digit #2 occurs | Digit #3 occurs | Combinations
-----------------|-----------------|-----------------|--------------
 1 time          | 1 time          | 2 times         | 12
-----------------|-----------------|-----------------|--------------
 1 time          | 2 times         | 1 time          | 12
-----------------|-----------------|-----------------|--------------
 2 times         | 1 time          | 1 time          | 12

---

Cada caso puede ser calculado de cualquiera de las siguientes maneras:

• $\binom41\cdot\binom31\cdot\binom22=12$
• $\binom41\cdot\binom32\cdot\binom11=12$
• $\binom42\cdot\binom21\cdot\binom11=12$

Answer 4

Esta es mi respuesta para un código de longitud $n$ utilizando $k$ diferentes dígitos que pueden repetirse con una frecuencia arbitraria. Cada dígito debe aparecer al menos una vez. (de lo contrario, no se gastará).

Para ello se utiliza la secuencia correspondiente " A019538 " que Barry Cipra mencionado.

Ahora bien, hacer referencia a la OEIS está muy bien, pero si no eres un matemático lo más probable es que esa página sea bastante confusa. Tiene un montón de comentarios que parecen apuntar a un significado diferente. Ninguno de esos significados en el que realmente tenemos. (El "Número de $k$ caras" dimensionales del $n$ El "permutoedro dimensional" no se parece en absoluto a los números de un teclado... (¿Y qué es un permutoedro?)

Aquí tenemos una formulación que podemos convertir en un teclado: "Número de proyecciones (sobre funciones) de un $n$ -elemento fijado en un $k$ -conjunto de elementos".

¿Qué es una "sobreproyección de un $n$ -elemento fijado en un $k$ -¿"Conjunto de elementos"? Es una asignación que asigna uno de $k$ números cada uno de $n$ lugares. Los números pueden aparecer con una frecuencia arbitraria y la "suryección" nos dice que cada $k$ los elementos deben ser elegidos al menos una vez. ¡Genial! Eso es exactamente lo que buscamos. Cada posición $n$ posiciones del código se asigna una de $k$ llaves desgastadas y cada llave se recoge al menos una vez.

Estamos en la página correcta de la OEIS, obtengamos una fórmula. (Hay muchas) $$T(n, k) = k*\left(T(n-1, k-1)+T(n-1, k)\right) \text{ with } T(0, 0) = 1$$ No se trata exactamente de una fórmula de "introduce tus números y obtén un resultado", pero con una pequeña tabla obtener un valor es bastante fácil. Y resulta que esta fórmula es fácil de explicar.

En primer lugar, ¿por qué $T(0,0) = 1$ ? Esto cuenta las formas de introducir un código de longitud $0$ sin usar dígitos. Suena un poco loco si ves esto la primera vez, pero hay exactamente una manera de hacerlo: Quédate ahí y no hagas nada.

Ahora bien, ¿dónde está el $T(n, k) = k*\left(T(n-1, k-1)+T(n-1, k)\right)$ ¿de dónde viene? En primer lugar, tenemos $k$ diferentes posibilidades. ¿Qué pasa con los otros $n-1$ lugares que siguen? Lo dividimos en dos casos:

• El primer dígito no se vuelve a utilizar. Luego hay $T(n-1, k-1)$ formas de rellenar el último $n-1$ dígitos con $k-1$ números.
• El primer dígito se utiliza de nuevo. Hay $T(n-1, k)$ formas de rellenar el último $n-1$ dígitos con $k$ números.

En resumen, eso nos da $T(n-1, k-1)+T(n-1, k)$ formas de rellenar el último $n-1$ lugares tiempos $k$ formas de rellenar el primer dígito.

A continuación se presentan algunos valores que también fueron amablemente facilitados por la OEIS:

n\\k 1    2     3      4       5        6        7        8        9
1:  1
2:  1    2
3:  1    6     6
4:  1   14    36     24
5:  1   30   150    240     120
6:  1   62   540   1560    1800      720
7:  1  126  1806   8400   16800    15120     5040
8:  1  254  5796  40824  126000   191520   141120    40320
9:  1  510 18150 186480  834120  1905120  2328480  1451520   362880

En conclusión, si utiliza una longitud de tres a seis, duplique un solo dígito. Para el siete, el ocho y el nueve debes usar dos menos y si usas códigos aún más largos, pide ayuda de codificación en stackoverflow.

Espero que eso ayude.

Answer 5

Si
$n$ ...el número total de dígitos,
$k$ ...el número de los mismos dígitos.
entonces el número de opciones diferentes (y números) $c$ es igual a:
$$c=\binom{n}{k}\cdot (n-k)!$$ y por la $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ el $c$ puede simplificarse:
$$c=\frac{n!}{k!}$$ Para $n=4$ [dígitos], y $k=1$ (todos los números son diferentes): $c=\frac{4!}{1!}=24$ ,
para $n=4$ [dígitos], y $k=2$ [los mismos números]: $c=\frac{4!}{2!}=12$ ,
para $n=4$ [dígitos], y $k=3$ [los mismos números]: $c=\frac{4!}{3!}=4$ ,
y para $n=4$ [dígitos], y $k=4$ (4 los mismos números): $c=\frac{4!}{4!}=1$ .
Si tiene $n$ dígitos que contienen $k$ los mismos números, entonces puede crear $\binom{n}{k}$ combinaciones que representan diferentes patrones numéricos (donde cada uno contiene (n-k) posiciones vacías). Las (n-k) posiciones restantes pueden contener cualquier permutación de números restantes. Por ejemplo, para los números $1,1,3,4$ Esto significa que $n=4$ y $k=2$ puedes crear $\binom{4}{2}=6$ estos diferentes patrones:
1) $1,1,-,-$ ;
2) $1,-,1,-$ ;
3) $1,-,-,1$ ;
4) $-,1,1,-$ ;
5) $-,1,-,1$ ;
6) $-,-,1,1$
Ahora para cada combinación se puede reemplazar el par de $-$ con la permutación de dos números restantes, esta media $3,4$ o $4,3$ . Para la primera combinación $1,1,-,-$ : $1,1,3,4$ y $1,1,4,3$ . Y, por lo tanto, $6\cdot{2}=12$ .