¿Cuántas posibilidades diferentes hay?

Question

Estaba haciendo este genial juego de rompecabezas de la vida real en Shanghai, China. Funciona así:

Tú y un grupo de amigos estáis encerrados en una habitación juntos -sin smartphones, sin cámaras- y vuestra tarea es salir. Una de las preguntas era un rompecabezas numérico para desbloquear un teclado digital.

Esto es lo que decía:

El código contiene sólo estos números (pero debe utilizarlos todos) $4, 6, 9$

Es un $6$ código de dígitos.

El código termina en $4$ .

$4$ y $9$ nunca son consecutivos.

La respuesta correcta era $4,6,6,9,6,4$ .

Creo que he tenido suerte al conseguir el código correcto. Así que mi pregunta es la siguiente:

¿Cuántas posibilidades diferentes hay?

Gracias.

Answer 1

Dejemos que $N_{a,b}$ sean los códigos de longitud $a$ que terminan en $b$ y no tienen adyacentes $4$ y $9$ 's. Cada código de longitud $a$ que termina con $b$ puede extenderse de forma única a un código de longitud $a+1$ que termina en $c$ , a menos que $(b,c)=(4,9)$ o $(9,4)$ . Así que $$ N_{a+1,4}=N_{a,4}+N_{a,6} \\ N_{a+1,6}=N_{a,4}+N_{a,6}+N_{a,9} \\ N_{a+1,9}=N_{a,6}+N_{a,9}, $$ o $$ N_{a+1}=\left(\begin{array}{ccc}1 & 1 & 0\\1 & 1 & 1\\0 & 1 & 1\end{array}\right)\cdot N_{a} $$ en una notación matricial, donde $N_{0}=(1,1,1)^{t}$ . Uno encuentra que $N_6=(169,239,169)^t$ , por lo que hay $169$ códigos de seis números que terminan en $4$ . Tenemos que restar los códigos de este tipo que no utilizan los tres números ya que $4$ y $9$ no pueden ser adyacentes, son sólo aquellos códigos que contienen $4$ y $6$ de los cuales hay $2^5=32$ terminando en $4$ . El resultado es $169-32=137$ .

Answer 2

Como obtuve dos respuestas diferentes (una de 38 y otra de 137) decidí escribir un programa para averiguar la respuesta a través de adivinar y comprobar. Obtuve la respuesta de 38.

#!/usr/bin/perl

## The code contains only these numbers (but must use them all) 4,6,9
## It is a 6 digit code.
## The code ends in 4.
## 4 and 9 are never consecutive.

$n = 10000;
$total = 0;
until ($n eq 99999)
{
    $n++;

    # make sure it only contains 4,6,9
    next if ($n =~ m/0|1|2|3|5|7|8/);

    # make sure it countians 6 & 9 (4 is already included)
    next if ($n !~ m/6/);
    next if ($n !~ m/9/);

    # make sure 4 & 9 are never consecutive
    next if ($n =~ m/49/);
    next if ($n =~ m/94/);

    # make sure 9 & 4 are never consecutive (Because we arent looking at the 4)
    next if ($n =~ m/9$/);

    print $n . "4\\n";
    $total++;

}

print "\\n\\nTotal: $total\\n";  

SALIDA

446964
466964
469644
469664
469964
646964
666964
669644
669664
669964
696444
696464
696644
696664
696964
699644
699664
699964
964444
964464
964644
964664
966444
966464
966644
966664
966964
969644
969664
969964
996444
996464
996644
996664
996964
999644
999664
999964

Total: 38

Answer 3

Dejemos que $a_n$ , $b_n$ y $c_n$ es el número de códigos de n dígitos que terminan en 4, 9 o 6, respectivamente, sin el requisito de que se utilicen los 3 dígitos.

Si $e_n$ da el número total de códigos de n dígitos, entonces

$a_n=e_{n-1}-b_{n-1}$ , $b_n=e_{n-1}-a_{n-1}$ y $c_n=e_{n-1}$ y

$e_n=a_n+b_n+c_n=3e_{n-1}-(a_{n-1}+b_{n-1})=3e_{n-1}-(e_{n-1}-c_{n-1})=2e_{n-1}+e_{n-2}$ ;

así que $e_1=3, e_2=7, e_3=17, e_4=41, e_5=99$ .

Desde $a_n=b_n$ por simetría, $e_n=2a_n+e_{n-1}\;\;$ y por lo tanto $a_n=\frac{1}{2}(e_n-e_{n-1})=\frac{1}{2}(e_{n-1}+e_{n-2})$ .

Entonces $a_6=\frac{1}{2}(e_5+e_4)=70$ y

debemos deducir el número de códigos de 6 dígitos terminados en 4 que no incluyen un 9.

Dado que hay $2^5$ tales códigos, hay $70-2^5=70-32=38$ posibilidades.

$-----------------------------------$

Una forma alternativa de contar el número de posibilidades es dividirlo en casos, basándose en el número $\;\;l$ de 4's consecutivos al final del código.

Entonces $1\le l\le4$ y el dígito que precede a la cadena de 4's debe ser un 6; entonces

hay $\displaystyle\sum_{m=1}^4 (e_m-2^m)=1+3+9+25=38$ posibilidades. (donde $m=5-l$ )