XXIIIOMM Problema 6

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.

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.

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. :)