Problema 24 de Febrero
Alrededor de una mesa redonda se sientan 2n peruanos, 2n bolivianos y 2n ecuatorianos. Si se pide que se pongan de pie todos los que tienen como vecinos, a su derecha y a su izquierda, a personas de la misma nacionalidad, ¿Cuál es el mayor número de personas que se pueden poner de pie?
Suscribirse a:
Comentarios de la entrada (Atom)
Ya lo intenté, pero solo se me ocurrió como que la respuesta era 6n-4 tras varias observaciones. No se cómo probarlo o si es verdad.
ResponderBorrarpor casillas cada nacionalidad tiene al menos 2n+2 vecinos y como solo pueden tener a los mas 2n vecinos de la misma nacionalidad por lo tanto al lo mas se pueden parar 6n-4 personas ya que es cuando los e vecinos mas de otras nacionalidad se repiten entre las nacionalidades y solo encontramos un caso sonde alternamos a los peruanos y bolivianos y ponemos juntos a los ecuatorianos.
ResponderBorrarla respuesta si es 6n-4 y el acomodo que me se es como el que dice Orlando, pero no entiendo muy bn tu argumento(Orlando) como que tienen 2n+2 vecinos?
ResponderBorrarAbjo pondré el hint
Hint:
ResponderBorrarDar un acomodo en el que se paran 6n-4.
VEr que no se pueden más, para esto, colorear las sillas una negra la siguiente blanca, luego negra, luego blanca, etc (se puede hacer bien ya que 6n es par) luego nos fijamos q para cada persona sus dos vecios estan en sillas de otro color, luego si nos fijamos en las puras sillas blancas vemos que si en sillas seguidas hay de la misma nacionalidad quien este entre ellos se pondra de pie. Concluir
Veamos. Siguiendo el hint...
ResponderBorrarSi tenemos las 3n sillas blancas, es fácil ver que el máximo número de sillas blancas que a su derecha tienen a alguien de su misma nacionalidad es 3n-2. Esto es debido a que si todas cumplieran, entonces las 3n sillas tendrían todas la misma nacionalidad. Pero esto no es posible, pues sólo hay 2n personas de cada nacionalidad. Entonces hay al menos 2 nacionalidades, y por tanto, al menos dos partes en las que las personas de sillas consecutivas no son de la misma nacionalidad. El acomodo es muy simple, te tomas a los 2n peruanos y los pones juntos y seguido de eso, pones n bolivianos.
Hacemos lo análogo con las sillas negras, utilizando a los 2n colombianos y a los n bolivianos restantes.
Entonces, como por cada color, el máximo de personas que se paran es 3n-2, por ambos es 6n-4.
bn
Borrar