¿De cuántas maneras pueden los seis números del conjunto $\{4, 3, 2, 12, 1, 6\}$ se ordenen de manera que $a$ viene antes que $b$ siempre que $a$ es un divisor de $b$ ?
Respuestas
¿Demasiados anuncios?
Hagen von Eitzen
Puntos
171160
Mike Powell
Puntos
2913
La siguiente terminología no es necesaria para el problema, pero permítanme mencionarla de todos modos. Suponga que piensa en los números como nodos en un gráfico, con aristas entre el nodo $a$ y el nodo $b$ si $a$ es un divisor de $b$ . Entonces se quiere ordenar los nodos en una línea tal que si hay una arista desde el nodo $a$ al nodo $b$ , entonces el nodo $a$ se produce a la izquierda de $b$ . En otras palabras, usted quiere ordenar topológicamente el siguiente gráfico:
(Para simplificar, he omitido las aristas que no afectan a la respuesta, ya que están implícitas en la transitividad; el gráfico real es el siguiente
cuando se dibujan todas las aristas).
En otra terminología, se quiere calcular el número de extensiones lineales del orden parcial dado por la relación anterior.
De todos modos, sea cual sea la terminología que utilicemos, podemos desecharla porque la solución es la misma que la de las otras respuestas: considera cualquier camino más largo del grafo, digamos $1 \rightarrow 3 \rightarrow 6 \rightarrow 12$ . Estos deben aparecer en ese orden. Más información en $2$ debe comparecer ante $6$ y después $1$ por lo que puede aparecer tanto entre $1$ y $3$ o entre $3$ y $6$ . Enumerar las posibilidades:
- Si $2$ aparece entre $1$ y $3$ , por lo que tenemos el orden $1, 2, 3, 6, 12$ entonces las opciones válidas para el número restante $4$ están en los tres "huecos" 2-3, 3-6 y 6-12:
- $1, 2, 4, 3, 6, 12$
- $1, 2, 3, 4, 6, 12$
- $1, 2, 3, 6, 4, 12$
- Si $2$ aparece entre $3$ y $6$ , por lo que tenemos el orden $1, 3, 2, 6, 12$ , entonces las opciones de $4$ están en los huecos 2-6 o 6-12:
- $1, 3, 2, 4, 6, 12$
- $1, 3, 2, 6, 4, 12$
Estos son todos los cinco (5) posibilidades.
Shabaz
Puntos
403
tfrederick74656
Puntos
582
Bueno, uno puede decir que 1 y 12 son fijos y, por lo tanto, puedes empezar por ahí. Una opción posible es 1,2,3,4,6,12 . También puede invertir el 2 y 3 porque son primos, haciendo una segunda opción de 1,3,2,4,6,12 . El 6 y 4 puede cambiarse porque el único otro múltiplo de 4 es 12 , haciendo una tercera combinación posible de 1,2,3,6,4,12 . Esto también se puede utilizar para hacer 1,2,4,3,6,12 para 3 es primo.He utilizado la misma regla para 6 y cambió su lugar por el 4 haciendo 1,3,2,6,4,12 . Esto hace un total de 5 opciones y creo que estas son las opciones correctas.
