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.
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:
ResponderBorrarsi para cualesquiera dos elementos a,b del subconjunto, si su promedio es entero, entonces tambien esta en el subconjunto
Aproveche mis poderes administrativos para corregirlo =P
ResponderBorrarGracias Isai. Es bueno checar conmigo, seguido copio problemas mal.
ResponderBorrarEstos problemas me desivian de mis estudios :)
ResponderBorrarYa mero me sale, espero mañana ya tener solucion jeje
ResponderBorrarah 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
ResponderBorrarsaludos!
perdon.. menor o igual a n
ResponderBorrarok. no bueno..ia le entendi bien al problema.. al menos en la parte de porque {1,3} no es mediocre... jeje
ResponderBorrarpero 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
Se abre el telón y se ven dos sistemas lineales incompatibles.
ResponderBorrar¿Cómo se llama la película ?
Kramer contra Kramer.
y sarrus??? es el k esta narrando
HAHAHA ESTE ME MATO:
ResponderBorrarLA 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..
Si su promedio es entero entonces esta en el subconjunto.
ResponderBorrar{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.
*** SPOILER ***
ResponderBorrarSin 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
OHH IO TMB LO ESTOI HACIENDO X RECURSION!!
ResponderBorrar