Rompecabezas | Juego de coles de bruselas

Dado n número de lugares, y dos jugadores. Los jugadores deben conectar dos puntos cualesquiera sin cruzar ninguna de las líneas dibujadas, el jugador que no puede dar un movimiento, pierde. Determine quién ganará jugador1 o jugador2.

Ejemplos:

Input : n = 2
Output : player 2

Input : n = 3
Output : player 1

Explicación :

Método: El ganador de este juego no depende de los movimientos que elijan los jugadores, sino que solo depende de n. Este problema se puede resolver utilizando las características de Euler .

Según las características de Euler: Para toda superficie S existe un entero tal que siempre que un grafo G con V vértices y E aristas esté incrustado en S de modo que haya F caras (regiones divididas por el grafo), entonces:

.

Para un gráfico plano .

Considere la imagen final (es decir, la situación después del último movimiento).

Enfoque de la solución utilizando las características de Euler:
1. En la imagen final, podemos tomar cada punto de cruce como un vértice.
2. Cada línea que une estos puntos de cruce se puede considerar como un borde y
3. Cada sección de área (incluida la exterior) se puede considerar como una cara del gráfico.

Sea, el número de movimientos posibles para un n particular es m. Para resolver el problema, se debe encontrar el valor de m.

Observaciones:
1. Hay inicialmente n cruces (es decir, n vértices). Cada movimiento crea una nueva cruz. Por lo tanto, al final habrá un total de V = (n+m) cruces (vértices).
2. En cada movimiento, el jugador une dos extremos libres mediante una línea y hace una nueva cruz en la línea (creando un nuevo vértice), el próximo jugador termina con dos nuevos bordes que conectan los tres vértices (antiguo 2, nuevo 1). Por lo tanto, después de m movimientos habrá E = 2*m aristas en el gráfico.
3. Se puede ver que hay exactamente un extremo libre dentro de cada una de las caras. Por lo tanto, el número de caras es igual al número total de extremos libres. Nuevamente, en cada movimiento, el jugador conecta dos extremos libres (pierde dos extremos libres) y crea dos nuevos extremos libres (haciendo un nuevo punto de cruce). Por lo tanto, el número total de extremos libres permanece sin cambios. Entonces, número total de extremos libres inicialmente = Número de caras, F = 4*n.

Ahora, se puede escribir como: V – E + F = 2
, es decir, (n + m) – 2*m + 4*n = 2.
Resolviendo esta ecuación, m = (5*n – 2)

Ahora, si m es impar, el jugador 1 ganará y si m es par, el jugador 2 ganará.

// C++ code to find out winner
// of Brussels Sprouts game.
#include <iostream>
using namespace std;
  
// Function to find out winner of
// the game.
void winner(int n)
{
  
    // Total number of moves m.
    int m = 5 * n - 2;
  
    // If m is odd Player 1 is winner
    // If m is even Player 2 is winner.
    if (m % 2 == 1)
        cout << "Player 1" << endl;
    else
        cout << "Player 2" << endl;
}
  
// Driver code
int main()
{
    // Test case 1
    int n1 = 2;
    winner(n1);
  
    // Test case 2
    int n2 = 3;
    winner(n2);
  
    return 0;
}

// Java code to find out winner
// of Brussels Sprouts game.
  
import java.io.*;
  
class GFG {
      
    // Function to find out winner of
    // the game.
    static void winner(int n)
    {
  
        // Total number of moves m.
        int m = 5 * n - 2;
  
        // If m is odd Player 1 is winner
        // If m is even Player 2 is winner.
        if (m % 2 == 1)
            System.out.println("Player 1");
        else
            System.out.println("Player 2");
    }
  
    // Driver code
    public static void main(String[] args)
    {
  
        // Test case 1
        int n1 = 2;
        winner(n1);
  
        // Test case 2
        int n2 = 3;
        winner(n2);
    }
}
  
// This code is contributed by vt_m.

Player 2
Player 1