Anuncio

Colapsar
No hay ningún anuncio todavía.

Enemigos en el parlamento

Colapsar
X
 
  • Filtro
  • Hora
  • Mostrar
Borrar todo
nuevos mensajes

  • Olimpiada Enemigos en el parlamento

    En un parlamento cada miembro tiene como mucho 3 enemigos. Demuestra que es posible dividir el parlamento en 2 grupos donde cada miembro tenga como mucho 1 enemigo en su propio grupo.

    - - - Actualizado - - -

    Pista:
    Ocultar contenido
    Separadlos en dos grupos de manera arbitraria. Si es el número de enemigos que tiene en su grupo el miembro i-ésimo () y , hacemos lo siguiente. Si para algún i se tiene que , pasamos a ese miembro de su grupo al otro (donde solo tendrá un enemigo). Probar que en tal caso decrece
    Última edición por angel relativamente; 02/03/2017, 00:39:16.
    [TEX=null]k_BN_A \cdot \dst \sum_{k=0}^{\infty} \dfrac{1}{k!} \cdot 50 \cdot 10_{\text{hex}} \cdot \dfrac{2\pi}{\omega} \cdot \sqrt{-1} \cdot \dfrac{\dd x} {\dd t } \cdot \boxed{^{16}_8\text{X}}[/TEX]

  • #2
    Re: Enemigos en el parlamento

    Hola.

    Imagino que debe haber alguna solucion más elegante, pero ahi va la mia.

    Ocultar contenido

    Los diputados que no tienen ningun enemigo, pueden ir a cualquier grupo. Lo mismo que los diputados que solo tienen un enemigo.

    Los diputados que tienen solo dos enemigos, pueden organizarse en filas: A-B-C-D-E-...., donde el quion indica "enemigo de". Estas filas acaban en diputados con un solo enemigo (ya tratados) o diputados de tres enemigos. Es facil acomodar estas filas de diputados, distribuyendolas en los dos grupos, de manera que no haya más de dos diputados consecutivos en el mismo grupo. Asi, fijado el grupo de los diputados de los extremos de la fila, se pueden acomodar los diputados del interior de la fila, alternando de uno o en uno o de dos en dos según convenga.

    El hueso duro de roer son los diputados con tres enemigos. Estos pueden visualizarse como los vertices de un poliedro, de forma que de cada vertice surgen tres lineas, que conectan el vertice de un diputado con los vertices de los diputados odiados. Para cada poliedro hay que asignar el grupo en el que estan los vertices, para cumplir la condicion. Voy a poner un ejemplo: Cuatro diputados que se odian. El diagrama seria un tetraedro, con vertices A,B,C,D. La signacion de grupos es que A y B van al grupo 1, y C y D van al 2.
    Podemos tener situaciones más complejas, por ejemplo 6 diputados cuyo diagrama de odios forma un prisma triangular. Ahi tendriamos 3 diputados, A,B,C que se odian entre si, otros 3 diputados E,F,G que se odian, y luego A odia a E, B a F y C a G. Aqui asignariamos A,B y G al grupo 1, y C,E,F al grupo 2.



    Saludos

    Comentario


    • #3
      Re: Enemigos en el parlamento

      Angel no me resulta obvio tu procedimiento. Si paso uno con dos o mas enemigos al otro grupo, puedo estar haciendo que en el segundo grupo, otro diputado (no el que he pasado), pase a tener dos o mas enemigos. No veo como ese procedimiento tiene a priori un final en el que en ambos grupos tengamos uno o ningun enemigos.

      Un saludo

      Comentario


      • #4
        Re: Enemigos en el parlamento

        Hace casi 4 meses que postee este problema, he tenido que re-estudiarlo
        Gracias por haberlo pensado, es un problema bonito. Algo que creo que sí has entendido, pero lo pongo por si a alguien no le parece obvio, es que la propiedad de ser enemigo es recíproca (si A es enemigo de B entonces B lo es de A).
        Con respecto a tu solución:
        Ocultar contenido
        Entiendo la idea, pero creo que se deja casos (y que a priori es difícil de saber si los cubres todos). Por ejemplo, no necesariamente los de dos enemigos puedes meterlos en una cadena. Si A tiene dos enemigos: B,C. B tiene por enemigos: A,C y C tiene por enemigos: B,A, estos tres forman un triángulo cerrado donde cada miembro tiene exactamente dos enemigos en su grupo.

        Escrito por carroza
        Angel no me resulta obvio tu procedimiento.
        No es obvio, pero paso a hacer la demostración detallada a ver si se entiende

        Ocultar contenido
        Supongamos que hay enemigos en el parlamento y denotémoslos . Los dividimos de manera arbitraria en dos grupos. Sea el número de enemigos de en su grupo y sea . Vamos a probar que, dado un con más de dos enemigos en su grupo (), cambiarlo de grupo reduce estrictamente el valor de . Tenemos 3 casos:

        -Supongamos y sean los 3 enemigos de en su grupo. Si cambiamos a de grupo tenemos que decrece 3 unidades, mientras que decrece cada uno una unidad. Como el resto de valores no se modifica, en total decrece 6 unidades.

        Para los dos siguientes casos supondremos y llamaremos a los dos enemigos en su grupo.


        -Si no tiene más enemigos, cambiarlo de grupo decrecerá en dos unidades, y en una unidad cada uno, por lo que decrece 4 unidades.


        -Si tiene un tercer enemigo en el otro grupo, cambiarlo de grupo decrecerá en una unidad (pasa de tener dos enemigos a tener uno), decrecerán también una unidad y aumentará una unidad. En total, decrece en 2 unidades.

        En general hemos visto que si para algún i, , cambiar de grupo a decrece estrictamente. Si iteramos el proceso, como es un entero no negativo eventualmente alcanzará un mínimo absoluto cuando .


        ¡Un saludo!
        Última edición por angel relativamente; 30/06/2017, 07:02:28.
        [TEX=null]k_BN_A \cdot \dst \sum_{k=0}^{\infty} \dfrac{1}{k!} \cdot 50 \cdot 10_{\text{hex}} \cdot \dfrac{2\pi}{\omega} \cdot \sqrt{-1} \cdot \dfrac{\dd x} {\dd t } \cdot \boxed{^{16}_8\text{X}}[/TEX]

        Comentario


        • #5
          Re: Enemigos en el parlamento

          Ok. Ahora lo entiendo. Habia interpretado E como la suma de enemigos dentro de un grupo. Ahora veo que es la suma de los enemigos dentro de los dos grupos.

          Solo una puntualización;
          Ocultar contenido

          No puedes asegurar que por este procedimiento alcanzas el minimo absoluto de E. Puede haber varias configuraciones, que cumplan todas , y que lleven a diferentes valores de E.
          Imaginate solo dos diputados que se odian. Pueden estar en el mismo grupo, con el otro vacío (E=2), o pueden estar uno en cada grupo (E=0).


          Saludos.
          Última edición por carroza; 30/06/2017, 10:24:19.

          Comentario

          Contenido relacionado

          Colapsar

          Trabajando...
          X