2
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Empy2
    Sep 30, 2021 at 14:48
  • $\begingroup$ @Empy2 can you share the program?I see people bruteforcing for smaller values and finding the pattern.This is common strategy,right. $\endgroup$
    – user69608
    Sep 30, 2021 at 20:02

1 Answer 1

Reset to default
2
$\begingroup$

Hint (Inspired by Empy2's comment).

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.

What if no pile is a strict majority? In that case, I claim that the game will end with zero stones in play. This means that if there are an odd number of stones total, the first player wins, and if it is even, the second player wins. You just need to show that the player who wants the clock to run out can ensure that no pile ever becomes a majority. Indeed, the strategy to ensure all stone get taken is simple; always take from the biggest pile. (Note that both players can follow this strategy, but the strategy is only beneficial to one player, depending on the parity of the total number of stones).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .