Cada uno de los números del 1 al 4027 se ha coloreado de verde o de rojo. Cambiar el color de un número es pasarlo a verde si era rojo, y pasarlo a rojo si era verde.
Diremos que dos enteros positivos $m$ y $n$ son cuates si alguno de los números $\frac{m}{n}$ o $\frac{n}{m}$ es un número primo. Un paso consiste en elegir dos números que sean cuates y cambiar el color de cada uno de los números.
Muestra que después de realizar algunos pasos es posible hacer que todos los números del 1 al 2014 sean verdes.
En mi opinión el problema 1 y
En mi opinión el problema 1 y 2 de esta nacional deberían quedar en categoría intermedia
Listo, ya los cambié! ¡Me
Listo, ya los cambié! ¡Me descubriste! No resolví los problemas por lo que no supe en qué categoría ponerlos. Saludos!
Para este problema no era
Para este problema no era necesario considerar los números del 1 al 4027. Se puede sustituir el 4027 por 2015 y sigue siendo cierto.
En este problema se puede
En este problema se puede abusar de el postulado de Bertrand :)
Usando el postulado de Bertrand el problema se puede generalizar para pintar los números del $1$ a $n$, usando números de $1$ a $2n - 1$
Te fijas que puedes pintar $k$ y $\frac{k}{p}$ donde $p$ es un primo que divide a $k$ y te fijas que $k$ es mayor que $\frac{k}{p}$. Pintas $n, n-1, n-2, ...$ en ese orden, en cada paso te fijas que no alteras a los que ya habias pintado, luego ya dejaste a todos bien ... excepto quizas el $1$ (el $1$ no tiene menor con quien pintarse). Pero por el postulado de bertrand hay un primo $q$ entre $n$ y $2n$, pintas $1$ y $q$ y listo.
Luego tambien hay una solución que solo usa el postulado de Bertrand.
Supongamos que quieres pintar $k \leq n$ usando un número entre $n$ y $2n$, para eso necesitas un primo $p$ tal que $n < pk < 2n$, es decir $\frac{n}{k} < p < 2\frac{n}{k}$ y por el postulado de Bertrand ese primo existe :)
(Nota: Desde luego hay que ajustar un poco con el piso y techo de $\frac{n}{k}$ porque no es entero, pero eso es una tecnicalidad)
Hola iwakura, Sobre tu
Hola iwakura,
Sobre tu primera prueba de la generalización, está muy buena. Germán hizo la misma generalización en su examen; recuerdo que no usaba Bertrand; seguramente en tu demostración se podría evitar.
De hecho, hay una generalización más fuerte. Se puede probar que es posible pintar los números del $1$ al $n$, usando los números del $1$ al $n+1$.
Sobre tu segunda prueba, me parece muy elegante y corta. Pero tiene una falla. Para el caso $k=n$ no existe primo $p$ que satisfaga $\frac{n}{k} < p <2 \frac{n}{k}$. Para los demás valores de $k$ (es decir, para $k <n$) sí me convenciste que Bertrand garantiza que se pueden cambiar de color.
Saludos
Jesús
Desde luego que se puede
Desde luego que se puede evitar, solo que me pareció interesante lo mucho que se puede abusar de un teorema tan poderoso en un problema 1 de la OMM :P
De la segunda, cierto, lo bueno es que es facilmente arreglable ese caso cambiando $n$ y uno mas chico como en otras pruebas.
Comprendo Isaí, Gracias por
Comprendo Isaí,
Gracias por compartirnos esas formas de uso de Bertrand.
Tienes razón, es curioso cómo aún abusando de Bertrand no se obtiene una solución sustancialmente más simple y rápida a las demás. Como suelen decir "es como matar moscas con cañonazos".
Saludos
Una solución de este problema
Teniendo los números del 1 al
Teniendo los números del 1 al 4027, vemos que podemos formar parejas con un número ‘n’ y su doble ‘m’, y m/n sería igual a 2, que es un primo. Por lo tanto, m y n son cuates y los podemos cambiar de color. Si es rojo, no importa el color de m, n < 2014 quedará verde. Si m no es mayor que 2014, y queda rojo, lo volvemos a cambiar, pero con su respectivo doble, hasta que tenga el color que deseamos.
⇒ Los números del 1 al 2013 quedan verdes.
- - - - - - - - - - - - - - - - - -
La excepción a esta regla sería 2014, porque 2*2014 = 4028 > 4027. Para este caso, si 2014 es rojo, vemos que sus factores primos son 2*19*53. Como 2014 es cuate con sus divisores, escogemos cualquiera de ellos, digamos α, y los cambiamos de color, tal que 2014 queda verde y α, rojo. Sea α (k) múltiplo de α tal que 2014 < α (k). Finalmente, intercambiamos los colores de α y de α (k).
- - - - - - - - - - - - - - - - - - - -
⇒ Los números del 1 al 2014 quedan verdes.
Bueno, ya que están
Bueno, ya que están publicando soluciones a este problema aprovecho para darles mi prueba del caso general, esto es, que si tengo los números de 1 a n+1, pintados de rojo y verde, puedo cambiar los colores de los números de 1 a n a verdes usando la movida permitida.
Primero observemos que dado cualquier número $M$ entre 2 y n+1, puedo usar su descomposición prima y quitando un factor primo a la vez obtenemos una sucesión de números $M = M_1 > M_2 > \dots > M_k = 1$ tal que cualesquiera dos consecutivos son cuates. Si aplicamos la movida a cada pareja de cuates $M_i$ y $M_{i+1}$ (con $i = 1 , \dots, k-1$) terminaremos cambiando sólo el cólor de $M$ y 1 (=$M_k$). En consecuencia, siempre podemos cambiar el color de cualquier número y el 1 al mismo tiempo sin afectar el color de los demás. Llamaremos a este aplicación de movidas como "movimiento extremo".
Con el movimiento extremo, descrito anteriormente, puedo cambiar todos los rojos de 2 a n a verde. Podría ocurrir que 1 haya quedado en rojo, en tal caso, podemos usar el movimiento extremo nuevamente pero ahora en n+1 y así cambiamos el color de 1 a verde (el de n+1 también cambiaría de color, pero no nos interesa). Quedando así, todos los números de 1 a n en verde.