Os dejo hoy lunes el problema de esta semana. Ahí va:
Sea
un subconjunto de números enteros positivos del conjunto
(con
números enteros positivos) que cumple que para cualesquiera dos elementos
con
(
) entonces
también pertenece al propio
.
Prueba entonces que:
Que se os dé bien.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
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.
Gaussianos recibió el Premio Prisma 2018 a la mejor web/red social. Haz click en la imagen si quieres saber más.
Los Premios Prismas son una iniciativa de los Museos Científicos Coruñeses para premiar la difusión de la cultura científica y apoyar a profesionales que trabajan en este campo. Más información en Premios Prismas.
Si quieres recibir los artículos de Gaussianos en tu mail, haz click en la imagen.
Únete a la iniciativa Yo construí el poliedro de Császár. Haz click en la imagen para conocer todo los detalles.
Y visita este set de Flickr para ver las construcciones de los lectores de Gaussianos.
Algo no entiendo de las condiciones. Si tomo el conjunto (1, 2, 3, …, 100), el subconjunto (1, 2, 3) cumple las condiciones impuestas: m=3, n=100 y las sumas de cada dos elementos es menor que 100, sin embargo, la media aritmética del subconjunto sí es menor que (100+1)/2
JJGJJG:
1+3 y 2+3 son < 100 y no pertenecen a (1,2,3), contrariamente a lo que pide la última propiedad. Sin embargo, si tomas n=3, se cumple la propiedad porque no hay ningún par de números cuya suma sea menor que 3, y la media artimética es 2, cumpliéndose la desigualdad final.
Información Bitacoras.com
Valora en Bitacoras.com: Os dejo hoy lunes el problema de esta semana. Ahí va: Sea un subconjunto de números enteros positivos del conjunto (con números enteros positivos) que cumple que para cualesquiera dos elementos con () entonces también per…
Una pista: no es difícil ver que
para todo 
.
Sabemos que si m=n es un caso particular en el que se cumplen las condiciones (si su suma es menor o igual que n entonces dicha suma será un número menor o igual que n que claramente está en el conjunto ya que el subconjunto es igual al conjunto {1, 2… n}) y que cumple la desigualdad con igualdad.
La suma de números de 1 a n es n*(n+1)/2
O dicho de otra forma, la media es (n+1)/2 y hay n números.
(la parte izquierda de la desigualdad es la media del subconjunto)
Entonces sólo faltaría probar que si faltan números la media de dichos números debe ser menor (o igual) que la media anterior… de forma que la media de los m que quedan sea mayor (o igual) que la media anterior (la media que resulta cuando están todos los números del 1 al n)
Un descubrimiento que creo interesante: Si 1 pertenece a A entonces m=n
Es decir, si está el 1 entonces no puede faltar ningún elemento de 1 a n
Prueba previa: si 1 pertenece a A entonces deben pertenecer a A todas las potencias de 2 (menores o iguales a n, claro). Si 1 pertenece, 1+1 = 2 pertenece, 2+2 = 4 pertenece, 4+4 = 8 pertenece… En general, cualquier potencia de 2 menor o igual que n debe pertenecer.
Prueba: supongamos que hay un elemento q de 1 a n que no esté en A. Dicho elemento se puede expresar en binario como suma de un número finito potencias de 2… Tomamos la mayor de dichas potencias de 2 en la que se descompone y formamos una suma de números q = pot2 + qresto … pot2 como hemos dicho pertenece a A así que si qresto pertenece a A también deberá pertenecer q. Pero con qresto podemos seguir el mismo proceso (y en qresto la suma de potencias de 2 tiene un sumando menos que antes) hasta que qresto tenga sólo 2 sumandos que serán potencias de 2 y que pertenecen a A. Por tanto es imposible que 1 pertenezca y otro número de 1 a n no pertenezca.
De la misma forma, podríamos seguir con afirmaciones similares:
* Si 2 pertenece a A entonces pertenecen todos los pares.
Cuya media es mayor que n/2 (que viene a ser mayor o igual que n/2 + 1/2) … si n es impar, la media es n/2 + 1/2 = (n+1)/2, si es par será n/2 + 1 = (n+1)/2 + 1/2 > (n+1)/2
* Si 3 pertenece a A entonces pertenecen todos los múltiplos de 3
Otra progresión aritmética cuya media es mayor o igual que (n+1)/2
* etc
Con esta idea… llegamos a que A sólo puede tener la unión de progresiones aritméticas (por ejemplo, la unión de múltiplos de 2 y múltiplos de 3). Y en cada una de ellas la media es mayor o igual así que en la unión la media debe ser mayor o igual.
Simplemente y por simplificar la prueba de Ácido. En el propio enunciado del problema no se restringe a que ai=aj (de hecho aparece un menor o igual en la cadena de 1,i.j.n) con lo cual supongo que lo del uno lo puedes argumentar sumando unos todas las veces que quieras. Idem con doses, treses, etc.
Creo que la prueba de Acido no es válida. Siguiendo con el ejemplo, la unión de los múltiplos de 2 y los múltiplos de 3 no es una unión disjunta, porque hay elementos que pertenecen a los dos conjuntos (por ejemplo, el 6). Eso hace que no se pueda aplicar un argumento tan sencillo como que la media de la suma va a ser la suma de las medias.
Por otra parte, al unir los dos conjuntos habrá que añadir también nuevos elementos, por ejemplo 5 = 2 + 3. De hecho, si a y b son coprimos, cualquier número a partir de (a-1)(b-1) se puede expresar como sumas de a y b. Es posible que siguiendo por ese camino se pueda demostrar. De todas formas, con la clave que ha dado Manzano se resuelve fácilmente.
Yo también creo que Manzano ha dado justo en el clavo, ordenando el conjunto de menor a mayor se comprueba lo que manzano dijo y… VOILÀ.
A ver lo que dice Manzano:
a(i) + a(m-i+1) >= n+1
por ejemplo, para i=1 el elemento primero a(1) sumado al elemento último a(m) es mayor o igual que n+1 … ¿no puede ser n? No, porque entonces n pertenecería a A y n>a(m) lo cual contradice que a(m) fuese el mayor.
Pero, ¿¿¿se cumple esto en para todo i ??? Por ejemplo i=2
El elemento segundo sumado al penúltimo ¿debe ser mayor o igual que n+1???
En este caso no me resulta tan sencillo verlo… ¿qué pasa si la suma es n? Pues que ese n debe pernecer a A… pero n sería el último y hemos hablado del penúltimo así que no veo tan claro que no pueda ser así.
Por ejemplo, el último puede ser n = 24 y el segundo puede ser 3 ¿por qué el penúltimo no puede ser 21? Ah, vale, porque si 3 es el segundo habrá otro (el 2) menor que 3 tal que 21 + 2 = 23 y entonces no podría ser el penúltimo.
Bueno, viendo esto ya estaría… pero eso de que «es fácil» verlo… pues quizá no es tan fácil ¿no? xD
Si m es par:
a(1) + …. + a(m) >= (n+1) * m/2
Si m es impar:
a(1) + …. + a(m) >= (n+1) * (m-1)/2 + a(intermedio)
= (n+1)*m – (n+1)/2 + a(intermedio)
Luego para que se cumpla debe ser:
a(intermedio) + a(intermedio) >= n+1
¿y cómo sabemos que no puede ser 2*a(intermedio) = n?
Golvano, tienes razón… no sería la unión.
En caso de ser la unión, me dio por intuir que si en ambos la media es mayor en la unión también lo sería… lo cual es falso en general. En general si tienes conjunto que en media es mayor que algo y lo unes a otro que en media es mayor que eso la unión puede tener una media menor que eso. Por ejemplo, {30, 50, 100} en media (60) es mayor que 59, {32, 48, 100} en media (60) es mayor que 59 pero {30, 32, 48, 50, 100} tiene una media (260/5 = 52) menor que 59.
A pesar de lo anterior tenía la duda de si en el caso de múltiplos no se pudiese llegar a eso (que la media de la unión siguiese siendo mayor)… aunque al no ser la unión tampoco serviría probarlo.
Pero hice un contraejemplo con múltiplos de 2 y 3:
* Múltiplos de 2: {2, 4, 6, 8, 10, 12} : Media_2 = 7
* Múltiplos de 3: {3, 6, 9, 12}: Media_3 = 7.5
Si n=13 en ambos casos se cumple que la media es >= (n+1)/2 = 7
* Unión: {2, 3, 4, 6, 8, 9, 10, 12}: Media_U = (14*3+12)/8 = 6.75 (menor que ambas medias… Y menor que (n+1)/2 )
Ácido, ese «a(intermedio)» ha de ser mayor o igual que
ya que de lo contrario a(intermedio) no podría ser el intermedio.
Un ejemplo del razonamiento a seguir:
Asumiedo que los elementos están ordenados de menor a mayor.
Si
, entonces 
, contradiciendo que 
era el máximo de A, luego 
.
Si
, entonces 
, contradiciendo que 
era el penúltimo, luego 
.
Y así…
Daniel San, igual se me escapa algo… pero no acabo de ver eso que dices. Por decir una chorrada, {1, 2, 3, 20, 21} n=22 … 3 es el intermedio pero no es mayor o igual que (n+1)/2
… ya se que ese conjunto A que puse no cumple las condiciones pero no acabo de ver por qué el elemento intermedio debe ser mayor o igual que (n+1)/2
No me vale «es que no podría ser el intermedio» o «es imposible»… quiero la prueba.
Daniel como se garantiza que
no es 
Simplemente, si tomas el elemento k empezando por arriba y el elemento k empezando por abajo, su suma tiene que ser mayor que n, porque si no habría k elementos (sumando desde
hasta 
) por encima, y ya no sería el elemento k. Si son impares, emparejas el central consigo mismo y aplicas el mismo razonamiento.
Karl, no te lo puedo garantizar, pero si
, entonces 
sea el penúltimo.
De nuevo se incumple el hecho de que
Ácido, suscribo el comentario de Golvano previo al mío.
Daniel San,
Dices
«Un ejemplo del razonamiento a seguir:
Asumiendo que los elementos están ordenados de menor a mayor.»
«Si a(2) + a(m-1) menor o igual que n, entonces a(m-1) menor que a(2) + a(m-1) perteneciente a A, contradiciendo que a(m-1) era el penúltimo»
Bueno… en el caso a(1) + a(m) la contradicción se ve más clara. En este caso puede ser que a(2) + a(m-1) fuese a(m) y eso no contradice que a(m-1) sea el penúltimo ¿verdad? Aquí hay que explicar que si a(2)+a(m-1) fuese a(m) entonces podemos formar un a(1)+a(m-1) que es mayor que el penúltimo y menor que el a(m)… así que ahora se ve claro que no puede ser el penúltimo.
Mi crítica es que decís: pues en el caso de a(1) y a(m) se ve claro… así que en los demás casos pues igual y así sucesivamente… y no es así, ya he explicado que en cada caso se va enrevesando… aunque al final sale la prueba pero no tan «fácil» como se prometió.
En el caso a(3)+a(m-2) si fuese menor o igual que n, entonces a(m-2) menor que a(3) + a(m-2) perteneciente a A… ¿contradice que a(m-2) sea antepenúltimo?. Sí, pero no es obvio, es enrevesado. a(3) + a(m-2) podría ser el penúltimo o el último… Supongamos a(3) + a(m-2) = a(m-1) entonces a(2) + a(m-2) es mayor que a(m-2) y menor que a(m-1) lo cual es imposible (no puede haber uno entre el antepenúltimo y el penúltimo). Supongamos que a(3) + a(m-2) = a(m) entonces a(2) + a(m-2) debería ser a(m-1) ya que está entre ambos y debería pertenecer a A pero eso también es imposible porque a(1) + a(m-2) también debería pertenecer a A y está entre a(m-2) y el supuesto a(m-1) lo cual es imposible.
Creo que la explicación completa debería de esa manera.
Y con esa explicación se llegaría también al caso del intermedio en posición k… Si a(k) + a(k) fuese menor o igual a n entonces dicha suma pertenecería a A… y en ese caso habría k-1 sumas que también pertenecerían: a(1)+a(k), a(2)+a(k) hasta a(k-1) +a(k)
y podríamos llegar a ver que no pueden ser los k-1 superiores si suponemos que hay otro que es a(k) + a(k) … ya no serían k-1 superiores sino k superiores lo que contradice que fuese el intermedio.
Supongo que esto es lo que decía Golvano… cuando dijo «sumando desde a1 hasta ak» se refería a las sumas a(1)+a(m-k+1) , a(2)+ a(m-k+1) … hasta a(k) + a(m-k+1) son k sumas distintas y mayores que ese elemento que deberían pertenecer a A y ya no sería el k-esimo empezando por arriba.
Algo falla: A=(4, 5, 9) subconjunto de {1, 2,…, 12}. La única pareja que cumple la condición es a1=4 y a2=5, pues 4+5=9, que es menor que 12, y 9 a su vez pertenece a A. Sin embargo, (4+5+9)/3 = 6 pero n+1/2 = 6.5, y la desigualdad estaría al revés. Es decir, algo en el enunciado está mal.
O soy yo que no capto bien el enunciado… que también podría ser.
tu conjunto está incompleto, te falta 4+4=8; 4+8=12; 5+5=10. Lee bien el enunciado, i puede ser igual a j 😉
Pues tiene usted toda la razón. Y si hubiera leído los comentarios también me hubiera percatado que lo de i = j ya se menciona.
Es falso, basta tomar los conjuntos A={1,2,3}; subconjunto de {1,2,3,4,5}.
Petronicio,
El conjunto A que has dicho no cumple las condiciones. Ya que 1 y 3 pertenecen a A pero 1+3=4 no pertenece a A… ni 2+3=5 tampoco pertenece a A. (siendo 4 menor que n y 5 igual a n)
Acido, entonces esa condición hace que el conjunto A sea vacío debido a que si a
(que es el más alto del conjunto A) le sumas otro número de A el resultado no pertenece a A.
Y el enunciado dice «entonces» lo que significa que no es información adicional, sólo es un resultado de la información ya entregada y también debería poder ser demostrable.
No Petronicio. Por ejemplo: Si el subconjunto A de {1, 2,…, n} es este mismo {1, 2, …, n} (es decir m=n) entonces se cumplen las condiciones del problema: solo basta tomar las parejas de números que suman < ó igual que n, i.e. cualquier emparejamiento con los i,j < n/2 o también emparejados como en la famosa fórmula de la suma de los n primeros números naturales {(n-1)+1, (n-2)+2,….(n-1/2)+(n+1/2), n/2+n/2} (si n fuera par) y entonces dichas sumas sí están contenidas en A; el resto de sumas no y las desechamos.
Perdón, en el mensaje anterior la lista de parejas sumadas debería acabar en {…,(n-2)/2 + n/2, ((n-1)/2 + (n-1)/2)}.
Petronicio,
El enunciado dice cualesquiera elementos de A cuya suma sea menor que n y que siempre dicha suma debe pertenecer a A.
Por tanto, si es el elemento mayor de A ( a_m ) es por ejemplo n entonces al sumarle otro elemento la suma será mayor que n y no es necesario que dicha suma pertenezca a A. Otro ejemplo, si A no tiene el elemento 1 y a_m = n – 1 entonces a_m + a_i = n – 1 + a_i será mayor que n ya que a_i es mayor que 1…
Un ejemplo: sea el conjunto {2, 3, 4, 5} que ni es vacío ni es el ejemplo sencillo que contiene todos los elementos, se cumple que la suma de a_m y otro elemento es mayor que n=5 así que 5+2 no debe pertenecer a A (por ser mayor que n). Y otros elementos cuya suma es menor como 2+2 = 4 sí pertenecen a A. Por supuesto, dicho conjunto cumple la desigualdad. (2+3+4+5)/4 = 3.5 es mayor que (n+1)/2 = 3
Otro ejemplo más sencillo con n=5 : A = {2, 4} (múltiplos de 2 menores que n+1=6)
Y otro ejemplo más A = {3} (múltiplos de 3 menores que 6)
Respecto a la palabra «entonces» no siempre que aparece es para expresar algo que puede deducirse de lo anterior.
Por ejemplo «Sea B un subconjunto de {1, 2} que cumple que para cualquier elemento x, si x es par entonces x es menor que 2»
En este caso, el «entonces» es una condición que deben cumplir los elementos del conjunto B (sólo si es par… entonces… ) pero que todos los números sean menores que 2 no es algo que se deduzca de lo anterior, es sólo una condición que hemos definido. No puede ser B={2} porque 2 es par y no es menor que 2… pero puede ser B={1}
No termino de ver la pista de Manzano :
Algo se me escapa. Esta claro para i=1 e m-i+1=m pero no lo veo para el resto de sumas.
¿Alguien me lo puede aclarar?
Antonio,
Yo tampoco lo veía a la primera. Quizá te ayude el comentario de Golvano
golvano | 11 de noviembre de 2013 | 23:17
o el mio posterior a ese…
Pero intentaré decirlo más claro (por reducción al absurdo).
* Supongamos que no se cumple a(i) + a(m-i+1) >= n+1
Suponer eso es equivalente a decir que
a(i) + a(m-i+1) es menor o igual a n (y por tanto debe pertenecer a A)
Nótese que a(m-i+1) que es el elemento i-ésimo empezando por arriba.
Para i=1 sería el primero empezando por arriba (el mayor, el último)
Para i=2 sería el segundo empezando por arriba (el penúltimo)
Etc.
Entonces hacemos i sumas:
a(1)+a(m-i+1) ,
a(2)+ a(m-i+1)
… hasta
a(i) + a(m-i+1)
son i sumas distintas y mayores que ese elemento a(m-i+1) (el i-esimo empezando por arriba) y menores o iguales que n (ya que hemos supuesto que la suma mayor de ellas lo es) que deberían pertenecer a A !!!
Eso es lo mismo que decir que hay i números en A mayores que ese !!!
y ya no sería el i-esimo empezando por arriba.
Para i=1 sería como decir que hay un número mayor que el mayor…
Para i=2 … dos números mayores que el penúltimo…
Etc…
Por tanto para todo i se cumple que es mayor o igual que n+1 porque de lo contrario entramos en contradicción (o absurdo).
Gracias por la aclaracion, Acido.