Para una preparación eficaz en informática, para cada tarea se proporciona un breve material teórico para completar la tarea. Se han seleccionado más de 10 tareas formativas con análisis y respuestas, desarrolladas a partir de la versión demo de años anteriores.

No hay cambios en el Examen Estatal Unificado KIM 2020 en informática y TIC.

Áreas en las que se pondrán a prueba los conocimientos:

• Programación;
• Algoritmización;
• herramientas TIC;
• Actividades de información;
• Procesos de información.

Acciones necesarias cuando preparación:

• Repetición del curso teórico;
• Solución pruebas en ciencias de la computación en línea;
• Conocimiento de lenguajes de programación;
• Mejorar las matemáticas y la lógica matemática;
• No basta con utilizar una gama más amplia de literatura (el plan de estudios escolar para aprobar el Examen Estatal Unificado).

Estructura del examen

La duración del examen es de 3 horas 55 minutos (255 minutos), de las cuales se recomienda dedicar hora y media a la realización de las tareas de la primera parte de los KIM.

Las tareas de los tickets se dividen en bloques:

• Parte 1- 23 tareas con respuesta corta.
• Parte 2- 4 tareas con respuestas detalladas.

De las 23 tareas propuestas en la primera parte del examen, 12 pertenecen al nivel básico de prueba de conocimientos, 10 a mayor complejidad, 1 a un nivel alto de complejidad. Tres tareas de la segunda parte son de alto nivel de complejidad, una es de mayor nivel.

Al tomar una decisión, es necesario registrar una respuesta detallada (forma libre).
En algunas tareas, el texto de la condición se presenta en cinco lenguajes de programación a la vez, para comodidad de los estudiantes.

Puntos por tareas de informática.

1 punto - por 1-23 tareas
2 puntos - 25.
3 puntos - 24, 26.
4 puntos - 27.
Total: 35 puntos.

Para ingresar a una universidad técnica de nivel medio, debes obtener al menos 62 puntos. Para ingresar a la universidad de la capital, el número de puntos debe corresponder a 85-95.

Para redactar con éxito un examen, es necesario tener un conocimiento claro de teoría y constante práctica en la resolución tareas.

Tu fórmula para el éxito

Trabajar + trabajar en los errores + leer atentamente la pregunta de principio a fin para evitar errores = puntuación máxima en el Examen Estatal Unificado de Informática.

Abrimos una suscripción a simuladores interactivos para la preparación del Examen Estatal Unificado de Informática 2016

Cualquiera que tenga una billetera Visa, MasterCard, Yandex.Money e incluso un saldo positivo en su teléfono celular puede solicitar 60 animaciones interactivas únicas para prepararse para el examen de informática de 2016 sin salir de su computadora.

Simulador para la tarea No. 26 de la versión demo del Examen Estatal Unificado 2015.
en informática y TIC utilizando el método "Hills and Holes"

La solución más sencilla al problema 26 o al antiguo C3.
en informática y TIC utilizando el método visual “Hills and Holes”

Un ejemplo de cómo resolver un problema en el caso de aumentar piedras en un montón de dos maneras: “+1” y “*2”

Dos jugadores, Petya y Vanya, juegan el siguiente juego. Hay un montón de piedras frente a los jugadores. Los jugadores se turnan, Petya hace el primer movimiento. En un turno, un jugador puede agregar una piedra a la pila o duplicar la cantidad de piedras en la pila. Por ejemplo, teniendo un montón de 15 piedras, en un movimiento puedes conseguir un montón de 16 o 30 piedras. Cada jugador dispone de un número ilimitado de piedras para realizar movimientos. El juego termina cuando el número de piedras en la pila llega a ser al menos 22. El ganador es el jugador que hizo el último movimiento, es decir, el primero en recibir una pila que contenga 22 o más piedras.
En el momento inicial había S piedras en el montón, 1<= S <=21. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Complete las siguientes tareas. En todos los casos, justifique su respuesta.

1. a) Indique todos los valores del número S por los cuales Petya puede ganar en un solo movimiento. Justifique que se han encontrado todos los valores requeridos de S e indique el movimiento ganador para cada valor especificado de S.
b) Indique un valor de S tal que Petya no pueda ganar en un solo movimiento, pero por cualquier movimiento que haga Petya, Vanya puede ganar con su primer movimiento. Describe la estrategia ganadora de Vanya.

2. Especifique dos de esos valores de S para los cuales Petya tiene una estrategia ganadora, y
– Petya no puede ganar en un solo movimiento, y
– Petya puede ganar con su segundo movimiento, independientemente de cómo se mueva Vanya.
Para cada valor dado de S, describe la estrategia ganadora de Petit.

3. Especifique el valor de S en el que:
– Vanya tiene una estrategia ganadora que le permite ganar con el primer o segundo movimiento en cualquiera de las partidas de Petya, y
– Vanya no tiene una estrategia que le permita tener garantizada la victoria en su primer movimiento.
Para el valor dado de S, describe la estrategia ganadora de Vanya.
Construye un árbol de todos los juegos posibles con esta estrategia ganadora de Vanya (en forma de imagen o tabla). En los bordes del árbol, indica quién está haciendo el movimiento; en los nodos, indica el número de piedras en la pila.

Pregunta 1a.
Trabajando hacia atrás desde la “victoria” determinamos los límites de la posición ganadora inicial: 22 – 1 = 21 Y 22/2 = 11
Para cualquier número que se encuentre dentro de este rango, la siguiente entrada es válida: máx0*2>= 22 o máx0*2 > 21 (encierre en un círculo este rango en la parte superior e indíquelo como max0, que significará la posición ganadora inicial o ganar en un movimiento)

1a) Petya gana con su primer movimiento en 11<= S <= 21. Для этого достаточно число камней в куче увеличить вдвое и их всегда получится более 21.

