SID-2324-P6

Enunciado

Dados $n$ concellos de Galicia, dous deles, Vigo e A Coruña teñen unha fábrica. Por quedas dous xogadores xogan a un xogo. Ao que lle toca elixe 2 concellos $X$ e $Y$ tales que $X$ e $Y$ non están conectados por unha estrada e, polo menos, algún deles ten acceso (non é necesario que estea conectado directamente) a unha fábrica. Unha vez escolles, faise unha estrada entre eles. Perde o xogador que faga posible ir de Vigo a A Coruña.

---

Resolución

Solución

Logo de probar para valores pequenos de $n$ temos a intuición de que o 2º xogador gaña se $n$ é par e se $n\equiv 1\mathrm{mod}4$, mentres que gañará o 1º xogador se $n\equiv 3\mathrm{mod}4$.

Para demostrar esta intuición, temos que buscar algún argumento, ben sexa unha estratexia concreta a seguir ou de algún outro tipo, para xustificar que (xogando de forma óptima) gaña o xogador en cuestión.

O caso no que $n\equiv 0\mathrm{mod}2$ é relativamente sinxelo darse conta dunha estratexia gañadora para o 2º xogador. Esta consiste en imitar, coma se dun espello se tratara, os movementos do 1º xogador, chegando a que, ao final da partida (antes de que se fagan conexas Vigo e A Coruña) temos dous grafos disconexos co mesmo número de vértices cada un.

Para os casos nos que $n\equiv 1\mathrm{mod}2$ e $n\equiv 3\mathrm{mod}2$, aínda que se nos podería ocorrer algún tipo de estratexia gañadora, imos empregar outro argumento. No final da partida, teremos dous grafos disconexos con $\alpha$ e $\beta$ nodos respectivamente. Ao xogador que lle toque nesa quenda perderá a partida. Imos contar o número de posibles carreteras que se poden construír:

$$C=\left(\genfrac{}{}{0ex}{}{\alpha }{2}\right)\left(\genfrac{}{}{0ex}{}{\beta }{2}\right).$$

Queremos comprobar a paridade de $C$, xa que se $C\equiv 0\mathrm{mod}2$ gañará o 2º xogador, e se $C\equiv 1\mathrm{mod}2$ gañará o primeiro xogador. Para isto, estudaremos primeiro a paridade de:

$$\left(\genfrac{}{}{0ex}{}{m}{2}\right)=\frac{m!}{2!(m-2)!}=\frac{m(m-1)}{2}=\{\begin{array}{l}\text{par, se }m\equiv 0\text{ ou }1\mathrm{mod}4,\\ \text{impar, se }m\equiv 2\text{ ou }3\mathrm{mod}4.\end{array}$$

Entón, só temos que estudar os distintos restos módulo $4$ de $C$, para cada un dos dous casos que nos ocupan:

• Se $n=\alpha +\beta \equiv 1\mathrm{mod}4$: gaña sempre o 2º xogador.

$$\begin{array}{cccccc}\alpha & 0& 1& 2& 3& \mathrm{mod}4\\ \beta & 1& 0& 3& 2& \mathrm{mod}4\\ \left(\genfrac{}{}{0ex}{}{\alpha }{2}\right)\left(\genfrac{}{}{0ex}{}{\beta }{2}\right)& \text{par}& \text{par}& \text{par}& \text{par}& \end{array}$$

• Se $n=\alpha +\beta \equiv 3\mathrm{mod}4$: gaña sempre o 1º xogador. $$ \begin{array}{|c|c|c|c|c|c|} \hline \alpha & 0 & 1 & 2 & 3 & \mod 4 \ \hline \beta & 3 & 2 & 1 & 0 & \mod 4 \ \hline {\alpha \choose 2} {\beta \choose 2} & \text{impar} & \text{impar} & \text{impar} & \text{impar} & \ \hline \end{array}

---

Dúbidas & Comentarios

Nesta sección pódesnos deixar as túas dúbidas e comentarios a cerca do problema anterior. Non teñas teima en preguntar, estamos aí para botar unha man!