A 3x3 array of counters is laid out. Players take turns removing counters. The rule for removing counters is to pick a row or column and take any 1,2 or 3 from it. Whoever removes the last counter wins.
Does the first or second player have a winning strategy?
What is this strategy?
This is a fine puzzle, and difficult to describe all the layouts where wins are forced. Both A and B try to get the opponent into a state which is a forced loss, i.e. which leaves a forced win by the player. I started from the end game and worked back.
If there are three counters in any configuration, the person to play always has a forced win. If there is a rectangle of four counters, the person to play has a forced loss. It then follows that a rectangle of six counters has a forced win (by leaving the opponent with a losing rectangle of four). It can be shown that a right triangle (six counters as 3-2-1) is a forced loss.
If A takes three on the first turn, this leaves B with the winning 6-rectangle. If A takes one, B can reduce the situation to the 6-triangle, which A loses. If A takes two, B immediately reduces this to a 4-rectangle which A will lose. Hence it appears that B will have forcing replies to whatever A selects as the first draw. So B's strategy is just to remember the target patterns to which A will be forced.
To fully describe B's winning strategy is rather complex because there are 512 (2**9) possible layouts to be considered. This probably could be programmed (so that a "B" automaton could take on all the rubes), by recursion from previous proved winning and losing moves, but I forebear. Of course if one wanted the misere version, a new analysis would be needed.
The references to the binary analysis of the traditional nim are interesting, but the formulas would be much more complex for the current game. I can recall as a beginning programmer some thirty years ago, coding an interactive extended version of the original game allowing an opponent to select how many piles, and of what sizes for play (from the basic 8-5-3 to other starts); part of the beauty of maths that a single calculation could show at each stage what to take next. It seems as though Charlie has carried out this project for the current game -- an exhaustive proof of B to win (tempting to suppose this is Bush's strategery at work?!)
Strategery