Pregunta 1b. Para responder a esta pregunta necesitas encontrar posiciones, llamémoslas min0 , del cual todos los movimientos posibles conducen a la posición ganadora inicial, marcada por nosotros como máx0 . A la inversa, determinamos las posiciones “sospechosas” en min0 :
11/2=? no está completamente dividida, por lo tanto, no existe tal posición. Todo lo que queda es S= 11-1=10
(pero por ahora esto es sólo especulativomin0 , así que dibujemos "fosa" dos características, lo que significará: ¡no te olvides de la existencia de 2 movimientos posibles que deberán verificarse!)

Verificamos el supuesto de S = 10 en min0. Este cheque te servirá como respuesta. a la pregunta 1b
Cuando S = 10, Petya tiene 2 movimientos con los que no puede ganar en un movimiento, pero con cualquier movimiento de Petya, Vanya puede ganar con su primer movimiento:
Cualquier movimiento de Petya “10+1=11” o 10*2=20 conduce a la posición ganadora inicial de Vanya, quien, habiendo duplicado el número de piedras en la pila, obtiene 22 o 40, que es más de 21 y Vanya ganará
Por lo tanto, delineamos la posición S = 10 a continuación con una línea continua ( dibujar un agujero) - min0 (pérdida inicial o pérdida del 1er turno):

Responda a la pregunta 1b. puede ser así: Con S = 10, Petya tiene 2 movimientos con los que no puede ganar, pero con cualquier movimiento de Petya, Vanya puede ganar con su primer movimiento. Cualquier movimiento de Petya “10+1=11” o “10*2=20” lleva a Vanya a la posición ganadora inicial, quien, duplicando el número de piedras del montón, obtiene 22 o 40, que es más que 21 y Vanya gana

Pregunta 2. Para que Petya tenga garantizada la victoria en su segundo movimiento, es decir, se encontró en posición máx0 , después de la mudanza de Vanya, necesita su primero mover " poner a Vanya en un agujero" Está claro que puede haber tales posiciones. dos, cuyos valores encontramos al revés y asegúrese de verificar...
Primera posición sospechosa "10-1=9"

S=9. ¡Revisemos esta posición para asegurar la victoria!
Si Petya estuviera jugando al sorteo, habría hecho un movimiento. "9*2 = 18", pero necesita ganar, así que descartamos este movimiento. Todo lo que queda es "9+1 = 10", y Vanya se encuentra en “pit” - lo que lleva a Petya a ganar en su segundo movimiento, ¡sin importar cómo salga Vanya!

Segunda "posición sospechosa" 10/2 = 5

S=5. ¡Revisemos esta posición para asegurar la victoria! Mover "5+1=6", retrasa el juego, por lo que no lo consideramos (lo descartamos)
Todo lo que queda es "5*2=10", y Vanya se encuentra en "fosa" - lo que lleva a Petya a ganar en su segundo movimiento, ¡sin importar cómo le vaya a Vanya!

La respuesta 2 podría ser:

Con S = 5 y 9, Petya no puede ganar con el primer movimiento, pero puede ganar con el segundo movimiento, y para ello solo necesita realizar el movimiento “5*2 = 10” desde la posición S = 5, enviando así Vanya a la posición inicial perdedora o desde la posición S = 9 envíalo a la misma posición con el movimiento “9+1=10”

Pregunta 3. Vanya debe ganar, por lo tanto debe estar en la cima. máx0, Esto significa que Petya ciertamente debe terminar en min0, dónde ir "encarcelará" Vanya de máx1, Todo lo que tenemos que hacer es encontrar posiciones en las que Petya definitivamente entraría. máx1
Encontramos posiciones "sospechosas" que podrían llevar a Petya a máx1 usando el mismo reverso:
9-1=8
9/2=? 9 no es divisible por 2 - desaparece
5-1=4
5/2=? 5 no es divisible por 2 - desaparece
Encontramos que tal "sospechoso" Sólo hay dos posiciones, ¡pero aún hay que comprobarlas!

S=8. ¡Revisemos esta posición para ver si Petya tiene la garantía de perder!
El movimiento de Petya es 8+1=9 y Vanya gana con su segundo movimiento.
El movimiento de Petya es 8*2=16 y Vanya gana con su primer movimiento.
S=4. ¡Revisemos esta posición para ver si Petya tiene la garantía de perder!
El movimiento de Petya es 4+1=5 y habría perdido, pero desde esta posición Petya se beneficia del movimiento 4*2=8, por lo que Vanya cae en el “agujero” y pierde. Pero necesitamos encontrar la estrategia ganadora de Vanya, por lo que excluimos la posición S=4 de los candidatos y obtenemos la final. "imagen":

3. En la posición S = 8 – Vanya no tiene una estrategia que le permita ganar con el primer movimiento, ya que su victoria depende del movimiento de Petya, por lo que Vanya tiene una estrategia para ganar ya sea con el primer o segundo movimiento: Si Petya elige el movimiento “+1”, la pila se convierte en 9 piedras y Vanya gana en el segundo movimiento (ver respuesta a la pregunta 2). Si Petya elige el movimiento “*2”, Vanya gana con su primer movimiento, duplicando el número de piedras de la pila.

La imagen que recibimos arriba se puede volver a dibujar fácilmente en el árbol del juego marcando primero los movimientos perdedores con líneas rojas (la línea gruesa es " trazo corto" o " +1 ", y delgado - " largo" o " *2 ") y verde - ganador. (Se pueden dibujar líneas rojas gruesas con jorobas hacia arriba, que coincidirán con la dirección de las ramas "cortas" del árbol de caza)

El panorama estratégico final de la victoria de Petit puede verse así:

Se pueden encontrar otros métodos para resolver problemas de este tipo aquí:

