Question

Cinco pueblos están conectados por un sistema de caminos. Hay exactamente un camino que conecta cada par de pueblos. Halle el número de maneras de hacer que todos los caminos sean de un solo sentido de modo que aún sea posible ir de cualquier pueblo a cualquier otro pueblo usando los caminos (posiblemente pasando por otros pueblos en el camino).

Five towns are connected by a system of roads. There is exactly one road connecting each pair of towns. Find the number of ways there are to make all the roads one-way in such a way that it is still possible to get from any town to any other town using the roads (possibly passing through other towns on the way).

Respuesta

Respuesta: 544

Conceptos:teoría de grafos conteo complementario inclusión-exclusión

Nivel de dificultad: 3060

Pista pequeña:

Los caminos de un solo sentido funcionan si y solo si ningún pueblo tiene sus cuatro caminos todos entrantes o todos salientes

The one-way roads work if and only if no town has all four of its roads inbound or all four outbound

Pista grande:

Cuente las asignaciones no válidas: $5 \cdot 2^6$ con un pueblo cuyos caminos son todos salientes, lo mismo con uno cuyos caminos son todos entrantes, menos $5 \cdot 4 \cdot 2^3$ contadas dos veces

Count the bad assignments: $5 \cdot 2^6$ with an all-outbound town, the same with an all-inbound town, minus $5 \cdot 4 \cdot 2^3$ counted twice

Solución:

La asignación funciona si y solo si ningún pueblo tiene los cuatro caminos entrantes o los cuatro salientes. Una dirección es clara: no se puede salir de un pueblo cuyos caminos son todos entrantes, ni llegar a uno cuyos caminos son todos salientes. Recíprocamente, supongamos que cada pueblo tiene un camino entrante y uno saliente, pero el pueblo $B$ no puede alcanzarse desde el pueblo $A.$ Sea $S$ el conjunto de pueblos alcanzables desde $A$ (incluyendo $A$ ) y $T$ el conjunto de pueblos desde los cuales $B$ es alcanzable (incluyendo $B$ ). Estos conjuntos son disjuntos, cada camino saliente de un pueblo en $S$ permanece dentro de $S,$ y cada camino entrante de un pueblo en $T$ proviene de dentro de $T.$ Como $A$ tiene un camino saliente, $|S| \ge 2,$ y de forma similar $|T| \ge 2;$ como $|S| + |T| \le 5,$ uno de los dos conjuntos tiene exactamente dos pueblos. Si $S = \{A, X\},$ los caminos salientes de $A$ y de $X$ deben ambos permanecer dentro de $S,$ obligando al único camino entre ellos a apuntar en ambos sentidos, una contradicción (y $|T| = 2$ es simétrico).

Ahora cuente las asignaciones con un pueblo cuyos caminos son todos entrantes o todos salientes entre las $2^{10} = 1024$ totales. Elegir un pueblo para que todos sus caminos sean salientes ( $5$ maneras) y orientar libremente los $\binom{4}{2} = 6$ caminos restantes da $5 \cdot 2^6 = 320$ asignaciones, y puede haber a lo sumo un pueblo de este tipo. De forma similar, $320$ asignaciones tienen un pueblo cuyos caminos son todos entrantes. Las asignaciones con ambos se cuentan dos veces: elija el pueblo con todos los caminos salientes ( $5$ ), el pueblo con todos los caminos entrantes ( $4$ ), y los otros $3$ caminos libremente, $5 \cdot 4 \cdot 2^3 = 160.$ Así que $320 + 320 - 160 = 480$ asignaciones fallan.

El número de las que funcionan es $1024 - 480 = 544.$

The assignment works if and only if no town has all four roads inbound or all four outbound. One direction is clear: an all-inbound town cannot be left, and an all-outbound town cannot be reached. Conversely, suppose every town has an inbound and an outbound road, yet town $B$ cannot be reached from town $A.$ Let $S$ be the set of towns reachable from $A$ (including $A$ ) and $T$ the set of towns from which $B$ is reachable (including $B$ ). These sets are disjoint, every outbound road of a town in $S$ stays inside $S,$ and every inbound road of a town in $T$ comes from inside $T.$ Since $A$ has an outbound road, $|S| \ge 2,$ and similarly $|T| \ge 2;$ as $|S| + |T| \le 5,$ one of the two sets has exactly two towns. If $S = \{A, X\},$ the outbound roads of $A$ and of $X$ must both stay inside $S,$ forcing the single road between them to point both ways — a contradiction (and $|T| = 2$ is symmetric).

Now count assignments with a bad town among the $2^{10} = 1024$ total. Choosing a town to be all-outbound ( $5$ ways) and orienting the remaining $\binom{4}{2} = 6$ roads freely gives $5 \cdot 2^6 = 320$ assignments, and there can be at most one all-outbound town. Similarly $320$ assignments have an all-inbound town. Assignments with both are counted twice: choose the all-outbound town ( $5$ ), the all-inbound town ( $4$ ), and the other $3$ roads freely, $5 \cdot 4 \cdot 2^3 = 160.$ So $320 + 320 - 160 = 480$ assignments fail.

The number that work is $1024 - 480 = 544.$

2017 AIME II Problema 11

Respuesta: 544

Nivel de dificultad: 3060

Pista pequeña:

Pista grande:

Solución:

El Problema 11 en otros años