100 personas participan en un torneo de ajedrez, en el que todos juegan contra todos exactamente una vez. Se sabe que si dos personas empataron entonces cada una de las otras 98 personas le ganó a exactamente uno de ellos.
Si hubo al menos dos empates demuestra que podemos ordenar a los concursantes en una fila de tal forma que cada persona le ganó a la que está exactamente atras de ella.
Se vale comentar!
ResponderBorrarpues, lo intente un rato pero no me salio, como que me faltaban cosas, creo que hay que separar por casos, fijandose primero en un empate, de ahi hay como 4 casos, pero pues no me salio
ResponderBorrarla fila debe de cerrarse??? el ultimo le gano al primero para continuar la condicion?
ResponderBorrarLa fila no necesariamente tiene que cerrarse. Por eso es fila y no "círculo".
ResponderBorrar¿Quién más ya intento el problema?
Si no les sale mañana pongo la solución.
a que te refieres con exactamente a uno de ellos??
ResponderBorrarentonces si los 98 le ganaron a A, ninguno de los 98 le ganó a B, sindo que A y B empataran
Es facil demostrar que las dos parejas que empataron no son distintas en su totalidad, Pongamos que A y B empataron y C yD tambien, se supone que los otros 96 mas A y B la ganaron ya sea a C o D, pero tambien se supone que los otros 96 mas C y D la ganaron a A o B !!
no se, esta medio confuso ahí, por que tampoco ay forma en que A y B empaten y B y C tambien, bueno lo seguire intentando
Si, un ejemplo sería que si A y B empataron y los otros 98 le ganaron a A entonces ninguno de los 98 le ganó a B.
ResponderBorrarY bueno no es un mal comienzo ver que una persona no puede empatar con dos personas distintas.
Les recomiendo como ir como construyendo la fila.
Bueno va la solución, como les dije el truco es ir construyendo la fila.
ResponderBorrarPrimero nos fijamos que una persona X no puede empatar con dos personas distintas Y, Z. Si fuera así entonces por las condiciones del problema como X y Y empataron entonces Z les tuvo que haber ganado a uno de ellos, pero Z empato con X por lo tanto Z le gano a Y, pero de la misma forma Y le tuvo que haber ganado a X o Z, pero empato con X, por lo tanto Y le gano a Z, lo cual es absurdo. Por lo tanto cualquier persona pudo haber empatado con a lo más una persona.
Entonces separemos a las personas en dos grupos, las que empataron, y las que no empataron. Las que empataron, empataron con exactamente una persona por lo dicho anteriormente.
Ahora fijémonos en dos parejas de personas que empataron(sabemos que hay al menos dos empates), digamos que P empato con Q y R con S. Ahora sin pérdida de generalidad como P y R no pudieron haber empatado, supongamos que P le gano a R, entonces R le tiene que ganar a P o Q, por lo tanto R le ganó a Q, luego Q le tiene que ganar a R o S, por lo tanto Q le gano a S.
Por lo tanto ya podemos formar una fila así:
P-R-Q-S donde cada persona le gano a la que esta exactamente a su derecha.
Ahora veamos que podemos ir metiendo a todas las parejas de empatados a esta fila. Supongamos que tenemos la fila A_1-A_2-...-A_n de personas y queremos meter a la pareja de empatados D y E. Como D y E empataron, A_n le tuvo que haber ganado a D o E. SPG supongamos que A_n le gano a D. Entonces a D lo colocamos a la derecha de A_n en la fila. Ahora vamos a ver que a E lo podemos meter en un lugar de la fila, supongamos que esto no es posible, entonces E perdió con A_1, sino podríamos meterlo hasta la izquierda de la fila, también perdió con A_2, sino lo podríamos meter entre A_1 y A_2, siguiendo este proceso vemos que E tuvo que haber perdido con A_1, A_2, …, A_n. Por lo tanto A_n le ganó a D y a E, pero eso es una contradicción al problema por que como D y E empataron A_n le tenía que haber ganado a exactamente uno de ellos, por lo tanto podemos meter a E en la fila.
Siguiendo este proceso podemos meter a todas las parejas de empatados en la fila de tal forma que cada persona le gane al que esta exactamente a su izquierda.
Ahora falta meter a los que no empataron con nadie, ahora veamos que siempre se puede meter a una persona K a la fila. Supón que la fila es A_1-A_2-…A_n. Supongamos que a K no lo podemos acomodar, entonces K perdió con A_1, si hubiera ganado lo podríamos poner a su izquierda, por lo tanto K perdió con A_2, si no lo podríamos poner entre A_1 y A_2, siguiendo este proceso vemos que entonces K tuvo que haber perdido con todos, en particular con A_n. Por lo tanto podemos ponerlo a la derecha de A_n. De esta forma podemos acomodar a todas las personas que no empataron y entonces ya hemos acomodado a todas las personas en una fila con las condiciones que nos pedía el problema. Fin
¿Si se entiende?