Dos jugadores, Pasha y Vova, juegan el siguiente juego. Hay un montón de piedras frente a los jugadores. Los jugadores se turnan, Pasha hace el primer movimiento. En un turno, un jugador puede añadir 1 piedra o 10 piedras a la pila. Por ejemplo, teniendo un montón de 7 piedras, en un movimiento puedes conseguir un montón de 8 o 17 piedras. Cada jugador dispone de un número ilimitado de piedras para realizar movimientos. El juego termina cuando el número de piedras en la pila llega a ser al menos 31. El ganador es el jugador que hizo el último movimiento, es decir, el primero en recibir una pila que contenga 31 o más piedras.

En el momento inicial había S piedras en el montón, 1 ≤ S ≤ 30.

Solución.

1. a) Pasha puede ganar si S = 21, ..., 30. Con valores más pequeños de S, en un movimiento es imposible conseguir una pila con más de 30 piedras. Pasha solo necesita aumentar el número de piedras en 10. Para S 1. b) Vova puede ganar en el primer movimiento (sin importar cómo juegue Pasha) si el montón inicialmente contiene S = 20 piedras. Luego, después del primer movimiento de Pasha, habrá 21 piedras o 30 piedras en la pila. En ambos casos, Vanya aumenta el número de piedras en 10 y gana en un solo movimiento.

2. Valores posibles de S: 10, 19. En estos casos, Pasha obviamente no puede ganar con su primer movimiento. Sin embargo, puede conseguir un montón de 20 piedras (en S=10 aumenta el número de piedras en 10; en S=19 añade 1 piedra). Esta posición se analiza en el párrafo 1 b. En él, el jugador que se moverá (ahora es Vova) no puede ganar, pero su oponente (es decir, Pasha) ganará en el siguiente movimiento.

3. Valor posible de S: 18. Después del primer movimiento de Pasha, habrá 19 o 28 piedras en la pila. Si hay 28 piedras en la pila, Vova aumentará la cantidad de piedras en 10 y podrás jugar con tu primer movimiento. La situación en la que hay 19 piedras en un montón se trata en el párrafo 2. En esta situación, el jugador que moverá (ahora es Vova) gana con su segundo movimiento.

Invitado 26.05.2014 12:31

Punto 3. Pero ¿qué pasa con la situación en la que inicialmente hay 9 piedras en la pila? Después del movimiento de Pasha, las piedras se convierten en 10 o 19, Vasya termina hasta 20 y más según el punto 1.b.

Konstantín Lavrov

Sí, 9 también es la respuesta correcta. Basta con indicar al menos un valor correcto.

Dos jugadores, Pasha y Vova, juegan el siguiente juego. Hay un montón de piedras frente a los jugadores. Los jugadores se turnan, Pasha hace el primer movimiento. En un turno, un jugador puede añadir 1 piedra o 10 piedras a la pila. Por ejemplo, teniendo un montón de 7 piedras, en un movimiento puedes conseguir un montón de 8 o 17 piedras. Cada jugador dispone de un número ilimitado de piedras para realizar movimientos. El juego termina cuando el número de piedras en la pila llega a ser al menos 41. El ganador es el jugador que hizo el último movimiento, es decir, el primero en recibir una pila que contenga 41 o más piedras.

En el momento inicial había S piedras en el montón, 1 ≤ S ≤ 40.

Diremos que un jugador tiene una estrategia ganadora si puede ganar con cualquier movimiento del oponente. Describir la estrategia de un jugador significa describir qué movimiento debe hacer en cualquier situación que pueda encontrar con diferentes jugadas del enemigo.

Complete las siguientes tareas. En todos los casos, justifique su respuesta.

1. a) Indique todos los valores del número S por los cuales Pasha puede ganar en un solo movimiento. Justifique que se han encontrado todos los valores requeridos de S e indique los movimientos ganadores.

b) Indique un valor de S tal que Pasha no pueda ganar en un solo movimiento, pero con cualquier movimiento de Pasha, Vova puede ganar con su primer movimiento. Describe la estrategia ganadora de Vova.

2. Especifique dos valores de S para los cuales Pasha tiene una estrategia ganadora y Pasha no puede ganar en un movimiento, pero puede ganar con su segundo movimiento, independientemente de cómo se mueva Vova. Para los valores dados de S, describa la estrategia ganadora de Pasha.

3. Indique el valor de S en el que Vova tiene una estrategia ganadora que le permite ganar con el primer o segundo movimiento en cualquier juego de Pasha, pero Vova no tiene una estrategia que le permita ganar con el primer movimiento. Para el valor especificado de S, describa la estrategia ganadora de Vova. Construye un árbol de todos los juegos posibles con esta estrategia ganadora de Vova (en forma de imagen o tabla). En los bordes del árbol se indica quién realiza el movimiento y en los nodos, la cantidad de piedras en la pila.

Solución.

1. a) Pasha puede ganar si S = 31, ..., 40. Con valores más pequeños de S, en un movimiento es imposible conseguir una pila con más de 40 piedras. Pasha sólo necesita aumentar el número de piedras en 10. Con S b) Vova puede ganar en el primer movimiento (sin importar cómo juegue Pasha) si la pila inicialmente contiene S = 30 piedras. Luego, después del primer movimiento de Pasha, habrá 31 piedras o 40 piedras en la pila. En ambos casos, Vanya aumenta el número de piedras en 10 y gana en un solo movimiento.

2. Valores posibles de S: 20, 29. En estos casos, Pasha obviamente no puede ganar con su primer movimiento. Sin embargo, puede conseguir un montón de 30 piedras (para S = 20 aumenta el número de piedras en 10; para S = 29 añade 1 piedra). Esta posición se analiza en el apartado 1. b). En él, el jugador que se moverá (ahora es Vova) no puede ganar, pero su oponente (es decir, Pasha) ganará en el siguiente movimiento.

3. Valor posible de S: 28. Después del primer movimiento de Pasha, habrá 29 o 38 piedras en la pila. Si la pila llega a 38 piedras, Vova aumentará la cantidad de piedras en 10 y podrás jugar con tu primer movimiento. La situación en la que hay 29 piedras en un montón se trata en el párrafo 2. En esta situación, el jugador que moverá (ahora es Vova) gana con su segundo movimiento.

