Loading [MathJax]/jax/output/HTML-CSS/jax.js

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.

43 comentarios:

  1. el primer y el ultimo numero de la mesa se consideran consecutivos?

    ResponderBorrar
  2. Este blog ha sido eliminado por un administrador de blog.

    ResponderBorrar
  3. bueno 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 2n0mod2

    ResponderBorrar
  4. Este blog ha sido eliminado por un administrador de blog.

    ResponderBorrar
  5. y 2y0mod2 11mod2 por lo tanto 2y+11mod2 entonces no existe tal numero
    no se si este bien mi respuesta pero no se a ke se refieren con numeros consecutivos

    ResponderBorrar
    Respuestas
    1. numeros consecutivos se refiere a numeros que estan uno al lado del otro en la mesa, aparte, no necesariamente son 2

      Borrar
  6. consecutivo significa que esta uno enseguida del otro o significa +1?
    ejemplo 6-7, 2012-2013?

    ResponderBorrar
  7. Si antonio, el primer y ultimo numero se consideran consecutivos

    ResponderBorrar
  8. consecutivo significa que esta uno enseguida del otro

    ResponderBorrar
  9. Tengo 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.

    ResponderBorrar
    Respuestas
    1. no chacon, por que dice numeros consecutivos, mas no necesariamente tiene q ser 2.
      en 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

      Borrar
  10. Definimos cada miembro de la mesa como a1,a2,...,an+1 Vemos que a1+a2+...+an+1=3n
    Para 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: (3n1n) será el número de combinaciones posibles tales que todo ai es un entero positivo.
    Y vemos que para que sumen 2n hay (2n1n) 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.

    ResponderBorrar
    Respuestas
    1. no entiendo de donde salio (3n1n)

      Borrar
    2. ricardo yo hice lo mismo que tu pero me atore en "Entoncestenemosque:(3n1n) seráelnúmerodecombinacionesposiblestalesquetodoa_iesunenteropositivo."despues de hacer eso, ya no supe que hacer, como llegaste a eso?

      Borrar
  11. Este comentario ha sido eliminado por el autor.

    ResponderBorrar
  12. Llamamos a los números alrededor de la mesa a1,a2,a3,...,an,an+1.
    Consideramos 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+...+aia1+a2+...+aj(modn), entonces a1+a2+...+aj(a1+a2+...+ai)=ai+1+ai+2+...+aj0(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.

    ResponderBorrar
  13. http://www.facebook.com/photo.php?fbid=388498091220991&set=a.384382948299172.87730.100001824112299&type=3&theater

    ResponderBorrar
    Respuestas
    1. con n > 3 no puedes garantizar que esos numeros sean consecutivos

      Borrar
  14. Si 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.
    Para 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 (n1) congruencias, donde o se repite al menos una congruencia o una congruencia se repite 3 veces.

    ResponderBorrar
    Respuestas
    1. Para completar mi solución:
      Sean 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+...+ara1+a2+a3+...+akz(modn)a1+a2+a3+...+ar(a1+a2+a3+...+ak)=ak+1+ak+2+...+ar0(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: 3nn=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

      Borrar
  15. Sean x1,x2,x3,,xn,xn+1 los numeros acomodados sobre la mesa.
    Nos 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++xk1
    Donde 1kn+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++xaxk+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++xb0modn
    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.

    ResponderBorrar
  16. Supongamos que no existen numeros consecutivos que sumen 2n, entonces tampoco habra numeros consecutivos que sumen n.
    Ahora 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.

    ResponderBorrar
  17. yo lo que ise fue que un conjunto de sumas de numeros las cuales serian:
    a1
    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

    ResponderBorrar
    Respuestas
    1. Como sabemos que ya hemos acabado? digo, la suma puede ser un multiplo de n mas no el multiplo de n q queremos

      Borrar
  18. Tenemos que los numeros en la mesa seran a1,a2,a3,...,an,an+1. Los ordenamos y los vamos sumando de la siguiente manera.
    a1
    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

    ResponderBorrar
  19. Tenemos n+1 sumas que veremos en congruencia modulo n

    a1
    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

    ResponderBorrar
  20. Comence con esta idea porque pense que con "logica" seria mas sencillo:
    Si 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 (n1) 3's, un 1 y un 0. Esto cuando n2 . 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:
    ax0(mod3) Se eligen algunos 3 .
    ax1(mod3) Se eligen algunos 3 y el 2 .
    ax2(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 :
    a10,1,,(n2),(n1)(modn)
    a1+a20,1,,(n2),(n1)(modn)
    a1+a2+a30,1,,(n2),(n1)(modn)

    a1+a2+a3++an10,1,,(n2),(n1)(modn)
    a1+a2+a3++an1+an0,1,,(n2),(n1)(modn)
    a1+a2+a3+...+an+an+10,1,,(n2),(n1)(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.

    ResponderBorrar
  21. Donde dice:
    "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!

    ResponderBorrar
  22. https://plus.google.com/u/0/photos/100066737030455211829/albums/posts

    ResponderBorrar
  23. Tenemos los miembros en la mesa desde a1, a2, a3…. an, an+1. Y todos sumados nos da como resultado 3n.
    Podrí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??

    ResponderBorrar