Maths Olympiad Prep

Library / /460 of 462

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Ireland

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 SS of sequences s=(si)is = (s_i)_i^\infty of non-negative integers with only finitely many non-zero entries.

For each iNi \in \mathbb{N}, the function fif_i is defined on the subset of SS of sequences ss such that si>0s_i > 0: fi(s)=tf_i(s) = t, where ti=si1t_i = s_i - 1 and ti=sit_i = s_i otherwise. The function g:SSg: S \to S is defined by g(s)=tg(s) = t, where tj=max{0,sj1}t_j = \max\{0, s_j - 1\}, jNj \in \mathbb{N}. Below, we write F\mathbb{F} for the set of functions consisting of gg and every fif_i.

A particular game is given by a sequence (sk)k=0(s^k)_{k=0}^\infty of elements of SS, where sk+1=f(sk)s_{k+1} = f(s^k) for some fFf \in \mathbb{F}. The winner is determined by the parity of the minimal kk for which sks^k is the zero element, denoted zz below.

Given sSs \in S, the notation f(s)f(s) will always refer to f(s)f(s) for some fFf \in \mathbb{F}; the number of positive and odd entries in ss are denoted by n(s)n(s) and o(s)o(s), respectively. We call WSW \subset S a strategy if the following conditions hold:
(1) If sWs \in W, and if f(s)f(s) is defined, then f(s)Wf(s) \notin W, but there exists fFf' \in \mathbb{F} such that f(f(s))Wf'(f(s)) \in W.
(2) zWz \in W.
(3) WW is rearrangement invariant: if wWw \in W, then every rearrangement of ww lies in WW.

(1) says that a player should strive to leave a configuration in WW after his/her move. If this is achieved, every move the other player makes gives a configuration not in WW; the first player can then move it back to WW, 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 WW tells us how to win from certain configurations, but it might not tell us how to proceed from every winnable configuration. WW is kk-complete if for each sSs \in S, n(s)kn(s) \le k, either sWs \in W or f(s)Wf(s) \in W for some fFf \in \mathbb{F}. (A kk-complete strategy tells us how to win from every configuration involving at most kk piles.)

The previously given solution to Configuration (a) is essentially equivalent to the fact that
W0:={sSo(s)=0} W_0 := \{s \in S \mid o(s) = 0\}
is a strategy. To verify (1), it suffices to note that if sW0{z}s \in W_0 \setminus \{z\} and if f(s)f(s) is defined, then o(f(s)){1,n(s)}No(f(s)) \in \{1, n(s)\} \subset \mathbb{N}, but f(f(s))Wf(f(s)) \in W.

Clearly, W0W_0 is 2-complete, but it is not 3-complete. We will enlarge W0W_0 to first make it 3-complete, and then 4-complete. In general, if we have a strategy WW, and a rearrangement invariant ASA \subset S, then AWA \cup W is also a strategy if for each sAs \in A:
* there is no fFf \in \mathbb{F} with f(s)Wf(s) \in W, but
* if f(s)f(s) is defined, then there exists fFf' \in \mathbb{F} such that f(f(s))Wf'(f(s)) \in W.

In the above situation, we call AWA \cup W a one-step augmentation (of WW). The sole reason that W0W_0 is not 3-complete is because of ss with n(s)=3n(s) = 3 and o(s)=2o(s) = 2. However, if we define
A:={sSn(s)=3 and o(s)=2}, A := \{s \in S \mid n(s) = 3 \text{ and } o(s) = 2\},
then W1:=AW0W_1 := A \cup W_0 is a one-step augmentation and also a 3-complete strategy. (Note that if o(s)=2o(s) = 2, then o(f(s))o(f(s)) is either 3 or 1. In the former case, g(f(s))W0g(f(s)) \in W_0; in the latter, f(f(s))W0f(f(s)) \in W_0, where ii is the index of the odd entry.)

Finally, let W2:=W1BW_2 := W_1 \cup B, where BB consists of all ss such that n(s)=4n(s) = 4 and either
* o(s)=3o(s) = 3 and the odd entries of ss all exceed 1, or
* o(s)=2o(s) = 2 and the odd entries of ss both equal 1.
We call the former sequences Type 1 and the latter Type 2.

We now prove that W2W_2 is a strategy. (It is not a one-step augmentation of W1W_1, so the proof requires a little more effort.)

First, suppose ss is of Type 1. Since o(g(s))=1o(g(s)) = 1, we have fi(g(s))W0f_i(g(s)) \in W_0, where ii is the index of the odd entry in g(s)g(s). Alternatively, o(fi(s)){2,4}o(f_i(s)) \in \{2, 4\} whenever fi(s)f_i(s) is defined. If o(fi(s))=4o(f_i(s)) = 4, then g(fi(s))W0g(f_i(s)) \in W_0, as desired. If instead o(fi(s))=2o(f_i(s)) = 2, then the next step depends on whether or not both of the even entries equal 2. If they do, then g(fi(s))g(f_i(s)) is of Type 2, as desired. If instead the jjth entry is even and exceeds 2, then fj(fi(s))f_j(f_i(s)) is of Type 1.

Suppose instead that ss is of Type 2. First, n(g(s))=2n(g(s)) = 2 and o(g(s))=2o(g(s)) = 2, so g(g(s))W0g(g(s)) \in W_0. Next, assume that fi(s)f_i(s) is defined. It might be that si=1s_i = 1, in which case o(fi(s))=1o(f_i(s)) = 1 and n(fi(s))=3n(f_i(s)) = 3. Writing jj for the index of the single odd entry in fi(s)f_i(s), we have fj(fi(s))W0f_j(f_i(s)) \in W_0, as required. Suppose instead that si1s_i \neq 1, and so sis_i is even. Then o(fi(s))=3o(f_i(s)) = 3. Taking jj so that sj=1s_j = 1, we see that n(fj(fi(s)))=3n(f_j(f_i(s))) = 3 and o(fj(fi(s)))=2o(f_j(f_i(s))) = 2, so fj(fi(s))W1f_j(f_i(s)) \in W_1, as required.

Using W2W_2, 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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.