La tabla muestra el árbol de posibles juegos de la estrategia de Vova descrita anteriormente. Las posiciones finales (en ellas gana Vova) están subrayadas. En la figura, se representa gráficamente el mismo árbol (ambas formas de representar un árbol son aceptables).

Dos jugadores, Petya y Vanya, juegan el siguiente juego. Frente a ellos hay dos montones de piedras, el primero de los cuales contiene 2 y el segundo, 3 piedras. Cada juego tiene muchas piedras. Los jugadores se turnan y Petya da el primer paso. El movimiento consiste en que el jugador quita la cantidad de piedras de un montón o añade 4 piedras a un montón. El juego termina en el momento en que el número total de piedras en dos montones es al menos 31. Si en el momento en que termina el juego el número total de piedras en dos montones es al menos 40, entonces Petya ganó, en caso contrario ganó Vanya. ¿Con quién juegas cuando ambos jugadores juegan sin error? ¿Cuál debería ser el primer movimiento de tu juego? Explica la respuesta.

Solución.

Vanya gana.

Para demostrarlo, consideremos un árbol de juego incompleto, diseñado en forma de tabla, donde cada celda contiene pares de números separados por una coma. Estos números corresponden al número de piedras en cada etapa del juego en la primera y segunda pila, respectivamente.

La tabla contiene todos los movimientos posibles del primer jugador. Muestra que para cualquier movimiento del primer jugador, el segundo tiene un movimiento que conduce a la victoria.

Dos jugadores, Petya y Vasya, están jugando el siguiente juego. Frente a ellos hay dos montones de piedras, el primero de los cuales contiene 2 y el segundo, 1 piedra. Cada jugador tiene un número ilimitado de piedras. Los jugadores se turnan, Petya va primero. El movimiento es que el jugador aumenta 3 veces el número de piedras en una pila o agrega 3 piedras a una pila. Gana el jugador que tras su jugada quedan al menos 24 piedras en una de las pilas. ¿Quién gana jugando sin errores? ¿Cuál debería ser el primer movimiento del jugador ganador?

Justifica tu respuesta.

Solución.

Petia gana; con su primer movimiento debe triplicar el número de piedras del segundo montón. Para demostrarlo, consideremos un árbol de juego incompleto, diseñado en forma de tabla, donde cada celda contiene pares de números separados por una coma. Estos números corresponden al número de piedras en cada etapa del juego en la primera y segunda pila, respectivamente.

La tabla contiene todas las opciones posibles para los movimientos de Vasya. Esto demuestra que, con cualquier respuesta, Petya tiene un movimiento que le llevará a la victoria.

Dos jugadores, Petya y Vanya, juegan el siguiente juego. Hay un montón de piedras frente a los jugadores. Los jugadores se turnan, Petya hace el primer movimiento. En un turno, un jugador puede agregar una piedra a la pila o aumentar cinco veces la cantidad de piedras en la pila. Por ejemplo, teniendo un montón de 10 piedras, en un movimiento puedes conseguir un montón de 11 o 50 piedras. Cada jugador dispone de un número ilimitado de piedras para realizar movimientos.

El juego termina en el momento en que el número de piedras del montón supera las 100. El ganador es el jugador que hizo el último movimiento, es decir, el primero en recibir un montón que contenga 101 o más piedras.

En el momento inicial había S piedras en el montón, 1 ≤ S ≤ 100.

Se dice que un jugador tiene una estrategia ganadora si puede ganar con cualquiera de los movimientos de su oponente. Describir la estrategia de un jugador significa describir qué movimiento debe hacer en cualquier situación que pueda encontrar con diferentes jugadas del enemigo.

Complete las siguientes tareas. En todos los casos, justifique su respuesta.

1. a) ¿Para qué valores del número S puede ganar Petya con su primer movimiento? Enumere todos esos valores y el movimiento ganador de Petit.

b) Indique un valor de S tal que Petya no pueda ganar en un solo movimiento, pero por cualquier movimiento que haga Petya, Vanya puede ganar con su primer movimiento. Describe la estrategia ganadora de Vanya.

2. Especifique dos valores de S para los cuales Petya tiene una estrategia ganadora y Petya no puede ganar con su primer movimiento, pero Petya puede ganar con su segundo movimiento, independientemente de cómo se mueva Vanya. Para los valores dados de S, describa la estrategia ganadora de Petit.

3. Indique un valor de S tal que Vanya tenga una estrategia ganadora que le permita ganar con el primer o segundo movimiento en cualquier juego de Petya, y al mismo tiempo Vanya no tenga una estrategia que le permita ganar con el primero. mover.

Para el valor dado de S, describe la estrategia ganadora de Vanya. Construye un árbol de todos los juegos posibles con la estrategia ganadora de Vanya. Preséntelo en forma de imagen o tabla. Para cada borde del árbol, indica quién realiza el movimiento; para cada nodo, indica el número de piedras en la posición.

Solución.

1. a) Petya puede ganar si S = 21, ..., 100. Con valores más pequeños de S, en un movimiento es imposible conseguir una pila con más de 100 piedras. Para Petya, basta con aumentar 5 veces el número de piedras. Cuando S 1. b) Vanya puede ganar con el primer movimiento (sin importar cómo juegue Petya), si inicialmente hay S = 20 piedras en el montón. Luego, después del primer movimiento de Petia, habrá 21 piedras o 100 piedras en el montón. En ambos casos, Vanya aumenta la cantidad de piedras 5 veces y gana en un solo movimiento.

2. Valores posibles de S: 4, 19. En estos casos, Petya obviamente no puede ganar con su primer movimiento. Sin embargo, puede obtener un montón de 20 piedras (con S = 4, aumenta el número de piedras 5 veces; con S = 19, agrega 1 piedra). Esta posición se analiza en el párrafo 1 b). En él, el jugador que moverá (ahora Vanya) no puede ganar, pero su oponente (es decir, Petya) ganará en su próximo movimiento.

