Vemos, en las figuras 1 y 2, ejemplos de pantallas de bloqueo de un móvil que sólo funciona con una contraseña que no se teclea sino que se dibuja con segmentos de línea recta. Esos segmentos forman una línea poligonal con vértices en un entramado. Al dibujar el patrón que corresponde a un contraseña, el dedo no puede perder el contacto con la pantalla. Cada línea poligonal corresponde a una secuencia de dígitos y esta secuencia es, de hecho, la contraseña. El trazado de la poligonal obedece a la siguientes reglas:
i. El trazado comienza en algunos de los puntos desprendidos que corresponden a los dígitos de $1$ a $9$ (Figura 3).
ii. Cada segmento del patrón debe tener como uno de sus extremos (en en el que terminamos el trazado del segmento) un punto que no haya sido utilizado aún.
iii. Si un segmento conecta dos puntos y contiene un tercero (su punto medio), entonces el dígito correspondiente a este tercer punto se se incluye en la contraseña. Esto no ocurre si este punto/dígito ya ha sido ya ha sido utilizado.
iv. Cada contraseña tiene al menos cuatro dígitos.
Así, cada línea poligonal está asociada a una secuencia de cuatro o más dígitos, que aparecen en la contraseña en el mismo orden en que son visitan. En la figura 1, por ejemplo, la contraseña es $218369$ , si el primer punto visitado fue $2$ . Obsérvese cómo el segmento que une los puntos asociados a $3$ y $9$ incluye los puntos asociados a dígito $6$ . Si el primer punto visitado fuera el $9$ y la contraseña sería $963812$ . Si el primer punto visitado fuera el $6$ entonces el contraseña sería $693812$ . En este caso, el $6$ se omitiría, porque no se puede repetir. Por otro lado, la línea poligonal de Figura 2 está asociada a una contraseña única.
Determinar el menor $n$ $(n \geq 4)$ tal que, dado cualquier subconjunto de $n$ dígitos de $1$ a $9$ es posible elaborar una contraseña que involucre exactamente esos dígitos en algún orden.
Lo que yo pensaba: Claramente $n \geq 6$ ya que para $n=4$ podemos elegir $1,3,7,9$ y para $n=5$ podemos elegir $1,3,5,7,9$ . Para demostrar que $n=6$ En el caso de los puntos simétricos, acabo de nombrarlos con las mismas letras, es decir, C para el centro, M para el medio de los lados y E para los extremos de los lados. Si tomamos todos los triples que contengan sólo estos tres puntos simétricos y hacemos un poco de trabajo de caso, podemos demostrar que podemos hacer contraseñas con las otras combinaciones de $6$ puntos, y hemos terminado.
¿Cómo sería una solución elegante/formalizada?
