Question

Cuarenta equipos juegan un torneo en el que cada equipo juega contra cada otro equipo exactamente una vez. No hay empates, y cada equipo tiene una probabilidad del $50\%$ de ganar cualquier partido que juegue. La probabilidad de que no haya dos equipos que ganen el mismo número de partidos es $\frac{m}{n},$ donde $m$ y $n$ son enteros positivos primos entre sí. Halla $\log_2 n.$

Forty teams play a tournament in which every team plays every other team exactly once. No ties occur, and each team has a $50\%$ chance of winning any game it plays. The probability that no two teams win the same number of games is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $\log_2 n.$

Respuesta

Solución:

Hay $\binom{40}{2} = 780$ partidos, y por tanto $2^{780}$ resultados igualmente probables. Si los $40$ totales de victorias son todos distintos, deben ser exactamente $0, 1, \ldots, 39.$ En ese caso el equipo con $39$ victorias venció a todos, el equipo con $38$ victorias venció a todos excepto a ese equipo, y así sucesivamente: la asignación de totales a los equipos determina cada partido. Recíprocamente, cada una de las $40!$ asignaciones proviene de exactamente un resultado, así que la probabilidad es $\frac{40!}{2^{780}}.$

Por la fórmula de Legendre, la potencia de $2$ que divide a $40!$ es $20 + 10 + 5 + 2 + 1 = 38.$ En su forma más simple, el denominador es por tanto $n = 2^{780 - 38} = 2^{742},$ así que $\log_2 n = 742.$

There are $\binom{40}{2} = 780$ games, hence $2^{780}$ equally likely outcomes. If all $40$ win totals are distinct, they must be exactly $0, 1, \ldots, 39.$ In that case the team with $39$ wins beat everyone, the team with $38$ wins beat everyone except that team, and so on: the assignment of totals to teams determines every game. Conversely each of the $40!$ assignments arises from exactly one outcome, so the probability is $\frac{40!}{2^{780}}.$

By Legendre's formula the power of $2$ dividing $40!$ is $20 + 10 + 5 + 2 + 1 = 38.$ In lowest terms the denominator is therefore $n = 2^{780 - 38} = 2^{742},$ so $\log_2 n = 742.$

1999 AIME Problema 13

Solución:

El Problema 13 en otros años