3. Valor posible de S: 18. Después del primer movimiento de Petya, habrá 19 o 90 piedras en la pila. Si hay 90 piedras en la pila, Vanya aumentará la cantidad de piedras 5 veces y ganará con su primer movimiento. La situación en la que hay 19 piedras en el montón se trata en el párrafo 2. En esta situación, el jugador que moverá (ahora es Vanya) gana con su segundo movimiento.

La tabla muestra el árbol de posibles juegos de la estrategia de Vanya descrita anteriormente. Las posiciones finales (Vanya gana en ellas) están subrayadas. En la figura, se representa gráficamente el mismo árbol (ambos métodos de representación son aceptables).

Realice pruebas sobre estas tareas

La lección cubre el análisis de la tarea 26 del Examen Estatal Unificado en informática: se brinda una explicación detallada y una solución a la tarea de 2017.

La tarea número 26, "Teoría de juegos, búsqueda de una estrategia ganadora", se caracteriza por ser una tarea de alto nivel de complejidad, tiempo de finalización: aproximadamente 30 minutos, puntuación máxima: 3

* Algunas imágenes y ejemplos de páginas están tomados de los materiales de presentación de K. Polyakov.

Teoría de juego. Encontrar una estrategia ganadora

Para resolver la tarea 26, debes recordar los siguientes temas y conceptos:

estrategia ganadora

• para encontrar una estrategia ganadora en juegos simples, basta con utilizar el método de enumerar todas las opciones posibles para los movimientos de los jugadores;
• para resolver problemas 26 tareas se utilizan con mayor frecuencia para esto método de construcción de árboles;
• si dos ramas se extienden desde cada nodo del árbol, es decir posibles opciones para movimientos, entonces dicho árbol se llama binario(si hay tres opciones de continuación de cada posición, el árbol será ternario).

Posiciones ganadoras y perdedoras

• todas las posiciones en juegos simples se dividen en ganar y perder;
• posición ganadora– esta es una posición en la que el jugador que hace el primer movimiento definitivamente ganará sin importar lo que haga el oponente, a menos que cometa un error; al mismo tiempo dicen que este jugador tiene estrategia ganadora– un algoritmo para elegir el siguiente movimiento que le permita ganar;
• si el jugador que hace el primer movimiento está en perdiendo posición, entonces definitivamente perderá a menos que su oponente cometa un error; en este caso se dice que este jugador tiene ninguna estrategia ganadora; Así, la estrategia general del juego es crear una posición perdedora para tu oponente con tu movimiento;
• Las posiciones ganadoras y perdedoras se caracterizan de la siguiente manera:
• una posición desde la cual todos los movimientos posibles conducen a posiciones ganadoras – perdiendo;
• una posición desde la cual al menos uno de los posibles movimientos posteriores conduce a una posición perdedora - victorioso, y la estrategia del jugador es convertir el juego en uno perdedor(para oponente) posición.

¿Quién ganará con un juego estratégicamente correcto?

• Para determinar qué jugador ganará con un juego estratégicamente correcto, es necesario responder las preguntas:
• ¿Puede ganar cualquier jugador, independientemente de los movimientos de los demás?
• ¿Qué debe hacer un jugador con una estrategia ganadora en su primer movimiento para poder ganar, independientemente de las acciones de los movimientos de los jugadores?

Veamos un ejemplo:

Un juego: hay 5 cerillas en una pila; jugado por dos jugadores que se turnan para sacar cerillas del montón; condición: en un movimiento puedes eliminar 1 o 2 cerillas; El ganador es el que deja 1 cerilla en el montón.

Solución:

Respuesta: con el juego correcto (estrategia de juego), el primer jugador ganará; Para hacer esto, solo necesita eliminar una cerilla con su primer movimiento.

Resolver 26 tareas del Examen Estatal Unificado de Ciencias de la Computación

Análisis de la tarea 26 del Examen Estatal Unificado de Informática 2017 FIPI opción 5 (Krylov S.S., Churkina T.E.):

Dos jugadores, Pasha y Valya, están jugando el siguiente juego. Hay un montón de piedras frente a los jugadores. Los jugadores se turnan Pasha da el primer paso uno dos veces. Por ejemplo, teniendo un montón de 7 piedras, en un movimiento puedes conseguir un montón de 14 u 8 piedras. Cada jugador tiene un número ilimitado de piedras para realizar un movimiento.

El juego termina cuando el número de piedras en la pila es al menos 28 . Si al mismo tiempo no hay más de 44 piedras, el ganador es el jugador que hizo el último movimiento. De lo contrario, su oponente se convierte en el ganador. Por ejemplo, si había 23 piedras en la pila y Pasha duplica la cantidad de piedras en la pila, entonces el juego terminará y Valya será la ganadora. En el momento inicial había S piedras en el montón, 1≤ S ≤ 27.

Ejercicio 1
a) ¿En qué valores del número? S¿Podrá Pasha ganar de un solo movimiento? Enumere todos esos valores y los movimientos correspondientes de Pasha.
b) ¿Qué jugador tiene una estrategia ganadora cuando S = 26, 25, 24? Describa estrategias ganadoras para estos casos.

Tarea 2
S = 13, 12? Describir estrategias ganadoras relevantes.

Tarea 3
¿Qué jugador tiene una estrategia ganadora cuando S=11? Construya un árbol de todos los juegos posibles con esta estrategia ganadora (en forma de imagen o tabla). En los bordes del árbol se indica quién realiza el movimiento; en nodos: el número de piedras en la posición.

✍ Solución:

Para obtener una explicación detallada de la tarea 26 del Examen Estatal Unificado, mire el video:

Análisis de la tarea 26 del Examen Estatal Unificado de Informática 2017 (una de las opciones según egresado):

