XXIIIOMM Problema 6

Versión para impresión
Su voto: Ninguno Media: 4 (1 voto)

En una fiesta con n personas se sabe que de entre cualesquiera 4 personas, hay 3 de las 4 que se conocen entre sí o hay 3 que no se conocen entre sí. Muestra que las n personas se pueden separar en 2 salones de manera que en un salón todos se conocen entre sí y en el otro salón no hay dos personas que se conozcan entre sí. Nota: conocerse se considera una relación mutua.

AdjuntoDescripciónTamaño
Pr6Sols.PNGPr6Sols.PNG643.01 KB



Imagen de Irving

Haremos la prueba por

Haremos la prueba por inducción comenzando con n=4. La base de inducción es trivial porque ponemos a las tres personas que se conocen entre sí o no se conocen entre sí en un salón y mandamos a la otra al otro salón y terminamos. Ahora supongamos que es posible hacer el acomodo para n personas, con n>3 y vamos con el caso n+1. Sea P una persona cualquiera de las n+1. Si quitamos a P del grupo y aplicamos la hipótesis de inducción podemos accomodar a las n personas restantes en los salones A y B, donde A es el salón en el que todos se conocen y B en el que nadie se conoce. Sean a y b las cardinalidades de A y B, respectivamente. A cada acomodo de las n personas le asignamos la pareja (a,b). Consideremos todas las parejas (a,b) resultantes de todos los posibles acomodos de las n personas al quitar a cada una de las n+1 personas del grupo. Sea (a0, b0) la pareja con el elemento máximo de todas las parejas (a,b) posibles, supongamos sin perder la generalidad que a0> ó = a b0. Sea Pr la persona que dejamos fuera al hacer este acomodo (a0, b0). Demostraré que podemos acomodar a Pr en A o B de manera que obtengamos el arreglo deseado. Supongamos que no es posible, entonces existe P1 en A y P2 en B tales que Pr no conoce a P1 y Pr conoce a P2. Sea P una persona cualquiera en A distinta a P1. P y P1 se conocen por estar en A. Ahora, en el grupo de personas Pr, P1, P2 y P hay tres personas que se conocen entre sí o que no se conocen. Para esto es forzoso que  P conozca a P2. Como P es una persona cualquiera en A y P2 conoce a P, hasta ahora podemos decir que P2 conoce a todos en A, excepto a P1. Para terminar dividimos en dos casos:

Caso 1.

P2 conoce a P1, entonces P2 conoce a todos en A y podemos pasar a P2 a A para obtener un acomodo al que le corresponde la pareja (a0+1, b0-1), lo que contradice el hecho de que a0 es máximo.

Caso 2.

P2 no conoce a P1, entonces Pr conoce a P, entonces Pr conoce a todos an A, excepto a P1. Podemos hacer el siguiente movimiento: sacamos a P1 de A y metemos a Pr y a P2 en A. A P1 lo dejamos fuera de ambos salones y obtenemos un acomodo de las n personas al que le corresponde la pareja (a0+1, b0-1), lo que contradice el hecho de que a0 es máximo.

Imagen de Irving

Aquí está mi solución para el

Aquí está mi solución para el problema 6 de la XXIII OMM, perdón por la mala calidad de la escritura pero creo que de todas formas se entiende. Aún no he leido las soluciones oficiales, agradecería mucho si alguien las pudiera publicar.

Imagen de FernandoCortez

Hola Irving, yo soy un

Hola Irving, yo soy un concursante de la OMM, y me gusta tu solución, realmente es CASI IGUAL a la solución oficial, el cual se encuentra en el cuaderno de olimpiada de problemas avanzados. La cuestión es que concluíste mal... realmente sí se pueden acomodar las personas en dos grupos, usando los mismos argumentos que usaste, excepto el de la cardinalidad máxima, ese no fue un argumento utilizado en la solución. Pero en serio muchas felicidades, no muchos pueden resolver un problema 6 de la OMM. :)