Parejas de enteros especiales

Vamos con el problema de esta semana. Ahí va:

Ua pareja de enteros es especial si es de la forma (n,n-1) o de la forma (n-1,n), con n un entero positivo. Muestra que una pareja (n,m) de enteros positivos que no es especial se puede representar como la suma de dos o más parejas especiales diferentes si y sólo si los enteros n y m satisfacen la desigualdad

n+m \geq (n-m)^2

Nota: La suma de dos parejas se define como (a,b)+(c,d)=(a+c,b+d).

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.

17 Comentarios

  1. Sea la pareja no especial {1,3}

    n+m=4 y (n-m)^2=4

    Cumple la hipótesis y no hay suma que la cree.

    Publica una respuesta
  2. Juanjo, la pareja (1,3) si no entendí mal el problema podría expresarse como (0,1)+(1,2)

    Publica una respuesta
  3. Carlos
    El cero no es entero positivo, por lo demás estaría de acuerdo contigo

    Publica una respuesta
  4. Carlos

    Si el cero entra en el problema se aclara mucho y seguimos mal:

    La suma de m parejas {0,1} y n parejas {1,0} siempre es {n,m}

    Publica una respuesta
  5. Perdon, no son parejas distintas. Retiro mi último comentario

    Publica una respuesta
  6. Vamos a buscar la pareja no especial {n,m}, con n>m, que tenga la menor relación m/n y se pueda representar como suma de dos o más parejas especiales diferentes.

    La pareja especial {1,0} tiene una relación 0; {2,1} tiene 1/2; {3/2} tiene 2/3… Es una serie creciente. Para conseguir la menor relación m/n que cumpla los requisitos tendré que sumar los primeros términos de la serie, pues cualquier otra suma me dará una relación mayor. Por tanto la pareja no especial con menor m/n que cumple los requisitos es {0+1+…+k,1+2+…+(k+1)}={k*(k-1)/2,k(k+1)/2}.

    Como n=k*(k+1)/2 y m=k*(k-1)/2, n+m=k^2 y (n-m)^2=(k)^2, luego las parejas no especiales que cumplen los requisitos son las que tienen n+m=(n-m)^2. Ninguna pareja que tenga una relación mayor que la anterior, n+m>(n-m)^2, se podrá representar como suma de parejas especiales.

    Ahora hay que demostrar que todas las parejas que cumplen la desigualdad sí se pueden representar como suma de dos o más parejas especiales diferentes.

    Publica una respuesta
  7. Vamos a hallar las parejas especiales que sumadas nos dan {n,m}, con n>m y que cumplen la desigualdad anterior.

    Calculamos s=n-m y t=n-s*(s-1)/2. Tomamos las parejas {k,k-1} desde {1,0} hasta {s-1,s-2}, si existen, y la pareja {t,t-1}, y las sumamos, obteniendo {n,m}.

    Si n=m sumamos {n-1,n}+{1,0}={n,n}.

    Por tanto siempre hay solución cuando se cumple la desigualdad y nunca si no se cumple.

    Publica una respuesta
  8. La primera observación es que hay que considerar el 0 como entero positivo, ya que la pareja (1,1), que no es normal y cumple la condición impuesta (1+1>1-1) solo puede obtenerse como suma de dos parejas normales así: (1,0)+(0,1)=(1,1).
    Separemos las parejas no normales en dos tipos, la formadas por dos números iguales y la formadas por dos distintos.
    Las primeras cumplen la condición indicada y son fáciles de descomponer:
    Sea (a,a) con a par. Se descompone en (a/2,a/2-1)+(a/2,a/2+1), ambas normales.
    Si a es impar se descompondría así: (((a+1)/2+(a-1)/2))+((a-1)/2,(a+1)/2), también ambas normales.
    Para el caso de m y n distintos los casos m>n y m1 para que la pareja no sea normal.
    Como cada pareja normal aporta una diferencia de 1 al valor de m hay que sumar k parejas para poder obtener una diferencia de k. Se necesitan por tanto k sumandos de la forma (p+1,p)+(q+1,q)+(r+1,r)+… de modo que p+q+r+… =m.
    Tengo que irme. Continuará.

    Publica una respuesta
  9. JJGJJG, no hace falta tomar 0 como entero positivo. Con n=1 las parejas {n,n-1} y {n-1,n} valen {1,0} y {0,1}, y suman {1,1}.

    Publica una respuesta
  10. Donde dije “Para el caso de m y n distintos los casos m>n y m>n tienen soluciones simétricas por lo que basta con analizar uno solo de los casos”
    Mmonchi, he vuelto tarde y te me has adelantado.

    Publica una respuesta
  11. Si queremos obtener una pareja cuya diferencia es d>1, necesitamos sumar al menos d parejas especiales.

    Si sumamos las parejas {0,1},{1,2}…{d-1,d} obtenemos una pareja cuya diferencia es d, con:

    n = d(d-1)/2

    m = d(d+1)/2

    y por lo tanto su suma será:

    s = n + m = d^2

    Si queremos obtener una pareja con una suma mayor (manteniendo la diferencia) sólo tenemos que sustituir la pareja {d-1,d} por otra mayor.

    No se puede obtener una pareja con una suma menor (manteniendo la diferencia) sin repetir parejas.

    Publica una respuesta
  12. Este es el problema 5 de la Olimpiada Nacional de México del 2013. Lo sé por que yo estuve allí. Sinceramente mi problema favorito de esta vez. Ni siquiera sé por que comento, pero me emocionó mucho verlo en esta página 🙂

    Publica una respuesta
  13. Hasta ahora estoy entrando en este mundo y en medio de mi ignorancia intenté darle una solución al problema y no estoy seguro de si lo entendí bien.

    Dice que la suma de dos parejas especiales me permite obtener una pareja no especial, entonces hice lo siguiente:

    (n,m)=(a,b)+(c,d) o (n,m)=(a,a-1)+(c,c-1) porque son parejas especiales, estoy en lo correcto?

    Dice que debe cumplir la desigualdad y que la suma de parejas es sumando los primeros términos con los segundos, luego eso significa que:

    n=a+c y m=a+c-2

    Reemplazo estos términos en la desigualdad y obtengo que

    1>=2 lo cual obviamente es falso, por lo tanto el enunciado no es cierto.

    Cometí algún error?

    Publica una respuesta
  14. Esperando que se entienda bien el problema, se tiene que demostrar que una pareja no especial se puede escribir como suma de dos o MAS parejas especiales, si y sólo si se cumple la desigualdad. Al sustituir los valores que tu das, llegas a que 2a+2c-2 mayor o igual a 4, es decir, a+c mayor o igual a 3, que es cierto porque m es positivo, y entonces a+c es mayor a dos. Te conviene trabajar el problema más bien fijándote en una pareja no especial dada, no en cómo es la suma de dos o más parejas especiales

    Publica una respuesta
  15. Hola a todos. Creo haber dado con una demostración sencilla de una de las dos implicaciones. Concretamente suponiendo que {n,m} se puede representar como suma de parejas especiales, demostremos la desigualdad comparando el menor posible de n+m con el mayor posible de (n-m)^2. Sean a1, a2,….,ar los r representantes de las parejas especiales y sea S=a1+a2+…+ar. Es fácil comprobar que:
    n+m = 2S-r. El menor valor posible se dará para el menor S. Como todos los ai son enteros positivos distintos, el menor valor de S será para los primeros r enteros positivos. Es decir:
    S=r(r+1)/2. Por tanto, el menor valor de n+m:
    min(n+m)=min(2S-r)=r(r+1)-r=r^2
    Vamos con el otro lado de la desigualdad. Para ello se puede comprobar que m-n está acotado entre -r y +r, por lo que (m-n)^2 lo está entre 0 y r^2. así:
    max((m-n)^2)=r^2=min(m+n) que es lo que buscábamos.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com Valora en Bitacoras.com: Vamos con el problema de esta semana. Ahí va: Ua pareja de enteros es…

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 *