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

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: un pueblo todo-entrante no puede abandonarse, y un pueblo todo-saliente no puede alcanzarse. 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 malo entre las $2^{10} = 1024$ totales. Elegir un pueblo para que sea todo-saliente ( $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 todo-saliente. De forma similar $320$ asignaciones tienen un pueblo todo-entrante. Las asignaciones con ambos se cuentan dos veces: elija el pueblo todo-saliente ( $5$ ), el pueblo todo-entrante ( $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

Solución:

El Problema 11 en otros años