# Stone game with two players, where one player can't choose from the pile which was choosen in previous turn.

Alice is playing a game with his friend, Bob.

There are n piles of stones, the $$i-th$$ pile initially has $$a_i$$ stones.

Alice and Bob will take alternating turns, with Alice going first. In each turn, a player chooses a non-empty pile and then removes a single stone from it. However, one cannot choose a pile that has been chosen in the previous turn (the pile that was chosen by the other player, or if the current turn is the first turn then the player can choose any non-empty pile). The player who cannot choose a pile in his turn loses, and the game ends.

Assuming both players play optimally, given the starting configuration of t games, determine the winner of each game.

My attempt: say we have pile of stones as $$a_1<=a_2<=a_3... <=a_n$$.

If $$n=1$$, Alice wins as Bob can't choose anything.

If $$n=2$$, after Alice choose a stone from a pile the future moves of them gets predetermined.if $$a_1=a_2$$ ,no matter what Alice always loses, and if $$a_2>a_1$$ then Alice should choose a stone from $$a_1$$ to win.

can I get a hint on how to think further?

• This is for three piles. I set up a three-dimensional array A(x,y,z), with the x pile unavailable. If I programmed correctly, it is a loss if $y+z\le x$. It is a loss if $|y-z|\le x$ and $x+y+z$ is even. Otherwise, it is a win. So if the sum is even, your only chance is to sit on the biggest pile, which has to be bigger than the other two combined. Commented Sep 30, 2021 at 14:48
• @Empy2 can you share the program?I see people bruteforcing for smaller values and finding the pattern.This is common strategy,right. Commented Sep 30, 2021 at 20:02

Certainly, if one of the piles $$a_i$$ has a majority of the stones, meaning that $$a_i>(a_1+\dots+a_n)/2$$, then you can win by repeatedly taking from that pile. If the majority pile is unavailable, then your opponent wins by doing the same thing.