La comunidad de olímpicos, ex-olímpicos, entrenadores y seguidores de la Olimpiada en Chihuahua, wherever they are in the world. Por supuesto cualquier olímpico mexicano (para que parar ahí, de todo el mundo pues), esta invitado a comentar.
sábado, 8 de septiembre de 2012
Problema del día. Combinatoria (8 de septiembre)
En una mesa redonda se colocan n+1 números enteros positivos que suman 3n. Muestra que existen números consecutivos que suman 2n.
Suscribirse a:
Comentarios de la entrada (Atom)
el primer y el ultimo numero de la mesa se consideran consecutivos?
ResponderBorrarEste blog ha sido eliminado por un administrador de blog.
ResponderBorrarbueno podemos representar dos numeros consecutivos como y y+1 entonces su suma es 2y+1 y nos dice que es lo mismo qeu 2n y sabemos que 2n≡0mod2
ResponderBorrarEste blog ha sido eliminado por un administrador de blog.
ResponderBorrartodos los numeros son consecutivos?
ResponderBorrary 2y≡0mod2 1≡1mod2 por lo tanto 2y+1≡1mod2 entonces no existe tal numero
ResponderBorrarno se si este bien mi respuesta pero no se a ke se refieren con numeros consecutivos
numeros consecutivos se refiere a numeros que estan uno al lado del otro en la mesa, aparte, no necesariamente son 2
Borrarconsecutivo significa que esta uno enseguida del otro o significa +1?
ResponderBorrarejemplo 6-7, 2012-2013?
uno enseguida de otro
BorrarSi antonio, el primer y ultimo numero se consideran consecutivos
ResponderBorrarconsecutivo significa que esta uno enseguida del otro
ResponderBorrarTengo una duda. En el caso n=3, ¿4,1,3,1 no es un contra ejemplo? 4+1+3+1=9=3(3), pero 2(3)=6 y 4+1=5, 1+3=4, 3+1=4, 1+4=5.
ResponderBorrarno chacon, por que dice numeros consecutivos, mas no necesariamente tiene q ser 2.
Borraren el caso que describes 4 + 1 + 1 = 6, y no tienes manera de acomodarlos de tal manera de que no sean los 3 numeros consecutivos
Definimos cada miembro de la mesa como a1,a2,...,an+1 Vemos que a1+a2+...+an+1=3n
ResponderBorrarPara ver los posibles acomodos que puede haber de los enteros positivos, usaremos separadores. Ponemos 3n en una ilera, y pondremos n separadores, pero como no queremos que haya dos separadores juntos, quitaremos 1 a 3n pues así aseguraremos que todo ai será a lo menos 1.
Entonces tenemos que: (3n−1n) será el número de combinaciones posibles tales que todo ai es un entero positivo.
Y vemos que para que sumen 2n hay (2n−1n) posibles formas en que hay una suma de 2n en este conjunto.
Para el caso en que n=1
Sumaran 3
Y hay 2 números
Tenemos a1=1ya2=2 o a2=1ya1=2
(21)=2 = Número de posibles combinaciones que existen
(11)=1 = Número de ai que nos cumplen, y sabemos que serán consecutivos, debido a que es un circulo y habrá una combinación que cumpla.
Por casillas, tenemos que el número total de combinaciones que suman 3n es mayor al que suman 2n , así que habrá por lo menos un caso tal que cumpla.
Por lo tanto, así queda demostrado.
Q.E.D.
no entiendo de donde salio (3n−1n)
Borrarricardo yo hice lo mismo que tu pero me atore en "Entoncestenemosque:(3n−1n) seráelnúmerodecombinacionesposiblestalesquetodoa_iesunenteropositivo."despues de hacer eso, ya no supe que hacer, como llegaste a eso?
BorrarEste comentario ha sido eliminado por el autor.
ResponderBorrarLlamamos a los números alrededor de la mesa a1,a2,a3,...,an,an+1.
ResponderBorrarConsideramos las sumas a1,a1+a2,a1+a2+a3,...,a1+a2+...an+1 y sus congruencias módulo n, como hay n+1 sumas y n congruencias, por Casillas alguna congruencia se repite.
Tomamos ai,aj con i<j tales que a1+a2+...+ai≡a1+a2+...+aj(modn), entonces a1+a2+...+aj−(a1+a2+...+ai)=ai+1+ai+2+...+aj≡0(modn).
Como esta suma es congruente a 0 mod n hay 2 posibilidades: que sea n o que sea 2n. Si la suma es 2n, como son números consecutivos, ese esos son los números que buscamos. Si la suma es n, como la suma total es 3n, los demás números que no están en esta suma suman 2n y son consecutivos, entonces son los que buscamos.
Por lo tanto hay números consecutivos que suman 2n.
bien chacon te ganaste una carita feliz =)
Borrarhttp://www.facebook.com/photo.php?fbid=388498091220991&set=a.384382948299172.87730.100001824112299&type=3&theater
ResponderBorrarcon n > 3 no puedes garantizar que esos numeros sean consecutivos
BorrarSi lo vemos modulo n, sabemos que existen n congruencias modulo n, si tenemos n+1 términos, al menos una congruencia se va a repetir.
ResponderBorrarPara que ninguna suma de números consecutivos sea 2n, tampoco debe ser n (pues si todo suma 3n y una parte suma n, el resto sumará 2n), por lo que lo que queremos evitar es que números consecutivos sumen un múltiplo de n. Si no queremos múltiplos de n⇒ tampoco consideramos la congruencia 0 (modn), así que tenemos (n−1) congruencias, donde o se repite al menos una congruencia o una congruencia se repite 3 veces.
Para completar mi solución:
BorrarSean a1,a2,a3,...,an+1 los n+1 números en la mesa y en ese orden, tenemos n+1 sumas: a1, a1+a2, a1+a2+a3, a1+a2+a3+...+an+1, pero modulo n solo tiene n congruencias, entonces se repite al menos una, sea:
a1+a2+a3+...+ar≡a1+a2+a3+...+ak≡z(modn)⇒a1+a2+a3+...+ar−(a1+a2+a3+...+ak)=ak+1+ak+2+...+ar≡0(modn), lo cual es un conjunto de números consecutivos tales que su suma es múltiplo de n, esto puede ser: (n,2n), para el primer caso, el resto de los números suma: 3n−n=2n, en el segundo caso esos números suman 2n, entonces siempre tendremos números consecutivos que sumen 2n Q.E.D.
* (k,r) deben satisfacer que: 0<k<r<n+2 para ser parte de los números en la mesa y poder obtener la diferencia positiva: ak+1+ak+2+...+ar
=) carita feliz arturo
BorrarSean x1,x2,x3,⋯,xn,xn+1 los numeros acomodados sobre la mesa.
ResponderBorrarNos fijamos en que tenemos a lo mas n congurncias diferentes modulo n.
Ahora nos fijamos en las sumas:
xk
xk+xk+1
xk+xk+1+xk+2
⋮
xk+xk+1+xk+2+⋯+xk−1
Donde 1≤k≤n+1
Es facil ver que hay n+1 sumas, y n congruencias, por lo tanto
hay al menos dos sumas con la misma congruencia.
Sean xa,xb ,con a\textlessb, numeros en la mesa tales que:
xk+xk+1+xk+2+⋯+xa≡xk+xk+1+xk+2+⋯+xbmodn
Ahora veamos su diferencia:
(xk+xk+1+xk+2+⋯+xb)−(xk+xk+1+xk+2+⋯+xa)≡0modn
⇒xa+1+xa+2+⋯+xb≡0modn
Luego tenemos una serie de numeros consecutivos tales que su suma es multiplo de n.
Para esto, tenemos cuatro posibilidades: que sea 3n, 2n, n o 0
No puede ser 3n o 0 ya que esto implicaria que xa=xb
Luego, si es igual a 2n, ya acabamos, y si es igual a n, todos los demas numeros que sobran suman 2n, y acabamos.
∴Siempre es posible satisfacer las condiciones del problema.
LC te ganaste una carita feliz =)
BorrarSupongamos que no existen numeros consecutivos que sumen 2n, entonces tampoco habra numeros consecutivos que sumen n.
ResponderBorrarAhora me fijo que hay mas de n sumas entonces es facil ver que habra dos con la misma congruencia modulo n pero tambien me fijo en las siguientes n+1 sumas: a1,a1+a2,...,a1+a2+...+an+1. Como 2 tienen la misma congruencia modulo n al restar esas dos sumas con la misma congruencia modulo n nos van a quedar la suma de los términos no comunes de ambas sumas. Pero esa suma sera congruente a 0 modulo n. entonces como esa suma es menor a 3n esa suma solo puede ser n o 2n lo cual es una contradicción a lo propuesto al principio.
Entonces si hay numeros consecutivos que sumen 2n.
antonio te has ganado una carita feliz =)
BorrarEste comentario ha sido eliminado por el autor.
ResponderBorraryo lo que ise fue que un conjunto de sumas de numeros las cuales serian:
ResponderBorrara1
a1+a2
a1+a2+a3
⋯
a1+a2+a3⋯+a(n+1)
y me fijo que como ninguno es cero ni negativo entonces todas esas sumas son diferentes porque como que una contiene a las anteriores y asi y luego son n+1 sumas entonces ay almenos dos q tienen la misma congruencia modulo n y si las restamos nos vana quedar la suma de numeros consecutivos que no teniana en comun (ya que habiamos explicado q una coontiene a la otra)y ese resultado deve de ser congruente a 0 modulo n y acavamos
Como sabemos que ya hemos acabado? digo, la suma puede ser un multiplo de n mas no el multiplo de n q queremos
Borrarrumbo al nacional
ResponderBorrarTenemos que los numeros en la mesa seran a1,a2,a3,...,an,an+1. Los ordenamos y los vamos sumando de la siguiente manera.
ResponderBorrara1
a1+a2
a1+a2+a3
.
.
.
a1+a2+a3+...+an
a1+a2+a3+...+an+an+1
Como son n+1 sumas sabemos que habra al menos una congruencia que se repetira modulo n. Una vez hayamos las que se repiten, las restamos y nos quedara una sucesion que sera congruente a 0 modulo n. Si es congruente a 0 modulo n → sera n o 2n. Si es 2n entonces habremos encontrado el conjunto de numeros consecutivos que queriamos pero si es n entonces el conjunto que buscabamos es el resto de los numeros.
Por lo tanto siempre habra numeros consecutivos que sumaran 2n
carita feliz =)
BorrarTenemos n+1 sumas que veremos en congruencia modulo n
ResponderBorrara1
a1+a2
...
a1+a2+...+an+1
Al ser n+1 sumas, por casillas a lo menos habrá una suma con la misma congruencia modulo n
Nos encontramos que al restar los terminos comunes, y tomar los no comunes, habrá un número de terminos tales su suma será congruente a 0 modulo n Y esta suma será menor a 3n
Siendo así, tenemos que si es 2n hemos terminado
Si es n el resto de los terminos sumará 2n y acabamos. Q.E.D
carita feliz =)
BorrarComence con esta idea porque pense que con "logica" seria mas sencillo:
ResponderBorrarSi sabemos que que la suma total es 3n y que va a haber números consecutivos que suman 2n.
⇒ El resto de los números van a sumar n , que es lo que intentaré demostrar
Digamos que los n+1 números son (n−1) 3's, un 1 y un 0. Esto cuando n≥2 . Cuando n=1 lo veré después.
En ese caso específico, siempre se cumple que hay números consecutivos que suman n ; así en cada caso:
∙ax≅0(mod3)→ Se eligen algunos 3 .
∙ax≅1(mod3)→ Se eligen algunos 3 y el 2 .
∙ax≅2(mod3)→ Se eligen algunos 3 y el 1 .
Para hacer los demás casos es eligiendo cualesquiera dos dígitos consecutivos y restarle 1 a alguno de ellos y sumarselo a otro.
De esta forma la suma entre esos digitos permanecera igual y seguirá cumpliendo para cualquier caso.
Aqui intentaba demostrar que para cualquier suma, tendriamos que ir expandiendo el rango de numeros que elegimos. Pero ya no pude y lo de una forma mucho mas sencilla :P
Tenemos las sumas de a1 con sus posibles congruencias con n :
a1≡0,1,⋯,(n−2),(n−1)(modn)
a1+a2≡0,1,⋯,(n−2),(n−1)(modn)
a1+a2+a3≡0,1,⋯,(n−2),(n−1)(modn)
⋮
a1+a2+a3+⋯+an−1≡0,1,⋯,(n−2),(n−1)(modn)
a1+a2+a3+⋯+an−1+an≡0,1,⋯,(n−2),(n−1)(modn)
a1+a2+a3+...+an+an+1≡0,1,⋯,(n−2),(n−1)(modn)
Podemos ver que hay (n+1) sumas y unicamente n
⇒ Va a haber al menos una congruencia repetida.
Aqui pense que ya habia quedado terminado el problema, pero luego entendi q esa congruencia puede ser cualquiera y no unicamente 0 . Luego en base a lo que hize en otro problema supe que hacer :P
Si restamos una suma a la otra, sus congruencias iguales se resttarian y la respuesta sería 0 , es decir un multiplo de n.
Sabemos que todas las a's suman 3n, asi que la respuesta de la resta es un multiplo de n menor a 3n y mayor a 0, porque solo puede ser 0 si restamos la misma suma pero aqui hablamos de dos sumas distintas. Entonces el resultado puede ser 2n o n . Q.E.D.
Donde dice:
ResponderBorrar"Podemos ver que hay (n+1) sumas y unicamente n "
Debe ser n congruencias :P
P.D. Perdón por las faltas de ortografía!
carita feliz =) no te apures, yo no se mucho de ortografia
Borrarhttps://plus.google.com/u/0/photos/100066737030455211829/albums/posts
ResponderBorrar=) carita feliz leo
BorrarTenemos los miembros en la mesa desde a1, a2, a3…. an, an+1. Y todos sumados nos da como resultado 3n.
ResponderBorrarPodría ser, que n=3, así serían 4 en la mesa y los números puestos podrían ser 3, 3, 2,1. Y como no necesariamente tienen que ir en orden ascendente o descendente, sino cualesquiera n números enteros positivos, entonces se podría dar esa combinación, la cual, al sumar los primeros dos números consecutivos: 3+3=6=2n, y además 3+3+2+1=9=3n.
Otras posibles combinaciones para que el resultado de 3n, serian 1, 1, 1, 6, y este podría contar como un contra ejemplo, porque el enunciado dice números consecutivos y el seis ya en si es igual a 2n, y se puede mostrar que no necesariamente números consecutivos sumen 2n, no??
en un grupo de k consecutivos 6 es un grupo con k=1
Borrar