Olimpiada Enemigos en el parlamento

[angel relativamente]

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:

Solución: 

Separadlos en dos grupos de manera arbitraria. Si $E_i$ es el número de enemigos que tiene en su grupo el miembro i-ésimo ($E_i=0,1,2,3$) y $E= \sum_i E_i$, hacemos lo siguiente. Si para algún i se tiene que $E_i \geq 2$, pasamos a ese miembro de su grupo al otro (donde solo tendrá un enemigo). Probar que en tal caso decrece $E$

[carroza]

Re: Enemigos en el parlamento

Hola.

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

Solución: 

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

[carroza]

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

[angel relativamente]

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:

Solución: 

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.

Angel no me resulta obvio tu procedimiento.

No es obvio, pero paso a hacer la demostración detallada a ver si se entiende

Solución: 

Supongamos que hay $n\geq 3$ enemigos en el parlamento y denotémoslos $M_1, M_2, \cdots , M_n$. Los dividimos de manera arbitraria en dos grupos. Sea $E_i \in \{ 0,1,2,3 \}$ el número de enemigos de $M_i$ en su grupo y sea $E:= \dst \sum_{i=1}^n E_i \geq 0$. Vamos a probar que, dado un $M_i$ con más de dos enemigos en su grupo ($E_i \geq 2$), cambiarlo de grupo reduce estrictamente el valor de $E$. Tenemos 3 casos:

-Supongamos $E_i=3$ y sean $M_j, M_k, M_l$ los 3 enemigos de $M_i$ en su grupo. Si cambiamos a $M_i$ de grupo tenemos que $E_i$ decrece 3 unidades, mientras que $E_j,E_k,E_l$ decrece cada uno una unidad. Como el resto de valores no se modifica, en total $E$ decrece 6 unidades.

Para los dos siguientes casos supondremos $E_i=2$ y llamaremos $M_j,M_k$ a los dos enemigos en su grupo.


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


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

En general hemos visto que si para algún i, $E_i\geq 2$, cambiar de grupo a $M_i$ decrece $E$ estrictamente. Si iteramos el proceso, como $E$ es un entero no negativo eventualmente alcanzará un mínimo absoluto cuando $E_i \leq 1, \forall i$.

¡Un saludo!

[carroza]

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;

Solución: 

No puedes asegurar que por este procedimiento alcanzas el minimo absoluto de E. Puede haber varias configuraciones, que cumplan todas $E_i \le 1$, 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.