The game of Greed starts with an initial configuration of one or more piles of stones. Player 1 and Player 2 take turns to remove stones, beginning with Player 1. At each turn, a player has two choices:
take one stone from any one of the piles (a simple move*);
take one stone from each of the remaining piles (a greedy move*).
The player who takes the last stone wins.
Consider the following two initial configurations:
(a) There are 2018 piles, with either 20 or 18 stones in each pile.
(b) There are four piles, with 17, 18, 19, and 20 stones, respectively.
In each case, find an appropriate strategy that guarantees victory to one of the players.
Solution
The winning strategy in (a) is easily found: all piles are even in number so Player 2 maintains this all-even status by parroting Player 1's every move. This eventually guarantees a win for Player 2.
Configuration (b) is trickier. We will see that there is a guaranteed win for Player 1. We first mathematically encode the game as a system operating on the set of sequences of non-negative integers with only finitely many non-zero entries.
For each , the function is defined on the subset of of sequences such that : , where and otherwise. The function is defined by , where , . Below, we write for the set of functions consisting of and every .
A particular game is given by a sequence of elements of , where for some . The winner is determined by the parity of the minimal for which is the zero element, denoted below.
Given , the notation will always refer to for some ; the number of positive and odd entries in are denoted by and , respectively. We call a strategy if the following conditions hold:
(1) If , and if is defined, then , but there exists such that .
(2) .
(3) is rearrangement invariant: if , then every rearrangement of lies in .
(1) says that a player should strive to leave a configuration in after his/her move. If this is achieved, every move the other player makes gives a configuration not in ; the first player can then move it back to , and eventually win because of (2). (3) just encodes the fact that a winning strategy is readily adjusted to handle swapping of piles.
A strategy tells us how to win from certain configurations, but it might not tell us how to proceed from every winnable configuration. is -complete if for each , , either or for some . (A -complete strategy tells us how to win from every configuration involving at most piles.)
The previously given solution to Configuration (a) is essentially equivalent to the fact that
is a strategy. To verify (1), it suffices to note that if and if is defined, then , but .
Clearly, is 2-complete, but it is not 3-complete. We will enlarge to first make it 3-complete, and then 4-complete. In general, if we have a strategy , and a rearrangement invariant , then is also a strategy if for each :
* there is no with , but
* if is defined, then there exists such that .
In the above situation, we call a one-step augmentation (of ). The sole reason that is not 3-complete is because of with and . However, if we define
then is a one-step augmentation and also a 3-complete strategy. (Note that if , then is either 3 or 1. In the former case, ; in the latter, , where is the index of the odd entry.)
Finally, let , where consists of all such that and either
* and the odd entries of all exceed 1, or
* and the odd entries of both equal 1.
We call the former sequences Type 1 and the latter Type 2.
We now prove that is a strategy. (It is not a one-step augmentation of , so the proof requires a little more effort.)
First, suppose is of Type 1. Since , we have , where is the index of the odd entry in . Alternatively, whenever is defined. If , then , as desired. If instead , then the next step depends on whether or not both of the even entries equal 2. If they do, then is of Type 2, as desired. If instead the th entry is even and exceeds 2, then is of Type 1.
Suppose instead that is of Type 2. First, and , so . Next, assume that is defined. It might be that , in which case and . Writing for the index of the single odd entry in , we have , as required. Suppose instead that , and so is even. Then . Taking so that , we see that and , so , as required.
Using , we see that Player 1 has a guaranteed win in Configuration (b); the first move should be to remove a stone from one of the even piles.