## Cousin of Nim

In this game, two players take turns to take buttons from two different piles, the winner being the person to take the last button (similar to the game of Nim, in an earlier POTW.) On each turn a player must claim either (a) any number from one pile, or (b) an equal number from both. If a game had 4 buttons in one pile and 8 in the other, and it were your turn to claim, how should you play to be absolutely sure of winning?

What configurations, with 10 or less buttons in each pile, could be classified as winning configurations, where you could be absolutely sure of winning?

Source: Puzzlegrams, Pentagram Design Limited, 1989, #90. Used as Ken's POTD 9/9/94.

Solutions were received from David Toelkes, Larry Baum, Yaacov Yoseph Weiss, Al Zimmermann, Philippe Fondanaiche, and Denis Borris.

To win the game as described above, take one button from the pile with 8. All analysts showed there are many winning positions and only a few losing positions. For 10 buttons or less in each pile, the losing positions are 1-2, 3-5, 4-7 and 6-10.

Denis Borris' exhaustive (and moderately humorous) analysis follows. (I liked the first line, so chose to share it here.)

```Well, when I 1st saw it, I thought: what a dumb puzzle...
Then I went back: WHAT A GOOD PUZZLE!!

Part 1 : take one from the 8pile

Part 2 : ALL of them, except 1-2, 3-5, 4-7 and 6-10.

The Borris NIMematics
=====================
This takes a look at the first 20 "you lose if you go 1st" cases:
(top line is simply the differences from L to L...)

L = Low pile  H = High pile  N = Number

1 2 1  2  2  1 2  1  2  2  1  2  1  2  2  1  2  1  2  2
L  0 1 3 4  6  8  9 11 12 14 16 17 19 20 22 24 25 27 28 30 32

N  0 1 2 3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20

H  0 2 5 7 10 13 15 18 20 23 26 28 31 33 36 39 41 44 46 49 52

So we clearly see a repeating "1 2 1 2 2" making up the L's,
so an 8 accumulation at each 5th, and the H's are simply N + L.

From that, we get the following math-shattering formula:

L = N + 3A
H = L + N
if B = 2 or 3, then increase L and H by 1
if B = 4,      then increase L and H by 2
where:
A = int(N / 5)
B = N - 5A

Example: find 17th combo;
A = int(17/5) = 3
B = 17 - 5*3  = 2

L = 17 + 3*3 = 26
H = 26 + 17  = 43

Since B = 2 then L = 27, H = 44 (see N=17 above)

AND: you can use this to figure out wether you should start
or not when someone says: wanna play a game of 2pile NIM
for the next round?
Here's what you do:
1- say: "OK, set up the piles"
2- assume he sets up 54 and 88 !

- ok, that's an N of 34                     (88-54)
- so my A is 6                              (int(34/5))
- gives me a B of 4                         (34-30)
- the "Borris method" says N = L - 3A
- so my N = 36                              (54-18)
- my B is 4, so I subtract 2
- so this gives me 34...that's a "loser"
And you say innocently: OK, YOU start !!

Naturally, if opponent sets up 2 piles where
your 2 N's are not equal, you say: OK: I'll start :>)

For those interested in a "table-like" show:
gives an "eye-view" of how the "losers" come about;
losers are asterisked; example: in row 6, 6-10 is a loser:
pick to
P1(L)   ........................P2(H)......................    leave:
1      2*   3    4    5    6    7    8    9   10   11   12 ...
2      3    4    5    6    7    8    9   10   11   12   13 ...  1-2
3      4    5*   6    7    8    9   10   11   12   13   14 ...
4      5    6    7*   8    9   10   11   12   13   14   15 ...
5      6    7    8    9   10   11   12   13   14   15   16 ...  3-5
6      7    8    9   10*  11   12   13   14   15   16   17 ...
7      8    9   10   11   12   13   14   15   16   17   18 ...  4-7
8      9   10   11   12   13*  14   15   16   17   18   19 ...
9     10   11   12   13   14   15*  16   17   18   19   20 ...
10     11   12   13   14   15   16   17   18   19   20   21 ...  6-10
11     12   13   14   15   16   17   18*  19   20   21   22 ...
12     13   14   15   16   17   18   19   20*  21   22   23 ...
13     14   15   16   17   18   19   20   21   22   23   24 ...  8-13
14     15   16   17   18   19   20   21   22   23*  24   25 ...
15     16   17   18   19   20   21   22   23   24   25   26 ...  9-15
16     17   18   19   20   21   22   23   24   25   26*  27 ...
17     18   19   20   21   22   23   24   25   26   27   28*...
18     19   20   21   22   23   24   25   26   27   28   29 ... 11-18

The Borris 2pile Nim table
All rights (and lefts) reserved
```

Mail to Ken