Petya y Vanya juegan un juego: hay un conjunto de palabras, debes nombrar consistentemente las letras de estas palabras. El ganador es el jugador que nombra la última letra de cualquier palabra del conjunto. Petia va primero.

Por ejemplo, hay un conjunto de palabras. (Lobo, Informática, De miedo); para un conjunto determinado de palabras, Petya puede nombrar la letra con su primer movimiento EN, Y o CON. Si Petya elige la letra EN, entonces Vanya ganará (próximos movimientos: Petya - EN, Vania - ACERCA DE, Pedro - l, Vania - A).

Ejercicio 1
A) Dadas 2 palabras (conjunto de letras) ( IKLMNIKLMNH, NMLKINMLKI). Determinar una estrategia ganadora.

B) Dadas 2 palabras ( TRITRITRI...TRES, RITARITARITARITARITA...RITA). en la primera palabra 99 letras, en la segunda 164 . Determinar una estrategia ganadora.

Tarea 2
Es necesario intercambiar dos letras del conjunto de elementos. 1A en la palabra de menor longitud para que la estrategia ganadora sea el otro jugador. Explica una estrategia ganadora.

Tarea 3
Dado un conjunto de palabras ( Cuervo, Lobo, Ola, Derivado, Prójor, Mijo). ¿Qué jugador tiene una estrategia ganadora? Justifica tu respuesta y escribe un árbol de todos los juegos posibles para una estrategia ganadora.

✍ Solución:

* Para Vanya, solo se muestran movimientos estratégicos.
**El círculo rojo significa ganar

Para obtener más detalles sobre cómo resolver el problema verbal, mire el video tutorial:

Solución 26. Versión demo del Examen Estatal Unificado 2018 de informática:

Dos jugadores, Petya y Vanya, juegan el siguiente juego. Hay un montón de piedras frente a los jugadores. Los jugadores se turnan, Petya hace el primer movimiento. En un turno, un jugador puede añadir a la pila uno piedra o aumentar el número de piedras en la pila dos veces. Por ejemplo, teniendo un montón de 15 piedras, en un movimiento puedes conseguir un montón de 16 o 30 piedras. Cada jugador dispone de un número ilimitado de piedras para realizar movimientos.

El juego termina cuando el número de piedras en la pila es al menos 29. El ganador es el jugador que hizo el último movimiento, es decir, el primero en recibir una pila que contenga 29 o más piedras. En el momento inicial había S piedras en el montón, 1 ≤ S ≤ 28.

Diremos que un jugador tiene una estrategia ganadora si puede ganar con cualquier movimiento del oponente. Describir la estrategia de un jugador significa describir qué movimiento debe hacer en cualquier situación que pueda encontrar con jugadas diferentes del oponente. Descripción de la estrategia ganadora. no lo hagas incluir movimientos de un jugador que juega de acuerdo con esta estrategia que no son incondicionalmente ganadores para él, es decir, no ganar independientemente del juego del oponente.

Ejercicio 1
A) Indique los valores del número S con los que Petya puede ganar en un solo movimiento.
b) Indique un valor de S tal que Petya no pueda ganar en un solo movimiento, pero para cualquier movimiento que haga Petya, Vanya puede ganar con su primer movimiento. Describe la estrategia ganadora de Vanya.

Tarea 2
Especifique dos de esos valores de S para los cuales Petya tiene una estrategia ganadora y:
— Petia no puede ganar de un solo movimiento;
- Petya puede ganar con su segundo movimiento, independientemente de cómo se mueva Vanya.
Para los valores dados de S, describa la estrategia ganadora de Petit.

Tarea 3
Especifique el valor de S en el que:
— Vanya tiene una estrategia ganadora que le permite ganar con el primer o segundo movimiento en cualquiera de las partidas de Petya;
— Vanya no tiene una estrategia que le permita tener garantizada la victoria en su primer movimiento.

Para el valor dado de S, describe la estrategia ganadora de Vanya. Construya un árbol de todos los juegos posibles con esta estrategia ganadora (en forma de imagen o tabla). En los bordes del árbol se indica quién realiza el movimiento; en nodos: la cantidad de piedras en una posición

El árbol no debe contener juegos que sean imposibles si el jugador ganador implementa su estrategia ganadora. Por ejemplo, el árbol de juego completo no es la respuesta correcta a esta tarea.

✍ Solución:

Ejercicio 1.
• a) Petya puede ganar si S = 15,… 28

15, ..., 28 - posiciones ganadoras desde el primer movimiento

b) Vanya puede ganar con el primer movimiento (sin importar cómo juegue Petya), si hay T=14 piedras. Luego, después del primer movimiento de Petya, habrá 15 o 28 piedras en la pila. En ambos casos, Vanya duplica el montón y gana en un solo movimiento.

S = 14 Petya: 14 + 1 = 15 posición ganadora (ver punto a). Vanya Petya gana: 14 * 2 = 28 posiciones ganadoras (ver punto a). Vanya gana 14 - posición perdedora

Tarea 2.

Valores posibles S: 7, 13. En estos casos, Petya obviamente no puede ganar con su primer movimiento. Sin embargo, puede obtener un montón de 14 piedras: en el primer caso duplicándolas, en el segundo añadiendo una piedra. Esta posición se analiza en el párrafo 1b. En él, el jugador que moverá (ahora Vanya) no puede ganar, pero su oponente (es decir, Petya) ganará en su próximo movimiento.

S = 7 Petya: 7 * 2 = 14 posición perdedora (ver punto 1 b). Petya gana S = 13 Petya: 13 + 1 = 14 posición perdedora (ver punto 1 b). Petya gana 7, 13 - posiciones ganadoras desde el segundo movimiento

Tarea 3.

