Del conjunto [math]\{1,2,3,4,5,6,7,8,9\} hay que elegir seis dígitos y, con esos seis dígitos, formar los [math]30 números de dos dígitos de modo que haya entre ellos la mayor cantidad posible de números primos.
Dar un ejemplo de un conjunto que cumple esta condición y explicar por qué no es posible hallar conjuntos con los que se formen más números primos.
Para empezar, teniendo la Criba de Erastotenes (o tabla de números primos) notamos los números que hay del 13 al 97 inclusive. Estos son los únicos números primos de dos digitos que podremos formar con los numeros: 1, 2, 3, 4, 5, 6, 7, 8, 9.
Al ver la tabla, podremos fijarnos que la ultima cifra de los números primos son: 1, 3, 7 y 9. Y por lo tanto, esos números deben estar en nuestra elección.
Luego revisamos la primer cifra y podemos ver que el n° 4 es el único que contiene a 3 números primos estando en las decenas, estos números son: 41, 43 y 47.
Por lo tanto, también debemos agregarlo a nuestra eleccion
Los números 2, 5, 6 u 8, estando en las decenas sólo contienen a 2 números primos.
Es esa la razón por la que la elección de nuestro último número, puede ser cualquiera de ellos.
Y suponiendo que elegimos el 8, nuestra elección de los 6 números es: 1, 3, 4, 7, 8 y 9.
Así, podríamos formar 14 números primos.
Si buscas un resultado distinto, no hagas siempre lo mismo
Algo muy importante a saber (para muchos problemas) es que todos los números primos mayores que $5$ terminan en $1, 3, 7$ o $9$. (La demostración es sencilla, si termina en un digito par, entonces es múltiplo de $2$, si termina en $5$ entonces es múltiplo de $5$, esto nos deja con que solamente puede terminar en $1, 3, 7, 9$)
Esto nos da una idea de que debemos si o si elegir estos $4$ números, sin embargo faltaría demostrarlo, lo cual lo dejamos para el final.
Una vez que elegimos al $1, 3, 7$ y $9$ nos queda elegir $2$ números mas. Veamos que nuestra lista se reduce a formar algunos de los siguientes primos: $ 23, 29 | 41, 43, 47 | 53, 59 | 61, 67 | 83, 89$. Esta claro que si elegimos el $4$ vamos a "desbloquear" $3$ primos, por lo cual si o si lo elegimos. Finalmente podemos elegir cualquier otro numero de la lista: $2, 4, 5, 6, 8$ y vamos a obtener la misma cantidad de números. Por ejemplo si elegimos el $2$, la lista de primos nos quedaría:
$$13, 17, 19 | 23, 29 | 31, 37 | 41, 43, 47 | 71, 73, 79 | 97$$
La cual en total tiene $14$ números primos.
Ahora que encontramos una lista con $15$ primos veamos que pasa si no elegimos a los números $1, 3, 7$ o $9$
Si no elegimos al $1$
No vamos a poder formar ninguno de los siguientes números:
$$13, 17, 19 | 31 | 41 | 61 | 71 $$
Total: 8 primos
Por lo tanto, el máximo numero de primos que podemos obtener es $21 - 6 = 15$ sin embargo esto solo ocurre si usamos todos los números excepto el $9$, entonces al sacar otro numero ya no obtendríamos $15$.
