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.
¿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.
Tienes un 20% de descuento y envío gratis en toda la web de La Tostadora con al menos dos artículos. Usa el código GAUSSIANOS entrando con el enlace de la imagen.
Y usando el código REBAJAS tienes un 30% de descuento hasta el 8 de agosto con al menos 3 artículos.
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.
Información Bitacoras.com
Valora en Bitacoras.com: 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 element…
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
Un problema muy bonito.
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
Un contraejemplo para 11:
{10,11,12,13,14,15,16,17,18,19,20}
Demostración: Sean los elementos de un subconjunto con la propiedad de que ninguna suma pertenece al subconjunto. Consideremos los 23 enteros positivos: Estos enteros son todos distintos excepto quizás dos de ellos porque existe la posibilidad de que para algún (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 ? ¿Qué ocurre si en… Lee más »
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… Lee más »
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…
No se cómo se corrige. Lo escribo otra vez corrigiendo una errata. Demostración: Sean los elementos de un subconjunto con la propiedad de que ninguna suma , pertenece al subconjunto. Consideremos los 23 enteros positivos: Estos enteros son todos distintos excepto quizás dos de ellos porque existe la posibilidad de que para algún (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 ¿Qué es… Lee más »
Las posibles sumas (con repeticiones) obtenidas con parejas de nuestro subconjunto (llamémoslo ) es , supongamos entonces que ninguna de estas parejas dan como suma un elemento de , entonces todas estas sumas dan como resultado un elemento de los 8 restantes, digamos que estos 8 elementos son . Lo que hay que notar aquí es que para cada hay formas de escribir a como suma de 2 números si es par y si es impar, así Y la última expresión de la cadena es mayor o igual que el número de formas de expresar los como suma de dos… Lee más »
Se entiende que las sumas no tienen por qué ser menores o iguales que 20.
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
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… Lee más »
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… Lee más »
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.
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… Lee más »
Queremos probar que, dado el conjunto
y cualquier subconjunto suyo cuyo cardinal sea igual a 
; se pueden encontrar dos números 
y 
tales que 
.
Para ello es suficiente considerar el subconjunto
. Si existen dos elementos en él (
) tales que 
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.
Parece ser que si
es el máximo del conjunto 
de 12 elementos, hay 11 distintos resultados para 
con 
. En el caso que no debe darse de que 
, se consideran 10 resultados distintos factibles.
, 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.
En el peor de los casos, con 10 resultados distintos, estos 10 resultados deben pertenecer al complemento de
Del 1 al 20 siempre cumplirá todo aquel subconjunto menor a 12 = {1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12} donde se garantizará que la suma de dos de ellos estará dentro del rango, veamos.
El subconjunto con más elementos en los que se cumple que la suma de ninguna pareja está en el mismo es {10,11,12,13,14,15,16,17,18,19,20} que tiene 11 elementos. Cualquier intento de añadir otro elemento supondría que habría que sacar un elemento de dicho subconjunto para que se siguiere cumpliendo la condición expuesta. Por lo que todos cumplirán la negación de la misma, es decir, que cualquier subconjunto de 12 verifica que la suma de cualquier pareja está en el subconjunto. De hecho cualquier subconjunto que no incluya al indicado tendrá más de una pareja que verifique que su suma está en dicho… Lee más »