Valores posibles T: 12. Después del primer movimiento de Petya, habrá 13 o 24 piedras en la pila. Si hay 24 piedras en la pila, Vanya duplicará la cantidad de piedras y ganará en su primer movimiento. La situación en la que hay 13 piedras en el montón se trata en el párrafo 2. En esta situación, el jugador que moverá (ahora es Vanya) gana con su segundo movimiento.

S = 12 Petya: 12 + 1 = 13 Vanya: 13 + 1 = 14 posición perdida (ver punto 1 b). vanya gana segundo¡en movimiento!

La tabla muestra un árbol de juegos posibles (y solo ellos) para la estrategia descrita por Vanya. Las posiciones finales (Vanya gana en ellas) están subrayadas. En la figura se representa gráficamente el mismo árbol.


Árbol de todos los juegos posibles con la estrategia de Vanya:

*el círculo rojo significa ganar

Examen anticipado de informática 2018, opción 1. Tarea 26:

Dos jugadores, Pasha y Vasya, están jugando el siguiente juego. Hay un montón de piedras frente a los jugadores. Los jugadores se turnan Pasha da el primer paso. En un turno, un jugador puede añadir a la pila uno o cuatro piedra o aumentar cinco veces el número de piedras en una pila. El juego termina cuando el número de piedras el montón se convierte en al menos 69.
El ganador es el jugador que hizo el último movimiento, es decir, el primero en recibir una pila que contenga 69 o más piedras. En el momento inicial había S piedras en el montón, 1 ≤ S ≤ 68.

Ejercicio 1.
A) Indique todos los valores del número S por los cuales Pasha puede ganar en un solo movimiento. Justifique que se han encontrado todos los valores requeridos de S e indique el movimiento ganador para cada valor especificado de S.

b) Especifique un valor de S tal que Pasha no pueda ganar en un solo movimiento, pero con cualquier movimiento de Pasha, Vasya puede ganar con su primer movimiento. Describe la estrategia ganadora de Vasya.

Tarea 2. Especifique 2 de esos valores de S para los cuales Pasha tiene una estrategia ganadora, y Pasha no puede ganar en un movimiento y puede ganar con su segundo movimiento, independientemente de cómo se mueva Vasya. Para cada valor de S dado, describe la estrategia ganadora de Pasha.

Tarea 3. Indique al menos un valor de S para el cual Vasya tiene una estrategia ganadora que le permite ganar con el primer o segundo movimiento en cualquier juego de Pasha, y Vasya no tiene una estrategia que le permita ganar con el primer movimiento. Para el valor especificado de S, describe la estrategia ganadora de Vasya. Construye un árbol de todos los juegos posibles con esta estrategia ganadora de Vasya (en forma de imagen o tabla).

✍ Solución:

1.
A) S ≥ 14. Si el número de piedras en la pila es 14 o más, Pasha necesita aumentar su número cinco veces, obteniendo así 70 piedras o más.

S ≥ 14 posiciones ganadoras

b) S=13. Pasha puede hacer 14, 17 o 65 piedras en su primer movimiento, después de lo cual Vasya aumenta el número cinco veces, obteniendo 70, 85 o 325 piedras en la pila.

S = 13 Pasha 1er movimiento: 13 + 1 = 14 Pasha 1er movimiento: 13 + 4 = 17 Pasha 1er movimiento: 13 * 5 = 65 Vanya 1er movimiento: * 5 = S ≥ 14 Vanya gana 13 - pierde la posición

2. S = 9, 12. Para estos casos, Pasha necesita agregar 4 piedras a un montón de 9 piedras, o 1 piedra a un montón de 12, y obtener un montón de 13 piedras.
Después de lo cual el juego se reduce a la estrategia descrita en el párrafo 1b.

S = 13 Pasha 1er movimiento: 9 + 4 = 13 Pasha gana Pasha 1er movimiento: 12 + 1 = 13 Pasha gana 9, 12 - posiciones ganadoras desde el segundo movimiento

3. S=8. Con su primer movimiento, Pasha puede hacer que el número de piedras en la pila sea 9, 12 o 40. Si Pasha aumenta el número cinco veces, entonces Vasya gana con su primer movimiento, aumentando el número de piedras cinco veces.
Para el caso de 9 y 12 piedras, Vasya utiliza la estrategia indicada en cláusula 2.

S = 8 Pasha 1er movimiento: 8 + 1 = 9 Vanya gana (ver punto 2) Pasha 1er movimiento: 8 + 4 = 12 Vanya gana (ver punto 2) Pasha 1er movimiento: 8 * 5 = 40

Mire el vídeo para conocer la solución a la tarea 26:

Simulador del examen estatal unificado de informática 2018, versión de prueba 1. Tarea 26 (Krylov S., Ushakov D.):

una piedra o . El juego termina en el momento en que el número total de piedras en los montones sea al menos 73.
El ganador es el jugador que hizo el último movimiento, es decir. el primero en recibir una posición tal que las pilas contendrán 73 piedras o más.

Ejercicio 1.
(6, 33), (8, 32) indicar qué jugador tiene una estrategia ganadora. En cada caso, describa la estrategia ganadora; Explique por qué esta estrategia conduce a una victoria e indique la mayor cantidad de movimientos que un ganador podría necesitar para ganar con esta estrategia.

Tarea 2.
Para cada una de las posiciones iniciales (6, 32), (7, 32), (8, 31) indicar qué jugador tiene una estrategia ganadora.

Tarea 3.
Para la posición inicial (7, 31) indicar qué jugador tiene una estrategia ganadora. Construya un árbol de todos los juegos posibles con la estrategia ganadora que especificó. Imagine el árbol como una imagen o una mesa.

✍ Solución:

Solución en video de la tarea 26 con dos montones:

26_6: Análisis de la tarea 26 del sitio web de K. Polyakov (núm. 31):

