Vamos con el problema de esta semana. Ahí va:
Ua pareja de enteros es especial si es de la forma
o de la forma
, con
un entero positivo. Muestra que una pareja
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
satisfacen la desigualdad
Nota: La suma de dos parejas se define como
.
Que se os dé bien.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
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.
Juanjo, la pareja (1,3) si no entendí mal el problema podría expresarse como (0,1)+(1,2)
Carlos
El cero no es entero positivo, por lo demás estaría de acuerdo contigo
Juanjo, {0,1}+{1,2}={1,3}.
Con n=1, {n-1,n} es {0,1}.
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}
Aquí algo no me cuadra ya que (1,0)+(1,0)=(2,0) y 2<4
Perdon, no son parejas distintas. Retiro mi último comentario
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.
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.
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á.
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}.
Información Bitacoras.com
Valora en Bitacoras.com: Vamos con el problema de esta semana. Ahí va: Ua pareja de enteros es especial si es de la forma o de la forma , con un entero positivo. Muestra que una pareja de enteros positivos que no es especial se puede representar com…
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.
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.
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 🙂
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?
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
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.