viernes, 26 de septiembre de 2014

Problema del día. Combinatoria. (Antonio)

Sea un entero positivo. Encuentra el menor entero con la siguiente propiedad; Dados cualesquiera numeros reales     tal que y   para , es posible dividir estos numeros en conjuntos (algunos de ellos tal vez vacios)  tal que la suma de los numeros en cada conjunto es a lo mas .

9 comentarios:

  1. olvide ponerles cuanto tiempo seria optimo intentar el problema, por el nivel que se supone que tiene, deberia salir en una hora y media aprox.

    ResponderEliminar
  2. antonio dime si puedo llegar a terminarlo por donde estoy intentando, estoy viendo dos casos: si algún Ai+Aj es menor o igual a 1 o si ningún Ai+Aj es menor o igual a uno, del segundo caso saco que 2n-1 es la minima k que cumple el problema, y del primer caso no avanzo mas que agarro esos Ai+Aj como un conjunto y trabajo con los d-2 Ai´s restantes, ya que no he sacado nada interesante, dime que piensas?

    ResponderEliminar
  3. mmm como sacas que cuando ningun Ai+Aj es menor o igual entonces k debe ser al menos 2n-1?, es interesante lo que haces de dividir en esos dos casos, de hecho vas bien, por un lado es probar que k debe ser al menos 2n-1, y con el primer caso trata de llegar a que con 2n-1 conjuntos siempre sera suficiente, fijate que si Ai+Aj es menor a 1 entonces a esos dos numeros los puedes poner en el mismo conjunto

    ResponderEliminar
  4. para demostrar que en ningun Ai+Aj menor o igual a 1 solo pones d=2n y los agarras de 2 en 2 y queda la suma de tus Ai´s mayor a n por lo tanto d menor o igual a 2n-1 y como k va a ser la cantidad de Ai´s, k es almenos 2n-1, es decir, para este caso k= 2n-1 es el menor k que cumple, intente desde el inicio el agarrarme esos dos Ai+Aj menores o iguales a 1 y ponerlos en un conjunto pero me quedan desigualdaes feas porque puede ser n-1<suma de Ai´s menos los dos anteriores, pero con ella no puedo trabajar jeje.

    ResponderEliminar
  5. Este comentario ha sido eliminado por el autor.

    ResponderEliminar
  6. ok, , pues ya tienes que k debe ser al menos 2n-1, si quieres hay te va un hint para ver que siempre es posible con 2n-1 subconjuntos, sean b1,b2,..bk los k subconjuntos suponte que pasa si k<2n-1, como tratamos de hacer el arreglo con el minimo numero de subconjuntos entonces bi+bj siempre es mayor que 1, usando que k<2n-1 trata de llegar a una contradiccion

    ResponderEliminar
  7. Esto es lo que llevo de la solución:
    Sí nos fijamos en que cumple para cualesquiera reales, cumple en especial cuando todos son iguales a n/2n-1 que es mayor que un medio. Como es mayor a un medio, sí ponemos a 2 de ellos en un mismo conjunto, la suma será mayor a 1. Por lo tanto, cada uno de ellos está en su propio conjunto. Entonces sabemos que k es al menos 2n-1

    ResponderEliminar
  8. Veamos que si todas las $a_{i}$ son menores o iguales a 1 entonces $d\geq{n}$ si $n\leq{d}\leq{2n-1}$ entonces hacemos $\frac{1}{2}<{a_{i}}=\frac{n}{d}\leq{1}$ y la suma de las $a_{i}$s sera 1 con cada fraccion mayor a 1 por lo que los k subconjuntos tendran que ser de un solo elemento, entonces $k\geq{2n-1}$, luego nos fijamos en que si tenemos d=2n, los dividimos en n parejas: $(a_{1}+a_{2})+(a_{3}+a_{4})+...+(a_{2n-1}+a_{2n})$ no se puede que tengamos las n parejas mayores a 1 porque la suma seria mayor a n entonces hay una pareja que su suma es menor o igual a 1, la hacemos un subconjunto y ya tenemos 2n-1, para $d\geq{2n+1}$ con mas razon estara esta pareja, entonces lo iremos reduciendo tomando este tipo de parejas, al ir reduciendo nos quedan las mismas condiciones de que todos son menores o iguales a 1 entonces siempre lo podemos hacer hasta llegar a 2n-1 $\therefore k=2n-1$

    ResponderEliminar
  9. Pepe: bien lo que hiciste, ya demostraste k>=2n-1, ahora demustra 2n-1>=k, lee la sugerencia que le di a quique.
    Arturo:bien.

    ResponderEliminar