Dos jugadores, Petya y Vanya, juegan el siguiente juego. Delante de los jugadores hay dos montones de piedras. Los jugadores se turnan, Petya hace el primer movimiento. En un turno, un jugador puede agregar a una de las pilas (de su elección) dos piedras o duplicar el número de piedras en la pila. Para realizar movimientos, cada jugador dispone de un número ilimitado de piedras. El juego termina en el momento en que el número total de piedras en los montones sea al menos 44.
El ganador es el jugador que hizo el último movimiento, es decir. el primero en obtener una posición tal que las pilas contengan 44 o más piedras.

En el momento inicial en el primer montón había 5 piedras, en el segundo montón – S piedras; 1 ≤ S ≤ 38.
Ejercicio 1.
¿En qué S: 1a) Petya gana con su primer movimiento; 1b) ¿Vanya gana con su primer movimiento?

Tarea 2.
Nombra cualquier valor S, en el que Petya puede ganar con su segundo movimiento.

Tarea 3.
Indique el valor de S en el que Vanya gana con su primer o segundo movimiento.

✍ Solución:

5 + 20*2 = 45 (>44) * 5 - el número de piedras en el primer montón, no cambia según la condición

En consecuencia, todos los valores grande 20 resultará en un número mayor 44 . Indiquemos esto en la tabla. + significa posición ganadora desde el primer movimiento:

Respuesta 1a): S= (En el Examen Estatal Unificado, explique los movimientos, por ejemplo: (5; 20) -> (movimiento de Petit) -> (5; 40); 40 + 5 = 45)

Tarea 1 b):

Como Vanya irá en segundo lugar, es necesario cambiar la cantidad de piedras en la primera pila. Así que consideremos situaciones en las que Petya podría dar el primer paso. (7;S) y en (10;S). Indiquemos si estas posiciones ganarán en un solo movimiento: por ejemplo (7;19) posición ganadora porque el jugador hará un movimiento (7;38) y ganará (7 + 38 = 45). En consecuencia, todas las posiciones están ganando. (7;más de 19). Analicemos la tabla, aumentando el número de piedras del primer montón y buscando posiciones ganadoras de un solo movimiento:

La siguiente lógica de razonamiento: Vanya puede ganar con su primer movimiento, mientras que Petya con su primer movimiento solo puede pasar a posiciones ganadoras desde el primer movimiento (en +). Marquemos estas posiciones, teniendo en cuenta que este es el primer movimiento de Petya, y el número de piedras en el primer montón debe ser 5. Las posiciones encontradas serán posiciones perdedoras (-):

Encontramos el único valor de este tipo: (5; 19). Aquellos. S = 19.

Respuesta 1b): T=19 (En el Examen Estatal Unificado, explique los movimientos, por ejemplo: (5; 19) -> (movimientos de Petya): (5;21),(5;28);(7;19);(7;28). Vanya ganará en todas partes con el siguiente movimiento, ver párrafo anterior)

Tarea 2:

Tenga en cuenta que en la tabla, todas las "esquinas" resultantes son posiciones perdedoras (desde el primer movimiento): es decir, si un jugador se encuentra en esa posición, entonces solo puede moverse a posiciones ganadoras (es decir, el oponente ganará en el siguiente movimiento):

Lógica del razonamiento: Petya podrá ganar con su segundo movimiento cuando con su primer movimiento termine en una posición perdedora, es decir pondrá a tu oponente en una situación perdedora. Estos valores son: S = 16, 17 o 18. Llamemos a estas posiciones ganadoras desde el segundo movimiento (2+):

Respuesta 2: S = 16, 17 o 18

Tarea 3:

Indiquemos también en la tabla las posiciones que están ganando a partir del enésimo movimiento: cuando un jugador puede transferir al oponente a una posición perdedora:

Indiquemos también las posiciones perdedoras del segundo movimiento: un jugador que se encuentra en tal posición solo puede pasar a posiciones ganadoras (entonces el oponente ganará):

Lógica del razonamiento: Vanya puede ganar con su primer o segundo movimiento, mientras que Petya puede acertar con su primer movimiento. solo ya sea a una posición ganadora desde el primer movimiento (+), o a una posición ganadora desde el segundo o enésimo movimiento (2+). Esta es la posición en S = 14:

Respuesta 3: T=14 (En el Examen Estatal Unificado, explique los movimientos, refiriéndose a las explicaciones de los párrafos anteriores)

Complejidad : alto.
Tiempo aproximado de solución : 20 minutos
Sujeto: Fundamentos matemáticos de la programación. Algoritmos.
Subtema: Juegos y estrategias
Qué se comprueba: Conocimiento de conceptos básicos relacionados con el análisis de juegos con información completa. Capacidad para identificar posiciones ganadoras y perdedoras.
¿Cómo sería la tarea? Por ejemplo, así: Se da una descripción del juego de dos jugadores con información completa. Es necesario determinar posiciones en las que el jugador especificado en la condición tenga una estrategia ganadora que le permita tener garantizada la victoria en el número especificado de movimientos.

Cómo analizar un problema.
K.Yu realizó un buen análisis. Polyakov en el artículo “Examen estatal unificado: nuevas estrategias (tarea C3)” [Primero de septiembre. Ciencias de la Computación. 2013, enero. Página 22-27]. El artículo contiene muchas tareas que puede resolver usted mismo. Sólo hay una inexactitud en el artículo: el árbol que se muestra en la página 25 se llama árbol de "posibles opciones de juego". En el contexto del artículo, queda claro de qué estamos hablando. Pero al analizar el artículo con los alumnos, es mejor aclarar: un árbol de posibles opciones de juego. con la estrategia elegida por Vanya. Normalmente, un árbol de posibles opciones de juego (o simplemente un árbol de juego) es un árbol que representa todos los juegos posibles. Es decir, se consideran todos los movimientos posibles de Vanya, y no solo los movimientos que corresponden a una estrategia específica.

Comentario. La tarea C3-2013 combina ideas de las tareas C3-2011 y C3-2012. La continuidad con C3-2012 se desprende del análisis de K.Yu. Polyakov. Ver también análisis del C3-2012