UEA: Diseño de Algoritmos
Trimestre: 2006 Invierno
Fecha: 3 de febrero de 2006

Instrucciones: Conteste cada una de las siguientes preguntas. Puede auxiliarse de programas de computadora pero no necesita entregarlos. Envíe sus respuestas usando pine a franz.

Problema 1: El juego de Nim tiene muchas variantes. En esta primera variante, al principio hay un número entero positivo N de cerillos y los jugadores toman, por turnos, ya sea 2 ó 3 cerillos. Pierde aquel jugador que no puede hacer su tirada (esto ocurre cuando quedan menos de dos cerillos). Para cada uno de los siguientes valores de N diga (suponiendo que los dos jugadores juegan perfectamente) cuál de los dos jugadores gana: 10, 21, 32, 43 y 54. Evaluación: 1 punto por cada respuesta correcta.

Problema 2: Una segunda variante del juego de Nim es aquella en la que hay dos montones de cerillos, con M y N cerillos respectivamente. Los jugadores toman, por turnos, ya sea (a) cualquier cantidad positiva de cerillos de uno de los dos montones o (b) la misma cantidad positiva de cerillos de los dos montones. Gana aquel jugador que toma el último cerillo. Para cada una de las siguientes parejas [M,N] diga (suponiendo que los dos jugadores juegan perfectamente) cuál de los dos jugadores gana: [5,0], [11, 4], [17, 8], [23, 12] y [29, 16]. Evaluación: 1 punto por cada respuesta correcta.

Problema 3: En un tablero de ajedrez de lado N se desea colocar K reyes que no se ataquen entre sí (un rey puede atacar sus ocho casillas vecinas). Para cada una de las siguientes parejas [N,K] diga de cuántas formas distintas se pueden colocar los reyes sobre el tablero: [2,1], [3,2], [4,3], [5,3] y [10,10]. Evaluación: 1 punto por cada respuesta correcta.