Los 200 isleños, Argentina TST OMCS 2009 Opciones

[~Fatal_Collapse~]

En una isla viven 200 personas: 100 sinceros, que siempre dicen la verdad, 100 mentirosos, que siempre mienten. Cada una tiene por lo menos una persona amiga en la isla. Cierto día, 100 personas armaron, cada una, "todos mis amigos son sinceros" y las otras 100 personas afirmaron, cada una, "todos mis amigos son mentirosos" . Si se forman todos los pares de amigos integrados por una persona sincera y la otra mentirosa, determinar la menor cantidad de estos pares que puede haber.

Aclaración. Si A es amigo de B, entonces B es amigo de A. Cada persona puede integrar más de un par.

[Luffy]

Es claro que los sinceros se separan en dos grupos, los que sólo tienen amigos sinceros, y los que sólo tienen amigos mentirosos. Digamos que hay A isleños sinceros que sólo tienen amigos mentirosos, y 100-A isleños sinceros que sólo tienen amigos sinceros. Digamos también que hay B isleños mentirosos que tienen algún amigo sincero, y 100-B mentirosos que sólo tienen amigos mentirosos. Entonces, por lo menos, los 100-A sinceros y los 100-B mentirosos dijeron que todos sus amigos eran sinceros, así 200-A-B es menor o igual a 100, es decir, A+B es por lo menos 100. Esto quiere decir, que al menos uno de entre A o B es mayor o igual a 50, y como por cada sincero que sólo tiene amigos mentirosos, se forma al menos un par sincero-mentiroso; y como por cada mentiroso con al menos un amigo sincero también se forma al menos un par sincero-mentiroso, concluimos que la cantidad de pares de amigos sincero-mentiroso es al menos 50. La cota se alcanza por ejemplo, cuando hay 50 sinceros todos amigos entre sí, 50 mentirosos todos amigos entre sí, y los 50 sinceros y 50 mentirosos restantes, forman exactamente 50 parejas de amigos sincero-mentiroso (es decir, estos tienen sólo un amigo cada uno).