October 9, 2015

I was given a very challenging problem when I was in a math competition in the middle school. The problem is like this: Suppose X and Y take turns to pick stones from multiple packs. The rule is to pick up any number of stones (must be at least one stone, but as many as you want) only from one pack at a time; i.e., X / Y cannot pick up stones from many packs at the same time, but X / Y can pick up all the stones from one pack if X / Y wants to. X will pick first, but the person who picks up the last stone will lose the game. Suppose we have the following cases, will X win or lose?

• (6, 6): There are 2 packs, each of 6 stones. We will use this notation throughout this article.

• (1, 2, 3): There are 3 packs, with 1, 2, and 3 stones, respectively.

The actual problem in the competition even gave more complex cases; for example, what if we have 3 packs, with 4, 5, and 6 stones, respectively (4, 5, 6)? However, for simplicity, I will just target the above 2 cases, since the solutions to the more complex cases are similar.

Case 1: (6, 6)

As I mentioned always, if you think this is complicated, why don't you start with the simplest case? Let us say, there is only 1 pack of 1 stone: (1). X has to pick first, so X will lose since X needs to pick the last stone in this only pack.

In fact, if there is only 1 pack with more than 1 stone, i.e., (n) with n ≥ 1. X will win instead, since he can always pick up {n-1} stones, leaving the only remaining one for Y to pick. Here we have a table:

We will use this table later. Please note this table is symmetric: if X starts to pick from (2), X will win; this is the same for Y: Y will also win if Y starts to pick from (2). In other words, every X in the table indicates a good pattern for the starter, while every Y in the table suggests that the starter will most likely lose. Let us consider 2 packs. First start with (1, 1). X will definitely win, since he can only pick one stone from one stack, leaving the remaining one for Y to pick. Consider (1, 2), X will still win, since he can pick 2 stones from the second pack, forcing Y to pick the last one. For (1, 3), (1, 4), ..., this is the same. So we have:

Let us not rush to the conclusion prematurely; we now consider the case (2, 2). X will lose no matter how he / she picks; as can be seen in Table 1 and Table 2, X either chooses 1 stone from a pack, leaving a favorable pattern (1, 2) for Y to start with, or chooses 2 stones from a pack, leaving a favorable pattern (0, 2) for Y to start with. So we can see (2, 2) is not a good pattern to start with. However, if we consider pattern (2, n) with n > 2, X can put this pattern back into (2, 2) for Y to start with. In summary, we have the following table:

In fact, all the patterns (n, n) with n > 2 is also a bad pattern for the starter. For example, suppose X starts with a pattern (n, n). The strategy for Y is simple: just follow X's choice symmetrically from the other pack, until one of the following patterns is seen after X picks:

• (2, m) with m > 2: Y can make it (2, 2). X will lose according to Table 3.

• (1, m) with m > 2: Y can make it (1, 0). X will lose according to Table 1.

• (0, m) with m > 2: Y can make it (0, 1). X will lose according to Table 1.

Hence, no matter how X starts from (n, n) with n ≥ 2, X will lose. So starting from (6, 6), X will lose.

Case 2: (1, 2, 3)

We have experience now. What about 3 packs of stones? For simplicity, I will just show the following table:

This table means, if Y knows how to play, there is no single chance for X to win. So starting to pick stones from pattern (1, 2, 3) is doomed to fail. I guess now you may have already known how to target the pattern (4, 5, 6)!