Suppose two players play a game with two piles of stones. Initially there are fi

Question

Suppose two players play a game with two piles of stones. Initially there are five stones in one pile and seven stones in the other pile. The rules of the game are that on each turn a player has two choices:

Either (i) Choose a pile and remove one or more stones from it.
(ii) Remove an equal number of stones from each pile (at least one from each).

The winner is the person who takes the last stone. Find the Kernel of this game, and decide which player has winning strategy in this game. NOTE: A player must remove something on each turn. Removing zero stones or passing on your turn is NOT an option.

Explanation / Answer

int DP[1001][1001];

void make_table()

{

    for(int j=0; j<=1000; j++)

        DP[0][j] = 0;

    for(int i=1; i<=1000; i++)

        for(int j=0; j<=1000; j++)

        {

            int cw = 0, cl = 0;

            for(int k=1; k <= (j ? 2*j : i-1) && k <= i; k++)

            {

                if(DP[i-k][k] == 1)

                    cw++;

                else

                    cl++;

            }

            if(cl > 0)          

                DP[i][j] = 1;

            else               

                DP[i][j] = 0;

        }

    int count = 0;

    for(int N=2; N<=1000; N++)

        count += DP[N][0];

    printf("%d", count);

}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.