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 \le k \le \frac {n^2 + n}{2} $ existe un subconjunto de elementos distintos entre si $ \{ 1, 2, \cdots, n \} $ cuya suma seas $k$
Para $n=1$, $\frac{n^2+n}{2}=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$, $\frac{n^2+n}{2}=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 \} $. $\frac{n^2+n}{2} =1+2+3+...+n$. Supongamos que se puede para n, entonces todos los números hasta $\frac{n^2+n}{2}$ se pueden escribir como suma de números distintos entre 1 y n. Para $n+1$, podemos hacer todos los números hasta $\frac{n^2+n}{2}$ igual que para n. Para las $n+1$ k restantes ($1+2+...+n= \frac{n^2+n}{2} < k \le \frac{(n+1)^2+(n+1)}{2} =1+2+...+(n+1) $), tomamos las últimos n+1 k's de n (para $n \ge 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 + \cdots + (n-2) + (n-1) + n = \frac{(n)(n+1)}{2} = \frac{n^2 + n}{2}$ Para que la suma sea algo entre $1$ y $\frac{n^2 + n}{2}$ debemos quitar ciertos números del subconjunto. $*$ SUMA $\rightarrow$ {SUBCONJUNTO} $*1 \rightarrow 1$ $*2 \rightarrow 2$ $\vdots$ $*(n-1) \rightarrow (n-1)$ $*n \rightarrow n$ ---------- $*(n+1) \rightarrow n, 1$ $*(n+2) \rightarrow n, 2$ $\vdots$ $*(2n-2) \rightarrow n, (n-2)$ $*(2n-1) \rightarrow n, (n-1)$ ---------- $*(2n) \rightarrow n, (n-1), 1$ $*(2n+1) \rightarrow n, (n-1), 2$ $\vdots$ $*(3n-4) \rightarrow n, (n-1), (n-3)$ $*(3n-3) \rightarrow n, (n-1), (n-2)$ ---------- $\vdots$ $\vdots$
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 \le S \le \frac {n^2 + n}{2}$ Y sabemos que $1 \le k \le \frac {n^2 + n}{2}$ $\therefore \text{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\leq k\leq \frac{n^{2}+n}{2}=\frac{n(n+1)}{2}=1+2+3+\cdots n$ Y notamos que se puede formar cualquier suma con subconjuntos de $\{1, 2, \cdots n\}$ que este en el rango de valores de $k$: $1, 2, 3, \cdots n$ $n+1, n+2, n+3, \cdots n+(n-1)$ $n+(n-1)+1, n+(n-1)+2, n+(n-1)+3, \cdots n+(n-1)+(n-2)$ $\cdots$ $n+(n-1)+(n-2)+\cdots 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 $\frac{n^2+n}{2}$ 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 $\frac{n^2+n}{2}$ 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 $\frac{n^2+n}{2}$. 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=suma de algun subconjunto$ 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 $\frac{n(n+1)}{2}$ y sabemos que $\frac{n(n+1)}{2}\geq 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 $\frac{n(n+1)}{2}$ solo quitamos el o los numeros que sumados sean igual a $\frac{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 $\frac{n^2+n}{2}$ ya que $\frac{n^2+n}{2}=\frac{(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\le k \le \frac{n^2+n}{2}$ entonces alguna de esas sumas deve de ser $k$ y terminamos.
Para $n=1$, $\frac{n^2+n}{2}=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$, $\frac{n^2+n}{2}=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 \} $.
$\frac{n^2+n}{2} =1+2+3+...+n$.
Supongamos que se puede para n, entonces todos los números hasta $\frac{n^2+n}{2}$ se pueden escribir como suma de números distintos entre 1 y n.
Para $n+1$, podemos hacer todos los números hasta $\frac{n^2+n}{2}$ igual que para n. Para las $n+1$ k restantes ($1+2+...+n= \frac{n^2+n}{2} < k \le \frac{(n+1)^2+(n+1)}{2} =1+2+...+(n+1) $), tomamos las últimos n+1 k's de n (para $n \ge 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:
ResponderBorrar$1 = 1$
$1 + 2 + 3 + \cdots + (n-2) + (n-1) + n = \frac{(n)(n+1)}{2} = \frac{n^2 + n}{2}$
Para que la suma sea algo entre $1$ y $\frac{n^2 + n}{2}$ debemos quitar ciertos números del subconjunto.
$*$ SUMA $\rightarrow$ {SUBCONJUNTO}
$*1 \rightarrow 1$
$*2 \rightarrow 2$
$\vdots$
$*(n-1) \rightarrow (n-1)$
$*n \rightarrow n$
----------
$*(n+1) \rightarrow n, 1$
$*(n+2) \rightarrow n, 2$
$\vdots$
$*(2n-2) \rightarrow n, (n-2)$
$*(2n-1) \rightarrow n, (n-1)$
----------
$*(2n) \rightarrow n, (n-1), 1$
$*(2n+1) \rightarrow n, (n-1), 2$
$\vdots$
$*(3n-4) \rightarrow n, (n-1), (n-3)$
$*(3n-3) \rightarrow n, (n-1), (n-2)$
----------
$\vdots$
$\vdots$
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 \le S \le \frac {n^2 + n}{2}$
Y sabemos que $1 \le k \le \frac {n^2 + n}{2}$
$\therefore \text{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:
ResponderBorrar$1\leq k\leq \frac{n^{2}+n}{2}=\frac{n(n+1)}{2}=1+2+3+\cdots n$
Y notamos que se puede formar cualquier suma con subconjuntos de $\{1, 2, \cdots n\}$ que este en el rango de valores de $k$:
$1, 2, 3, \cdots n$
$n+1, n+2, n+3, \cdots n+(n-1)$
$n+(n-1)+1, n+(n-1)+2, n+(n-1)+3, \cdots n+(n-1)+(n-2)$
$\cdots$
$n+(n-1)+(n-2)+\cdots 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 $\frac{n^2+n}{2}$ 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 $\frac{n^2+n}{2}$ 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 $\frac{n^2+n}{2}$. 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 $\text{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=suma de algun subconjunto$ 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 $\frac{n(n+1)}{2}$ y sabemos que $\frac{n(n+1)}{2}\geq 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 $\frac{n(n+1)}{2}$ solo quitamos el o los numeros que sumados sean igual a $\frac{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 $\frac{n^2+n}{2}$ ya que
ResponderBorrar$\frac{n^2+n}{2}=\frac{(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\le k \le \frac{n^2+n}{2}$ 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