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.
martes, 13 de septiembre de 2011
Problema del dia (combinatoria) 13/09/11
Hay nk+k−1 duendes. Al principio cada duende tiene exactamente n amigos entre los demás duendes. Cada día cada duende se convierte en amigo de los amigos de sus amigos. Prueba que después de infinitos días no pueden existir k o más grupos de amigos
Supongamos que hay al menos k grupos al final. El promedio de duendes por grupo es ≤nk+k−1k=n+1−1k Por casillas de promedio, uno de los grupos va a tener menor igual del promedio, entonces va a tener maximo n. Pero al principio cada duende era amigo de otros n, entonces su "grupo" de amigos inicial era de n+1, contandolo a el mismo, y en el grupo que mencionamos habia n. Por lo tanto nuestra suposición de que si se puede es falsa, y no pueden existir k o mas grupos.
El menor de los grupos de amigos que puede formarse es de n+1 duendes, en el que los n amigos de un duende serían todos amigos entre sí al inicio. Si hubiera k grupos, entonces tendrían que haber k(n+1)=nk+k duendes, pero solo hay nk+k-1 duendes, por lo que al menos un grupo debería ser de máximo n duendes para que hubiera k grupos, pero el mínimo de duendes por grupo es de n+1 por lo que hay menos de k grupos.
bueno lo primero que hize fue factorizar kn+k-1 en k(n+1)-1 entonces me di cuenta que al iniciar hay k-1 grupos de n+1 duendes y un grupo de n duendes por el -1 que hay en el numero de duendes entonces cuando pasen infinitos dias entonces cada que pase un dia el grupo de n va conocer n personas mas pero faltara 1 y cuando se conoscan los k-1 grupos mas habra k-1 duendes que el grupo de n no conocio
tenemos que al principio abrian menos de k grupos de n+1 duendes enyonces tenemos que si existieran k grupos serian de n+1-(1/k) duendes que es menos de lo del principio y tiene que ser mas de lo del principio y entonces tenemos que si fueran k-1 que serian de n+1+ un numero x pero a lo que qiero llegar es que si fueran menos de k grupos la cantidad de duendes serian mas de n+1 y eso es aceptable por lo tanto tenemos que no puede ser k omas grupos
yo supuse que si podrán haber K o mas grupos de amigos, y cada grupo sera de por lo menos n+1 duendes entonces sabemos que hay (K)(n+1) duendes lo que es igual a que hay NK+K duendes pero nos dicen que hay NK+K-1 duendes y aquí llegamos a una contradicción entonces no puede haber K o mas grupos de duendes
digamos que si se pueden obtener k grupos, entonces si al principio teniamos que cada duende conocia a n duendes, mas si mismo, serian n+1. si hay k grupos entonces tendriamos k(n+1)=kn+k, pero nos falta un duende que debemos restar, asi que al principio no se puede tener k grupos. si lo continuamos con el siquiente dia, tenemos que cada duende conoce a n amigos de sus n amigos, teniendo que conoce a n^2 duentes, si es que los n duendes no se conocen entre los mismos grupos, mas si mismo, y diciendo que hay k grupos seria k(n^2+1)=kn^2+k>kn+k. si hay duendes que se conocen entre si en los mismos grupos entonces conocera a n+r duendes y esto con lo anterior tambien sera mayor al primer dia. si en ningun momento se puede tener k grupos completos, entonces llegamos a la contradiccion.
Cada duende tiene n amigos, los grupos por lo tanto van a ser de n+1, ya que el no se contaba entre los n, suponiendo que fueran k grupos, en algun momento, entonces el promedio de duendes por grupo seria de (nk+k-1)/k duendes que = n+1-1/k, por lo que como n+1-1/k<n+1, esto no será posible ya que cada día aumentara la cantidad de duendes por grupo o quedara igual si los amigos fueran amigos entre ellos mismos nomas, pero en ambos casos no disminuira para quedar en n+1-1/k, por lo tanto no pueden haber k grupos
si lo hacemos por contradiccion y decimos que si hubiera un grupo al fin de infinitos dias
tendriamos que el promedio de de duendes por grupo seria los duendes que hay al principio (nk+k-1)entre los grupos que serian (k)
y como dice que cada duende tiene a n amigos entonses quiere decir que no se cuenta el, por lo tanto serian n+1 duendes, entonses el promedio seria menor al total de duendes.
Como cada dia aumentaria la cantidad de duendes por grupo entonses no podria disminuir a tal grado de que los grupos queden con n duendes
la minima cantidad que esos grupos de duendes del final seria n+1 ya que en ese grupo se cumple que cada duende es amigo de n duendes y ya que todos son amigos entre si su numero no varia de principio a fin, ahora supongamos que al final existen k+1 grupo de duendes entonces minimo deberia de haber (n+1)(k+1)=nk+n+k+1 duendes pero solo existen nk+k−1 duendes por lo que no puede existir un numero mas grande a k ahora supongamos que hay k grupos k(n+1)=kn+n sigue habiendo un duende de mas por lo que llegamos a una contradiccion y solo pueden existir un numero de grupos menores a k
En un principio cada duende conoce a n otros, contándose a si mismo se obtienen n+1 duendes. Suponiendo existen k o mas grupos de duendes. Si existen más, suponiendo k+1, el total de duendes seria al menos igual a: (k+1)(n+1) lo que nos da nk+k+n+1. Pero solo se cuenta con nk+k–1 duendes, por lo que se llega a que no es posible tener grupos más grandes a k. Si fuesen exactamente k grupos, donde cada uno contaría con al menos n+1 duendes, obtenemos: nk+k, un duende mas a los contados inicialmente. Queda demostrado que no es posible tener k o mas grupos de amigos después de infinitos días.
En si, tengo que demostrar que despues de infinitos dias todos los dundes se conocen?
ResponderBorrarno que despues de infinitos dias no hay mas de k grupos donde los duendes de un grupo no conocen a los de otro
ResponderBorrarSupongamos que hay al menos k grupos al final.
ResponderBorrarEl promedio de duendes por grupo es
≤nk+k−1k=n+1−1k
Por casillas de promedio, uno de los grupos va a tener menor igual del promedio, entonces va a tener maximo n. Pero al principio cada duende era amigo de otros n, entonces su "grupo" de amigos inicial era de n+1, contandolo a el mismo, y en el grupo que mencionamos habia n.
Por lo tanto nuestra suposición de que si se puede es falsa, y no pueden existir k o mas grupos.
El menor de los grupos de amigos que puede formarse es de n+1 duendes, en el que los n amigos de un duende serían todos amigos entre sí al inicio. Si hubiera k grupos, entonces tendrían que haber k(n+1)=nk+k duendes, pero solo hay nk+k-1 duendes, por lo que al menos un grupo debería ser de máximo n duendes para que hubiera k grupos, pero el mínimo de duendes por grupo es de n+1 por lo que hay menos de k grupos.
ResponderBorrarbueno lo primero que hize fue factorizar kn+k-1 en k(n+1)-1 entonces me di cuenta que al iniciar hay k-1 grupos de n+1 duendes y un grupo de n duendes por el -1 que hay en el numero de duendes entonces cuando pasen infinitos dias entonces cada que pase un dia el grupo de n va conocer n personas mas pero faltara 1 y cuando se conoscan los k-1 grupos mas habra k-1 duendes que el grupo de n no conocio
ResponderBorrarEste comentario ha sido eliminado por el autor.
ResponderBorrartenemos que al principio abrian menos de k grupos de n+1 duendes
ResponderBorrarenyonces tenemos que si existieran k grupos serian de n+1-(1/k) duendes que es menos de lo del principio y tiene que ser mas de lo del principio y entonces tenemos que si fueran k-1 que serian de n+1+ un numero x pero a lo que qiero llegar es que si fueran menos de k grupos la cantidad de duendes serian mas de n+1 y eso es aceptable
por lo tanto tenemos que no puede ser k omas grupos
yo supuse que si podrán haber K o mas grupos de amigos, y cada grupo sera de por lo menos n+1 duendes entonces sabemos que hay (K)(n+1) duendes lo que es igual a que hay NK+K duendes pero nos dicen que hay NK+K-1 duendes y aquí llegamos a una contradicción entonces no puede haber K o mas grupos de duendes
ResponderBorrardigamos que si se pueden obtener k grupos, entonces si al principio teniamos que cada duende conocia a n duendes, mas si mismo, serian n+1. si hay k grupos entonces tendriamos k(n+1)=kn+k, pero nos falta un duende que debemos restar, asi que al principio no se puede tener k grupos. si lo continuamos con el siquiente dia, tenemos que cada duende conoce a n amigos de sus n amigos, teniendo que conoce a n^2 duentes, si es que los n duendes no se conocen entre los mismos grupos, mas si mismo, y diciendo que hay k grupos seria k(n^2+1)=kn^2+k>kn+k. si hay duendes que se conocen entre si en los mismos grupos entonces conocera a n+r duendes y esto con lo anterior tambien sera mayor al primer dia. si en ningun momento se puede tener k grupos completos, entonces llegamos a la contradiccion.
ResponderBorrarCada duende tiene n amigos, los grupos por lo tanto van a ser de n+1, ya que el no se contaba entre los n, suponiendo que fueran k grupos, en algun momento, entonces el promedio de duendes por grupo seria de (nk+k-1)/k duendes que = n+1-1/k, por lo que como n+1-1/k<n+1, esto no será posible ya que cada día aumentara la cantidad de duendes por grupo o quedara igual si los amigos fueran amigos entre ellos mismos nomas, pero en ambos casos no disminuira para quedar en n+1-1/k, por lo tanto no pueden haber k grupos
ResponderBorrarsi lo hacemos por contradiccion y decimos que si hubiera un grupo al fin de infinitos dias
ResponderBorrartendriamos que el promedio de de duendes por grupo seria los duendes que hay al principio (nk+k-1)entre los grupos que serian (k)
y como dice que cada duende tiene a n amigos entonses quiere decir que no se cuenta el, por lo tanto serian n+1 duendes, entonses el promedio seria menor al total de duendes.
Como cada dia aumentaria la cantidad de duendes por grupo entonses no podria disminuir a tal grado de que los grupos queden con n duendes
la minima cantidad que esos grupos de duendes del final seria n+1 ya que en ese grupo se cumple que cada duende es amigo de n duendes y ya que todos son amigos entre si su numero no varia de principio a fin, ahora supongamos que al final existen k+1 grupo de duendes entonces minimo deberia de haber (n+1)(k+1)=nk+n+k+1 duendes pero solo existen nk+k−1 duendes por lo que no puede existir un numero mas grande a k
ResponderBorrarahora supongamos que hay k grupos k(n+1)=kn+n sigue habiendo un duende de mas por lo que llegamos a una contradiccion y solo pueden existir un numero de grupos menores a k
En un principio cada duende conoce a n otros, contándose a si mismo se obtienen n+1 duendes. Suponiendo existen k o mas grupos de duendes.
ResponderBorrarSi existen más, suponiendo k+1, el total de duendes seria al menos igual a: (k+1)(n+1) lo que nos da nk+k+n+1. Pero solo se cuenta con nk+k–1 duendes, por lo que se llega a que no es posible tener grupos más grandes a k.
Si fuesen exactamente k grupos, donde cada uno contaría con al menos n+1 duendes, obtenemos: nk+k, un duende mas a los contados inicialmente. Queda demostrado que no es posible tener k o mas grupos de amigos después de infinitos días.
**Fecha limite para la C: 21 de septiembre***
ResponderBorrar