Prueba la desigualdad

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

Sea A=\{a_1,a_2, \ldots , a_m \} un subconjunto de números enteros positivos del conjunto \{ 1,2, \ldots , n \} (con m,n números enteros positivos) que cumple que para cualesquiera dos elementos a_i,a_j con a_i+a_j \leq n (1 \leq i \leq j \leq m) entonces a_i+a_j también pertenece al propio A.

Prueba entonces que:

\cfrac{a_1+a_2+ \ldots + a_m}{m} \geq \cfrac{n+1}{2}

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.

30 Comentarios

  1. 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

    Publica una respuesta
  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.

    Publica una respuesta
  3. 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)

    Publica una respuesta
  4. 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.

    Publica una respuesta
  5. 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.

    Publica una respuesta
  6. 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.

    Publica una respuesta
  7. 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À.

    Publica una respuesta
  8. 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?

    Publica una respuesta
  9. 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.

    Publica una respuesta
  10. 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 )

    Publica una respuesta
  11. Ácido, ese “a(intermedio)” ha de ser mayor o igual que \frac{n+1}{2} ya que de lo contrario a(intermedio) no podría ser el intermedio.

    Publica una respuesta
  12. Un ejemplo del razonamiento a seguir:
    Asumiedo que los elementos están ordenados de menor a mayor.

    Si a_{1} + a_{m} \leq n , entonces a_{m} < a_{1} + a_{m} \in A, contradiciendo que a_{m} era el máximo de A, luego a_{1} + a_{m} \geq n+1.

    Si a_{2} + a_{m-1} \leq n, entonces a_{m-1} < a_{2} + a_{m-1} \in A, contradiciendo que a_{m-1} era el penúltimo, luego a_{2} + a_{m-1} \geq n+1.

    Y así…

    Publica una respuesta
  13. 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.

    Publica una respuesta
  14. 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 a_1 hasta a_k) por encima, y ya no sería el elemento k. Si son impares, emparejas el central consigo mismo y aplicas el mismo razonamiento.

    Publica una respuesta
  15. Karl, no te lo puedo garantizar, pero si a_{2} + a_{m-1} = a_{m} , entonces a_{m-1} < a_{m-1} + a_{1} < a_{2} + a_{m-1} = a_{m}
    De nuevo se incumple el hecho de que a_{m-1} sea el penúltimo.

    Ácido, suscribo el comentario de Golvano previo al mío.

    Publica una respuesta
  16. 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.

    Publica una respuesta
  17. 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.

    Publica una respuesta
  18. 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 😉

    Publica una respuesta
  19. 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.

    Publica una respuesta
  20. Es falso, basta tomar los conjuntos A={1,2,3}; subconjunto de {1,2,3,4,5}.

    Publica una respuesta
  21. 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)

    Publica una respuesta
  22. Acido, entonces esa condición hace que el conjunto A sea vacío debido a que si a a_m (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.

    Publica una respuesta
  23. 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.

    Publica una respuesta
  24. 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)}.

    Publica una respuesta
  25. 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}

    Publica una respuesta
  26. No termino de ver la pista de Manzano :

    a_i+a_{m-i+1} >= n+1 para todo i

    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?

    Publica una respuesta
  27. 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).

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com Valora en Bitacoras.com: Os dejo hoy lunes el problema de esta semana. Ahí va: Sea un subconjunto…

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 *