lunes, 28 de diciembre de 2009

Problema del Dia

Ahora tenemos uno de combinatoria del Putnam. En el examen no me salió, pero el problema es muy bonito.

Un subconjunto de {1,2,3,...,n} se llama "mediocre" si para cualesquiera dos elementos a,b del subconjunto,si su promedio es entero se tiene que también esta en el subconjunto. Sea A(n) el número de subconjuntos mediocres de {1,2,...,n}. (Por ejemplo, todos los subconjuntos de {1,2,3} excepto {1,3} son mediocres, así que A(3) = 7). Encuentra todos los números naturales n tales que A(n+2) -2A(n+1) + A(n) = 1.

13 comentarios:

  1. Una correcion: lei el problema y se me hizo raro ver porque {1,2} era mediocre, y busque en internet el problema, resulta que en realidad dice:
    si para cualesquiera dos elementos a,b del subconjunto, si su promedio es entero, entonces tambien esta en el subconjunto

    ResponderEliminar
  2. Aproveche mis poderes administrativos para corregirlo =P

    ResponderEliminar
  3. Gracias Isai. Es bueno checar conmigo, seguido copio problemas mal.

    ResponderEliminar
  4. Estos problemas me desivian de mis estudios :)

    ResponderEliminar
  5. Ya mero me sale, espero mañana ya tener solucion jeje

    ResponderEliminar
  6. ah caray.. akabo de comenzar el problema.. pero no le entiendo... porque {1,3} no s mediocre, si su promedio es 2 y si esta en el conjunto?? mas bien los que son mediocres serian {1,2} y {2,3},,.. aunque su promedio no sea entero,pero si el promedio es entero, entonces esta en el intervalo [1,n], ya que el promedio entero es menor a n... mmmhh esta bien la condicion de ser entero?? o que alguien me explique por favor bien el problema.. se ve interesante xD

    saludos!

    ResponderEliminar
  7. ok. no bueno..ia le entendi bien al problema.. al menos en la parte de porque {1,3} no es mediocre... jeje
    pero aun tengo una duda.. porque A(3)= 7... si {1,2} y {2,3} tampoco son mediocres, puesto que su promedio no es entero??.. asi k A(3)=5 no?.. xfa.. aclarenme esto =S

    ResponderEliminar
  8. Se abre el telón y se ven dos sistemas lineales incompatibles.
    ¿Cómo se llama la película ?
    Kramer contra Kramer.


    y sarrus??? es el k esta narrando

    ResponderEliminar
  9. HAHAHA ESTE ME MATO:


    LA EVOLUCIÓN DE LAS MATEMÁTICAS

    1950's
    Un campesino vende una bolsa de patatas por 1000 pesetas. El costo
    es 4/5 del precio de venta. ¿Cuál ha sido su beneficio ?

    1960's
    Un campesino vende una bolsa de patatas por 1000 pesetas. El costo
    es 4/5 del precio de venta, es decir, 800 pesetas. Cual ha sido su beneficio?

    1970's (nuevas matemáticas)
    Un campesino intercambia un conjunto P de patatas por un conjunto D
    de dinero. La cardinalidad del conjunto D es 1000, y cada elemento de D vale
    una unidad de pesetas. Dibuja 1000 puntos gordos representando los elementos
    de D. El conjunto C de los costes de producción esta formado por 200 puntos
    gordos menos que D. Representa C como un subconjunto de D y da la respuesta
    correcta a la pregunta: cual es la cardinalidad del conjunto de beneficios ?
    (Haz todos los dibujos en rojo.)

    1980's
    Un campesino vende una bolsa de patatas por 1000 pesetas. Sus costos
    de produccion son 800 pesetas y su beneficio son 200 pesetas. Subraya la
    palabra "patatas" y discutelo con tus compañeros.

    1990's
    Un zerdo capitalista injustamente consige 200 pseta po una volsa
    de pattas Hannalica ete tecsto en fusca d'errrore contenido, grasmatika i
    puntuazion, y aluejo ekspresa tu punto de fista sobreste metod d'aserse
    rico.


    A POCO NO__ ?? discutelo con tus compañeros..

    ResponderEliminar
  10. Si su promedio es entero entonces esta en el subconjunto.
    {1,2} es mediocre, dice que para cualquier par de elementos si el promedio es entero entonces tambien esta en el subconjunto, como el promedio de 1,2 no es entero entonces no tiene que estar en el subconjunto.

    ResponderEliminar
  11. *** SPOILER ***
    Sin perdida de generalidad todos los subconjuntos estan ordenados.

    Es claro que todos los subconjuntos de 0 o 1 elementos son mediocres.

    Primero demostrare que los pares e impares se alternan en todo conjunto mediocre de dos o mas elementos. Supongamos que un subconjunto mediocre tiene dos elementos seguidos de la misma paridad a y b. Pero como son de la misma paridad su promedio (a+b)/2 existe, y tenemos que min(a,b)<(a+b)/2<max(a,b) por lo que tenemos una contradiccion al hecho de que son seguidos.

    Con este hecho es facil ver que ningun subconjunto mediocre es una sucesion aritmetica de periodo par.

    Ahora demostrare que toda sucesion aritmetica de periodo impar es mediocre. Escribamos el subconjunto como:
    m,m+d,m+2d...,m+kd
    y consideremos dos elementos m+jd y m+hd con j<h ambos de la misma paridad. Ahora escribamos su promedio m + d(j+h)/2, como son de la misma paridad entonces j y h son de la misma paridad, por lo que (j+h)/2 es entero y j<(j+h)/2<h, y como mcd(d,2)=1 el numero es de la forma m+xd y por lo tanto m+xd es parte de la sucesion aritmetica.

    Ahora demostrare el reverso, todo subconjunto mediocre es una sucesion aritmetica de periodo impar.
    Caso de dos elementos, m,m+d son de diferente paridad entonces d es impar.
    Caso de tres o mas elementos.Supongamos que existe un subconjunto mediocre que no esta en sucesion aritmetica, entonces podemos encontrar 3 elementos seguidos que no estan en sucesion aritmetica, m,m+d1,m+d1+d2 con d1=/=d2. Como el subconjunto es mediocre, y m,m+d1+d2 son de la misma paridad entonces su promedio existe, m+(d1+d2)/2, pero el unico elemento entre estos dos es m+d1 entonces. m+(d1+d2)/2=m+d1
    d1+d2=2d1
    d1=d2
    Lo cual es una contradiccion.

    Ya que encontramos todos los subconjuntos mediocres ahora pasemos a contarlos.

    Consideremos dos elementos a,b del conjunto y contemos todas las sucesiones aritmeticas de perido impar que empiezen en a y terminen en b.
    Escribimos a como m y b como m+jd
    como m=m+jd mod d
    entonces a = b mod d
    y d|b-a, entonces tenemos que encontrar todas las d que dividan a b-a y ademas d es impar. Llamemos S(x) a la funcion que nos entregue el numero de divisores impares de x, entonces el numero de sucesiones aritmeticas entre b y a es s(b-a).

    Para {1,2,...,n,n+1} tenemos que A(n+1)= A(n) + algo, donde algo es el numero de subconjuntos mediocres que se agregan al poner el n+1.
    Entonces algo= 1 + s(n+1-1) +s(n+1-2) + ... +s(n+1-n)= 1 + s(1)+s(2)+...+s(n). Donde el 1 se agrega por el subconjunto de un elemento.

    Entonces tenemos que:
    A(n+1)=A(n)+1+s(1)+s(2)+...+s(n)
    A(n+2)=A(n+1)+1+s(1)+s(2)+...+s(n+1)

    A(n+2)-A(n+1)= 1+s(1)+...+s(n+1)
    A(n)-A(n+1)=-(1+s(1)+...+s(n))
    entonces
    A(n+2)-2A(n+1)+A(n)=s(n+1)=1
    Entonces n+1 tiene un solo divisor impar y todos los demas pares.
    Como 1|n+1 entonces ese es nuestro divisor impar y por lo tanto n+1=2^k
    n=2^k-1

    *** FIN DEL SPOILER ***

    Nota: Lo de la s(x) no fue idea mia yo me quede hasta donde dije A(n+1)=A(n)+algo jajaja

    ResponderEliminar
  12. OHH IO TMB LO ESTOI HACIENDO X RECURSION!!

    ResponderEliminar