Coloración con condiciones

Os dejo hoy martes el problema de esta semana. Ahí va:

Dado el conjunto N=\{1, 2, \ldots , n-1 \}, con n \geq 3, coloreamos cada uno de sus elementos de blanco o de negro según las siguientes reglas:

  1. i y n-i siempre se colorean del mismo color.
  2. Para algún j \in N primo relativo con n, i y |j-i| se colorean del mismo color para todo i \in N, \, i \ne j.

Demostrar que todos los números del conjunto N deben colorearse con el mismo color.

Que se os dé bien.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

13 Comentarios

  1. Para j=1 se cumple siempre:

    1 y n siempre son primos relativos; como i y i-1 son del mismo color, lo son 2 y 3, 3 y 4, 4 y 5, hasta n-1 y n, así que {2,3,4,…,n} son del mismo color; y como 1 y n-1 son del mismo color, 1 es del mismo color que el resto.

    Publica una respuesta
  2. Supongamos que no todos los números se colorean igual y el 1 es blanco. Llamamos m al número más pequeño de color negro. Es fácil ver que m debe ser menor o igual que j/2.

    Por la regla 1, el número n-m debe ser negro y, suponiendo que es mayor que j, podemos aplicar la regla 2 repetidas veces hasta llegar a un número menor o igual que j. Es decir, n-m módulo j debe ser negro y, aplicando 2 una vez más, m-n módulo j también.

    De la misma forma, si aplicamos primero la regla 2, obtenemos que j-m debe ser negro y, aplicando 1, n+m-j debe ser negro. Aplicando la regla 2 las veces necesarias llegamos a que m+n módulo j debe ser negro.

    Haciendo otra vez lo mismo con los números obtenidos llegamos a que m+2n y m-2n módulo j deben ser negros, y así se van recorriendo todos los números menores que j (ya que n y j son primos relativos), con lo que llegamos a la conclusión de que todos deben ser negros, incluido el 1, y hemos llegado a una contradicción.

    Publica una respuesta
  3. Coloreamos el 1 de blanco (o de negro) y, por la primera propiedad, 1 y n-1 son del mismo color.

    Como n-1 es primo relativo con n, para cualquier n, tenemos que:
    – Por la propiedad 2, 1 y |(n-1)-1|=n-2 son del mismo color y, por la primera propiedad, n-2 y 2 también lo son.
    – Por la propiedad 2, 2 y |(n-1)-2|=n-3 son del mismo color y, por la primera propiedad, n-3 y 3 también lo son.
    – Y así sucesivamente…

    Publica una respuesta
  4. Damiancete, la regla 2 dice que “para algún j primo con n …” y n-1 no tiene por qué ser el único primo con n que hay en el conjunto.Tienes que probarlo para todos ellos.

    Publica una respuesta
  5. Dado j para el que se cumple la condición (2.), es fácil ver que los primeros j-1 términos son del mismo color, pues:

    abs(j-(j-1))=1 , abs(j-(j-2))=2,… abs(j-(j-m))=m 1<=m <j

    Si n<2j, por la condición (1.) el color de m es igual a el color de n-m .

    n-m<2j-m (1<=m<j)

    en su valor máximo m=j-1, por lo cual el color de j-1 y el color de n-(j-1) son iguales.

    n-j+1<2j-j+1=j+1

    como n-(j-1)<2j

    Sea w en los naturales tal que:

    (w+1)j >n>wj

    Sea z en los naturales tal que wj<z<n, de la forma z=wj+r con 0<r<n-wj , r en los naturales.

    en general abs(j-z)=z-j

    Construimos w desigualdades de la siguiente forma:

    (w-1)j<z-j<n-j
    (w-2)j<z-2j<n-2j
    .
    .
    .
    0<z-wj<n-wj

    De donde se puede apreciar que, el color de cada z-Qj (0<=Q<=w) es el mismo.

    Como n-wjn-j.

    Por argumentos como los del caso anterior en que nwj>n-j, se tiene que z pertenece a {n-1,n-2 ,…,n-j}, por lo que cada z-Qj (0<=Qn-j, y como cada (w-R)j tiene el mismo color que wj, entonces todos los números de la forma (w-R)j tienen el mismo color que el conjunto {n-1,n-2 ,…,n-j}.

    Para probarlo en los números de la forma n-Tj, solo hace falta ver que, n-wj<j , por lo que
    n-wj esta en el conjunto {1,2,…,j-1} y como cada n-Tj tendra el mismo color que n-wj, todos los n-Tj tienen el mismo color que dicho conjunto.

    De esta forma todos los elementos del conjunto N tienen el mismo color.

    Q.E.D

    Recién llevo un año empezando en la carrera de matemáticas, aun no se manejar latex y todas las demostraciones que se me piden deben ser explicitas. Esta es la explicación que doy ante una demostración con tantas cosas innecesarias y una mala notación.

    Publica una respuesta
  6. No se que ocurrió con mi comentario anterior, pero aquí pongo la parte faltan-te de la demostración:

    De donde se puede apreciar que, el color de cada z-Qj (0<=Q wj > n-j

    Por argumentos como los del caso anterior en que 2j>n, los conjuntos {n-1,n-2 ,…,n-j} y {1,2,…,j-1} son del mismo color y como z pertenece al {n-1,n-2 ,…,n-j}, cada z-Qj (0<=Qn-j, y como cada (w-R)j tiene el mismo color que wj, entonces todos los números de la forma (w-R)j tienen el mismo color que el conjunto {n-1,n-2 ,…,n-j}.

    Para probarlo en los números de la forma n-Tj, solo hace falta ver que, n-wj<j , por lo que
    n-wj esta en el conjunto {1,2,…,j-1} y como cada n-Tj tendra el mismo color que n-wj, todos los n-Tj tienen el mismo color que dicho conjunto.

    De esta forma todos los elementos del conjunto N tienen el mismo color.

    Publica una respuesta
  7. Nuevamente, el comentario anterior se publico de forma cortada, por lo que vuelvo a escribir lo que no se puede leer.

    De donde se puede apreciar que, el color de cada z-Qj (0<=Qn, los conjuntos {n-1,n-2 ,…,n-j} y {1,2,…,j-1} son del mismo color y como z pertenece al conjunto {n-1,n-2 ,…,n-j}, cada z-Qj debe ser del mismo color que dicho conjunto.

    Falta probar que los numeros de la forma (w-R)j y n-Tj son todos del mismo color.

    Para esto, basta con ver que wj>n-j, por lo que wj tiene el mismo color que el conjunto {n-1,n-2 ,…,n-j}, como cada (w-R)j es del mismo color que wj, se sigue que cada (w-R)j es del mismo color.

    Para probarlo en los números de la forma n-Tj, solo hace falta ver que, n-wj<j , por lo que
    n-wj esta en el conjunto {1,2,…,j-1} y como cada n-Tj tendra el mismo color que n-wj, todos los n-Tj tienen el mismo color que dicho conjunto.

    De esta forma todos los elementos del conjunto N tienen el mismo color.

    Publica una respuesta
  8. Verdaderamente, lamento hacer algo que parece spam, pero al dar vista previa siempre aparece correctamente, y al momento de publicar el comentario es modificado

    Publica una respuesta
  9. Sea A=\left\lbrace kj : k=1,2,\dots\right\rbrace el conjunto de los múltiplos de j (dado por la condición 2). Para cada uno de los kj, sea r_k el resto de la división entera de kj y n, esto es, kj=nc_k+r_k con 0\leq r_k<n. Veamos, por inducción sobre k, que j y r_k están pintados del mismo color. Para k=1 es obvio. Supongamos cierto para k y veamos que también lo es para k+1. Tenemos que

    {\displaystyle\begin{cases}kj=nc_k+r_k\\(k+1)j=nc_{k+1}+r_{k+1} \end{cases}}

    de donde

    j=n(c_{k+1}-c_k)+(r_{k+1}-r_k) luego \left|j-r_{k+1}\right|=\left|n(c_{k+1}-c_k)-r_k \right|.

    Como j, r_{k+1}\in N=\left\lbrace1,2,\dots,n-1\right\rbrace, se tiene que |j-r_{k+1}|<n, luego o bien, c_{k+1}-c_k=0 en cuyo caso \left|j-r_{k+1}\right|=r_k, o bien c_k-c_{k-1}=1 en cuyo caso \left|j-r_{k+1}\right|=n-r_k. En ambos casos, se concluye (aplicando las condiciones (1) ó (2)) que r_{k+1} y r_k están pintados del mismo color. Por hipótesis de inducción, r_k es del mismo color que j y por tanto r_{k+1} también.

    Esto prueba que que  j y r_k están pintados del mismo color para todo k.

    Para concluir, hay que demostrar que la aplicación \mathbb{N}\longrightarrow N, \  k\mapsto r_k es sobreyectiva:

    Puesto que N es finitio, la sucesión r_1,r_2,\dots,r_k,\dots debe tener elementos repetidos. Sea m el primer valor de k tal que r_1=r_m. Obsérvese que r_1=j, luego j=r_m, de donde j\equiv mj\mod n, es decir, n\mid (m-1)j. Como n y son j son primos relativos n\mid m-1. Por tanto n<m y esto prueba la sobreyectividad.

    Publica una respuesta
  10. Por 1a regla, está claro que 1 y n-1 deben colorearse con el mismo color. Para la regla 2, exige para algún j, con que basta demostrar que 1 es primo relativo de n, i y |1-i| (es dicir, para j=1) para todo i perteneciente a N por el método de inducción:
    1) Con i=1 se cumple, pues:
    mcd(1,n)=1, para cualquier n>=3 natural
    mcd(1,1)=1
    mcd(1,|1-1|)=1, pues 0 solamente es primo relativo con 1 y -1.
    2) Establecer hipótesis de inducción (HI) con i=k-1 para luego demostrar con k:
    mcd(1,n)=1
    mcd(1,k-1)=1
    mcd(1,|1-(k-1)|)=1 => mcd(1,k)=1
    3) Demostrar para i=k:
    mcd(1,n)=(HI)=1, lo cual se cumple
    mcd(1,k)=(HI)=1, lo cual se cumple
    mcd(1,|1-k|)=mcd(1,k-1)=(HI)=1, lo cual se cumple.
    Una vez demostrado, simplemente se establece que para todo i perteneciente a N-{1} se colorea del mismo color, lo cual incluye a n-1. Pero como i debe colorearse con el mismo color que n-1 (regla 1), entonces se concluye la demostración de que todos los elementos de N deben pintarse del mismo color. QED

    Publica una respuesta
  11. Hola Eloy, creo que es una casi demostración a un problema casi igual que el problema inicial, me explico:
    1) En la 2a regla, creo que lo lógico es interpetarlo como que, si j es coprimo con n, entonces i y |j-i| se colorean del mismo color, (2 a 2), para todo i distinto de j.
    2) Entiendo que demostraste por inducción, que para j=1 cumple que es coprimo de esos 3 valores, para todo i. Creo que se podría demostrar directamente, pues 1 es coprimo con cualquier entero. Aún así, esto no te asegura, como ya se comentó, que no exista otro j distinto de 1 que cumpla esa misma condición. De hecho, para n=6 y j=5, se satisface pues 5 es coprimo con 6, y 1 lo es con 4, 2 con 3, etc.

    Por esto, creo que el problema original, si no lo he entendido mal, requiere más tiempo de demostrar. Propongo además ver qué condiciones (minimales) se le debe imponer a j para que, con las 2 reglas, se demuestre que necesariamente todos los elementos son del mismo color. No sé si es posible, en este caso, mejorar la condición de j para la 2a regla. Habría que ver si hay algún n y j, j no coprimo con n, tales que, imponiendo las reglas, se tuviesen todos los elementos del mismo color necesariamente.

    Suerte!

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com Valora en Bitacoras.com: Os dejo hoy martes el problema de esta semana. Ahí va: Dado el conjunto…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *