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, 22 de septiembre de 2012
Problema del día. 22 de septiembre (Combinatoria)
muestra que para cualquier entero k con 1≤k≤n2+n2 existe un subconjunto de elementos distintos entre si {1,2,⋯,n} cuya suma seas k
Para n=1, n2+n2=1 entonces la única k es 1, el conjunto es {1} y el subconjunto {1} tiene suma k. Para las demás n, usamos inducción. La base de inducción es n=2. Para n=2, n2+n2=3 entonces las posibles k son 1,2,3. El conjunto es {1,2}. Para k=1 tenemos el subconjunto {1}, para k=2 está {2} y para n=3 está {1,2}. n2+n2=1+2+3+...+n. Supongamos que se puede para n, entonces todos los números hasta n2+n2 se pueden escribir como suma de números distintos entre 1 y n. Para n+1, podemos hacer todos los números hasta n2+n2 igual que para n. Para las n+1 k restantes (1+2+...+n=n2+n2<k≤(n+1)2+(n+1)2=1+2+...+(n+1)), tomamos las últimos n+1 k's de n (para n≥2 podemos garantizar que hay al menos n+1 k porque están 1 y n) y les sumamos n+1, que es distinto a todos los demás elementos del subconjunto porque son a lo más n, entonces también se puede para n+1. Entonces si se puede con n se puede con n+1, como se puede para 2, se puede para todos los naturales.
Vemos la minima y maxima suma posible: 1=1 1+2+3+⋯+(n−2)+(n−1)+n=(n)(n+1)2=n2+n2 Para que la suma sea algo entre 1 y n2+n2 debemos quitar ciertos números del subconjunto. ∗ SUMA → {SUBCONJUNTO} ∗1→1 ∗2→2 ⋮ ∗(n−1)→(n−1) ∗n→n ---------- ∗(n+1)→n,1 ∗(n+2)→n,2 ⋮ ∗(2n−2)→n,(n−2) ∗(2n−1)→n,(n−1) ---------- ∗(2n)→n,(n−1),1 ∗(2n+1)→n,(n−1),2 ⋮ ∗(3n−4)→n,(n−1),(n−3) ∗(3n−3)→n,(n−1),(n−2) ---------- ⋮ ⋮
Tenemos que comenzamos usando el 1 y va aumentando hasta llegar a n . Luego se mantienen los números de la última suma y se pone el 1 y luego va aumentando hasta llegar a (n−1). Despues sucede lo mismo, se mantienen los números de la última suma y se agrega el 1 y aumenta hasta (n−2) . Y asi hasta llegar a la suma máxima. Aumenta hasta n , luego hasta (n−1), luego hasta (n−2) porque el numero mayor al que aumenta ya esta siendo utilizado y deben ser números distintos.
Y así podemos obtener cualquier suma S tal que: 1≤S≤n2+n2 Y sabemos que 1≤k≤n2+n2 ∴Q.E.D.
Agrupamos el conjunto en subconjuntos de la siguiente forma: {1},{2},{3},...,{n},{n,1},{n,2},...,{n,n-1},{n,n-1,1},{n,n-1,2},...,{n,n-1,n-2},{n,n-1,n-2,1},...,{n,n-1,n-2,...,3,2,1}. Luego vemos que comenzamos con el 1 y la suma de cada subconjunto va aumentando en 1. Como la suma del último subconjunto es [n(n-1)]/2, en total tenemos [n(n-1)]/2 subconjuntos con diferente suma, todas entre 1 y [n(n-1)]/2. QED
Tenemos que: 1≤k≤n2+n2=n(n+1)2=1+2+3+⋯n Y notamos que se puede formar cualquier suma con subconjuntos de {1,2,⋯n} que este en el rango de valores de k: 1,2,3,⋯n n+1,n+2,n+3,⋯n+(n−1) n+(n−1)+1,n+(n−1)+2,n+(n−1)+3,⋯n+(n−1)+(n−2) ⋯ n+(n−1)+(n−2)+⋯3+2+1 Notamos que la mayor y la menor suma coinciden con el mayor y el menor valor para k respectivamente y se tienen sumas consecutivas, por lo tanto se consideran todos los posibles valores. Q.E.D.
Como K esta entre los rangos de 1 y n2+n2 que es la suma de los numeros consecutivos hay que demostrar que en el conjunto {1,2,3,...,n} se pueden escoger términos tales que aparecen todas las sumas desde 1 hasta n2+n2 entonces esas sumas son las siguientes: {1},{2},{3},...{n},{1,n},{2,n}...{n-1,n}{1,n-1,n}... entonces me fijo que siempre es posible sumarle uno y seguirá así hasta llegar al conjunto {1,2,3,...,n} entonces aparecen todas las sumas desde el 1 hasta el n2+n2. Q.E.D
priemro nos damos cuenta que que n(n+1)/2= 1+2+3+4+...+n entonces 1 es myor o igual a k y k es mayor o igual a 1+2+3+4+...n entonces sabemos que tenemos un subconjunto de 1,2,3,...n entonces podemos decir que van a ver valores de n(n+1)/2 por lo tanto k es un subconjunto de n(n+1)/2, por lo tanto debe ser igual o menor
Queremos demostrar que k=sumadealgunsubconjunto Ese subconjunto se saca de 1,2,3,...,n. El subconjunto con la suma mas grande que podemos obtener de ahi es cuando los seleccionamos a todos. El resultado es n(n+1)2 y sabemos que n(n+1)2≥k Entonces cuando k es lo maximo posible, el subconjunto incluye a todos los numeros del conjunto 1,2,3,...,n. Cuando k es menor a n(n+1)2 solo quitamos el o los numeros que sumados sean igual a n(n+1)2−k (a esto le llamare "la diferencia") y los numeros que queden seran los del conjunto cuya suma sea igual a k
Siempre habra numeros que sumados sean igual a la diferencia. Esto es porque nos fijamos en si la diferencia es mayor a n. Si es asi, nos fijamos en si es mayor a n+(n−1). Si vuelve a ser mayor intentamos con n+(n−1)+(n−2) y asi sucesivamente hasta que lleguemos a una suma que sea mayor a la diferencia. Quitamos el numero mas chico que forma parte de la suma y le restamos a la diferencia todos los demas. El resultado sera el otro numero que quitemos y asi obtendremos un subconjunto cuya suma sea k
perdon por tardar, esta fue mi semana de examenes parciales :S http://www.facebook.com/photo.php?fbid=4668000502238&set=a.4586100454788.189149.1360331970&type=3&theater
nos fijamos que lo unico que tenemos que demostrar es que al subconjunto 1,2,3...n−1,n le podemos hacer tales cambios tal que la suma de todos los elementos de los subconjuntos alterados pueda ser cada uno de los numeros del 1 al n2+n2 ya que n2+n2=(n)(n+1)2 entonces nos fijamos en los soguinetes subconjuntos {1}{2}{3}\cdots{n}{n,1}{n,2}\cdots{n,n-1}{n,n-1,1}{n,n-1,2}\cdots{1,2,3\cdotsn entonces nos fijamos que siempre podemos sumrle uno y como 1≤k≤n2+n2 entonces alguna de esas sumas deve de ser k y terminamos.
Para n=1, n2+n2=1 entonces la única k es 1, el conjunto es {1} y el subconjunto {1} tiene suma k.
ResponderBorrarPara las demás n, usamos inducción. La base de inducción es n=2. Para n=2, n2+n2=3 entonces las posibles k son 1,2,3. El conjunto es {1,2}. Para k=1 tenemos el subconjunto {1}, para k=2 está {2} y para n=3 está {1,2}.
n2+n2=1+2+3+...+n.
Supongamos que se puede para n, entonces todos los números hasta n2+n2 se pueden escribir como suma de números distintos entre 1 y n.
Para n+1, podemos hacer todos los números hasta n2+n2 igual que para n. Para las n+1 k restantes (1+2+...+n=n2+n2<k≤(n+1)2+(n+1)2=1+2+...+(n+1)), tomamos las últimos n+1 k's de n (para n≥2 podemos garantizar que hay al menos n+1 k porque están 1 y n) y les sumamos n+1, que es distinto a todos los demás elementos del subconjunto porque son a lo más n, entonces también se puede para n+1.
Entonces si se puede con n se puede con n+1, como se puede para 2, se puede para todos los naturales.
Vemos la minima y maxima suma posible:
ResponderBorrar1=1
1+2+3+⋯+(n−2)+(n−1)+n=(n)(n+1)2=n2+n2
Para que la suma sea algo entre 1 y n2+n2 debemos quitar ciertos números del subconjunto.
∗ SUMA → {SUBCONJUNTO}
∗1→1
∗2→2
⋮
∗(n−1)→(n−1)
∗n→n
----------
∗(n+1)→n,1
∗(n+2)→n,2
⋮
∗(2n−2)→n,(n−2)
∗(2n−1)→n,(n−1)
----------
∗(2n)→n,(n−1),1
∗(2n+1)→n,(n−1),2
⋮
∗(3n−4)→n,(n−1),(n−3)
∗(3n−3)→n,(n−1),(n−2)
----------
⋮
⋮
Tenemos que comenzamos usando el 1 y va aumentando hasta llegar a n . Luego se mantienen los números de la última suma y se pone el 1 y luego va aumentando hasta llegar a (n−1). Despues sucede lo mismo, se mantienen los números de la última suma y se agrega el 1 y aumenta hasta (n−2) . Y asi hasta llegar a la suma máxima.
Aumenta hasta n , luego hasta (n−1), luego hasta (n−2) porque el numero mayor al que aumenta ya esta siendo utilizado y deben ser números distintos.
Y así podemos obtener cualquier suma S tal que:
1≤S≤n2+n2
Y sabemos que 1≤k≤n2+n2
∴Q.E.D.
El subconjunto debe de ser consecutivo???
ResponderBorrarno
BorrarAgrupamos el conjunto en subconjuntos de la siguiente forma: {1},{2},{3},...,{n},{n,1},{n,2},...,{n,n-1},{n,n-1,1},{n,n-1,2},...,{n,n-1,n-2},{n,n-1,n-2,1},...,{n,n-1,n-2,...,3,2,1}.
ResponderBorrarLuego vemos que comenzamos con el 1 y la suma de cada subconjunto va aumentando en 1. Como la suma del último subconjunto es [n(n-1)]/2, en total tenemos [n(n-1)]/2 subconjuntos con diferente suma, todas entre 1 y [n(n-1)]/2. QED
http://www.facebook.com/photo.php?fbid=389248664480287&set=a.389248274480326.91304.100001854706497&type=3&theater
ResponderBorrarTenemos que:
ResponderBorrar1≤k≤n2+n2=n(n+1)2=1+2+3+⋯n
Y notamos que se puede formar cualquier suma con subconjuntos de {1,2,⋯n} que este en el rango de valores de k:
1,2,3,⋯n
n+1,n+2,n+3,⋯n+(n−1)
n+(n−1)+1,n+(n−1)+2,n+(n−1)+3,⋯n+(n−1)+(n−2)
⋯
n+(n−1)+(n−2)+⋯3+2+1
Notamos que la mayor y la menor suma coinciden con el mayor y el menor valor para k respectivamente y se tienen sumas consecutivas, por lo tanto se consideran todos los posibles valores. Q.E.D.
Como K esta entre los rangos de 1 y n2+n2 que es la suma de los numeros consecutivos hay que demostrar que en el conjunto {1,2,3,...,n} se pueden escoger términos tales que aparecen todas las sumas desde 1 hasta n2+n2 entonces esas sumas son las siguientes:
ResponderBorrar{1},{2},{3},...{n},{1,n},{2,n}...{n-1,n}{1,n-1,n}... entonces me fijo que siempre es posible sumarle uno y seguirá así hasta llegar al conjunto {1,2,3,...,n} entonces aparecen todas las sumas desde el 1 hasta el n2+n2. Q.E.D
priemro nos damos cuenta que que n(n+1)/2= 1+2+3+4+...+n entonces
ResponderBorrar1 es myor o igual a k y k es mayor o igual a 1+2+3+4+...n
entonces sabemos que tenemos un subconjunto de 1,2,3,...n entonces podemos decir que van a ver valores de n(n+1)/2 por lo tanto k es un subconjunto de n(n+1)/2, por lo tanto debe ser igual o menor
Pero tienes que demostrar que para cualquier k se puede hacer la suma.
Borrarhttp://www.facebook.com/photo.php?fbid=393562640714536&set=a.384382948299172.87730.100001824112299&type=3&theater
ResponderBorrarhttp://s739.photobucket.com/albums/xx34/leo0_9506/Ommch/?action=view¤t=CAM000951.jpg#!oZZ1QQcurrentZZhttp%3A%2F%2Fs739.photobucket.com%2Falbums%2Fxx34%2Fleo0_9506%2FOmmch%2F%3Faction%3Dview%26current%3DCAM000951.jpg
ResponderBorrarRumbo al nacional
ResponderBorrarHay que demostrar que para cualquier k se puede hacer la suma.
BorrarQueremos demostrar que k=sumadealgunsubconjunto Ese subconjunto se saca de 1,2,3,...,n. El subconjunto con la suma mas grande que podemos obtener de ahi es cuando los seleccionamos a todos. El resultado es n(n+1)2 y sabemos que n(n+1)2≥k Entonces cuando k es lo maximo posible, el subconjunto incluye a todos los numeros del conjunto 1,2,3,...,n. Cuando k es menor a n(n+1)2 solo quitamos el o los numeros que sumados sean igual a n(n+1)2−k (a esto le llamare "la diferencia") y los numeros que queden seran los del conjunto cuya suma sea igual a k
ResponderBorrarSiempre habra numeros que sumados sean igual a la diferencia. Esto es porque nos fijamos en si la diferencia es mayor a n. Si es asi, nos fijamos en si es mayor a n+(n−1). Si vuelve a ser mayor intentamos con n+(n−1)+(n−2) y asi sucesivamente hasta que lleguemos a una suma que sea mayor a la diferencia. Quitamos el numero mas chico que forma parte de la suma y le restamos a la diferencia todos los demas. El resultado sera el otro numero que quitemos y asi obtendremos un subconjunto cuya suma sea k
perdon por tardar, esta fue mi semana de examenes parciales :S http://www.facebook.com/photo.php?fbid=4668000502238&set=a.4586100454788.189149.1360331970&type=3&theater
ResponderBorrarNo me queda claro el patron de los conjuntos que construiste.
Borrarnos fijamos que lo unico que tenemos que demostrar es que al subconjunto 1,2,3...n−1,n le podemos hacer tales cambios tal que la suma de todos los elementos de los subconjuntos alterados pueda ser cada uno de los numeros del 1 al n2+n2 ya que
ResponderBorrarn2+n2=(n)(n+1)2 entonces nos fijamos en los soguinetes subconjuntos {1}{2}{3}\cdots{n}{n,1}{n,2}\cdots{n,n-1}{n,n-1,1}{n,n-1,2}\cdots{1,2,3\cdotsn entonces nos fijamos que siempre podemos sumrle uno y como 1≤k≤n2+n2 entonces alguna de esas sumas deve de ser k y terminamos.
Cuando arregles tu LATEX te pongo tu carita feliz
BorrarEste comentario ha sido eliminado por el autor.
ResponderBorrar