Jugando con los 20 primeros enteros positivos

Volvemos esta semana a proponer un problema, como es habitual. Ahí va:

Dados los primeros 20 enteros positivos, demostrar que en todo subconjunto de 12 de ellos siempre hay dos números cuya suma da como resultado un elemento del propio subconjunto.

A por él.


Visto en la lista de Snark.

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. Sin meterme en la demostarción encontrar un contraejemplo para 10 elementos es sencillo:

    {1,3,5,…,17,19} no cumple

    Voy a hacer un programa para ver que pasa con 11 elementos

    Publica una respuesta
  2. Una sencilla prueba de ello lo tenemos con el primer subconjunto “12”:
    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
    Tenemos:
    1+11=12
    2+10=12
    3+9=12
    4+8=12
    n+(m-n)=m

    Publica una respuesta
  3. Demostración: Sean x_1,…,x_{12} los elementos de un subconjunto con la propiedad de que ninguna suma x_i+x_j, i<j, pertenece al subconjunto. Consideremos los 23 enteros positivos: x_1, . . . ,x_{12},  x_{12} - x_1, . . . .,x_{12} - x_{11}.

    Estos enteros son todos distintos excepto quizás dos de ellos porque existe la posibilidad de que x_i=x_{11}-x_i para algún i (pero sólo para uno).

    Es decir, entre los 23 enteros que hemos mencionado hay al menos 22 distintos. Pero eso es imposible porque todos ellos son mayores o iguales que 1, y menores o iguales que 20.

    q.e.d.

    El mismo argumento se generaliza para cualquier n.
    ¿Qués lo que hay que poner en lugar de 12?

    ¿Qué ocurre si en lugar de sumas de dos elementos consideramos sumas de tres elementos? ¿qué es lo que habría que poner en lugar de la parte entera de (n+1)/2?

    Publica una respuesta
  4. El problema claramente equivale a ver que existen un par de elementos a,b en el subconjunto (sea S) de modo que a-b=c pertenece a S (pues eso pasa si y solo si b+c=a). Aunque el enunciado no lo indica presupongo que nos interesa que b y c sean distintos

    Sea S el subconjunto y sea m su máximo.

    Hay 11 elementos de S estrictamente menores que m.
    Hay 10 elementos de la forma m-x, donde x va recorriendo S (digo 10, pues pudiera ser que m-x=x para uno de esos x).

    Como m es menor o igual que 20 queda probado por principio del palomar.

    Publica una respuesta
  5. Acabo de ver la demostración anterior, creo que falla en que alguno de los xi si puede valer 20 y se puede llegar a contrajemplo como bien se mostró arriba. Aunque me entran mis dudas de si se puede considerar o no dos veces el mismo elemento para hacer la suma…

    Publica una respuesta
  6. No se cómo se corrige. Lo escribo otra vez corrigiendo una errata.

    Demostración: Sean x_1,…,x_{12} los elementos de un subconjunto con la propiedad de que ninguna suma x_i+x_j, i<j, pertenece al subconjunto. Consideremos los 23 enteros positivos: x_1, . . . ,x_{12},  x_{12} - x_1, . . . .,x_{12} - x_{11}.

    Estos enteros son todos distintos excepto quizás dos de ellos porque existe la posibilidad de que x_i=x_{12}-x_i para algún i (pero sólo para uno).

    Es decir, entre los 23 enteros que hemos mencionado hay al menos 22 distintos. Pero eso es imposible porque todos ellos son mayores o iguales que 1, y menores o iguales que 20.

    q.e.d.

    El mismo argumento se generaliza para cualquier n. ¿Qué es lo que hay que poner en lugar de 12?

    ¿Qué ocurre, para cualquier n, si en lugar de sumas de dos elementos consideramos sumas de tres elementos?

    Publica una respuesta
  7. Las posibles sumas (con repeticiones) obtenidas con parejas de nuestro subconjunto (llamémoslo S) es \binom{2}{12}, supongamos entonces que ninguna de estas parejas dan como suma un elemento de S, entonces todas estas sumas dan como resultado un elemento de los 8 restantes, digamos que estos 8 elementos son n_{1},…,n_{8}.

    Lo que hay que notar aquí es que para cada n hay n/2 formas de escribir a n como suma de 2 números si n es par y (n-1)/2 si es impar, así

    66=\binom{2}{12}=\sum_{n=13}^{20}n/2 \geq \sum_{i=1}^{8}n_{i}/2

    Y la última expresión de la cadena es mayor o igual que el número de formas de expresar los n_{i} como suma de dos términos. Además, el caso de la igualdad sucede sólo cuando S=\{1,2,3,…,8\}, en el cual pues 1+2=3\in S.

    Así, tenemos en la desigualdad presentada arriba una desigualdad estricta, entonces tenemos más sumas en nuestro conjunto que posibles formas de expresar los elementos n_{i} como dos sumandos, de donde al menos una suma no es ninguno de los n_{i}, es decir, esta suma está en S.

    Publica una respuesta
  8. Se entiende que las sumas no tienen por qué ser menores o iguales que 20.

    Publica una respuesta
  9. Para generalizar el problema se vé fácilmente siguiendo la indicación de Mmonchi que

    para Cn = {1,2,…,n-1,n} siempre tenemos que para p = entero(n/2) +1 el conjunto Sp={p,p+1,…,n-1,n} es un contraejemplo.

    Siguiendo los criterios vistos antes p+1 sería el caso

    Publica una respuesta
  10. Buenas . Voy a proporcionar la primera solución que se me ocurrio. Supongo que no tan elegante pero es valida.Añado que es una versión muy parecida a la de Daniel , pero yo la he pensado por reduccion al absurdo.

    Nos disponemos a crear un subconjunto de 12 elementos que no cumpla la condición. Elijamos el número minimo n . Ahora creamos 10 pares nuevos de numeros menores de 20 ( o 11) restandole n a cada elemento del subconjunto menos n (son nuevos por la condicion de que no cumple la condicion pedida), pero como ya teniamos 12 numeros anteriores en total suman 22 lo que no es posible dado el cardinal de el conjunto dado.Aprovecho a plantear un problema bastante dificil para mi , a ver si alguien consigue incarle el diente:
    Determinar todos los números enteros positivos a y b tales que (a^4-a^2+1)/ab-1
    es un numero entero positivo. Tiene una curiosa propiedad de simetria que no alcanzo a comprender ( Ni si quiera se si ocurre para todas las soluciones)

    Publica una respuesta
  11. Martin Ortiz, muy interesante tu problema.. Te diré lo que he averiguado tanteando las soluciones.
    Considera la siguiente sucesión recurrente: x(1)=1, x(2)=2, … x(n)=4*x(n-1)-x(n-2).
    Los valores que adopta son: 1, 2, 7, 26, 97, …
    Cada dos valores consecutivos, EN CUALQUIER ORDEN, dan soluciones enteras a la ecuación que propones como a,b o b,a.
    Esto implica que si (a^4-a^2+1)/(ab-1) es entero también lo será (b^4-b^2+1)/(ab-1).
    La secuencia está documentada en la OEIS como A001075 (consúltala en Google) como solución de otras ecuaciones diofánticas. Curiosamente también es la secuencia de los denominadores de las sucesivas reducidas del desarrollo en serie de RAÍZ de 3.

    Publica una respuesta
  12. Martin Ortiz, la sucesión que da los resultados tiene como fórmula general la siguiente:
    x(n)=(((2+raiz(3))^n+(2-raiz(3)^n))/2 para n= 0, 1, 2, 3, …
    Cada dos términos consecutivos dan los valores a,b o b,a que producen resultados enteros en tu fórmula.

    Publica una respuesta
  13. Hola, como yo he estado pensando el problema es así, como estamos hablando de un conjunto que posee un buen orden, dado que tiene primer y ultimo elemento tomamos al conjunto que contiene al menor de esta forma {1,2,3,4,5,6,7,8,9,10,11,12} si sumamos al mínimo de estos, con el mismo vemos que este esta contenido en el subconjunto, si tomamos ahora un subconjunto que contenga al ultimo elemento {8,9,10,11,12,13,14,15,16,17,18,19,20} y de aquí seleccionamos al 10+10, podemos observar que este esta contenido, en el subconjunto hasta aquí he podido acotar y ver que siempre esta contenido la suma de dos de ellos, justo ahí ya no se como continuar pues desde mi punto de vista por aquí le debo hacer algún análisis combinatorio o quizás es el camino equivocado

    Publica una respuesta
  14. Queremos probar que, dado el conjunto {1,2,3,…,20} y cualquier subconjunto suyo cuyo cardinal sea igual a 12; se pueden encontrar dos números a y b tales que a+bleq20.

    Para ello es suficiente considerar el subconjunto {9,10,11,12,13,14,15,16,17,18,19,20}. Si existen dos elementos en él (a,y,b) tales que a+b leq 20 entonces queda demostrado el enunciado de este problema.

    Por ejemplo 9+10 si queremos que el resultado esté contenido de forma estricta en el conjunto inicial o 9+11 si se incluye al 20.

    Publica una respuesta
  15. Parece ser que si m es el máximo del conjunto S de 12 elementos, hay 11 distintos resultados para m-x con x  in S. En el caso que no debe darse de que m-x=x, se consideran 10 resultados distintos factibles.
    En el peor de los casos, con 10 resultados distintos, estos 10 resultados deben pertenecer al complemento de S, de tamaño 8, pero como son más de 8 resultados distintos (10) no puede darse esto y se llega a una contradicción.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com Valora en Bitacoras.com: Volvemos esta semana a proponer un problema, como es habitual. Ahí va: Dados los…

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 *