Paper, pencil and a bunch of bars

Question

_{An entry for the Fortnightly Topic Challenge #40.}

---

Alice and Bob are two rational players who are playing a simple pencil-and-paper game.

In the beginning, there are fifteen small vertical bars on the paper in the form of a pyramid. Players take turns crossing over one or more bars, and the player who crosses out the last bar wins.

A turn consists of making a single horizontal stroke which crosses over at least one uncrossed bar. More than one bar can be crossed with one stroke, up to and including the whole row if the player so chooses. Bars that are already crossed can be crossed over again, so long as the stroke still crosses over at least one previously uncrossed bar. The game ends when all bars have been crossed, and the player who made the last move is the winner.

In the current game, Bob has just finished making his move.

What was Bob's last move?

Answer 1

This game is

Nim with five piles. (It wouldn't be if moves weren't permitted to cross over already-crossed bars.)

So in this case

we have started with (1,2,3,4,5) which is a first-player win with any of 1->0, 3->2, 5->4 being winning moves; and we now have (apparently after six plays, but appearances might be deceptive) (0,1,1,2,4) which is a first-player win with the only winning move being 4->2. And we can see that 3->1 happened in two steps: 3->2->1.

If we take "rational" to mean that when either player had a winning move they took it then

an even number of moves have been played (because otherwise the winning player has shifted) and so 4->2 happened in a single move (which must have been made by the second=losing player, as will be apparent if you think about the binary expansions of the row-counts).

Now

we need to find a path from (1,2,3,4,5) to (0,1,1,2,4) taking six steps in which the first, third and fifth all move to positions with nim-sum zero, and the second, fourth or sixth is 4->2. Whenever the second player moves 4->2, the first player must play 5->(less than 4) in order to clear out that 4-bit. That hasn't happened yet, and therefore the second player must just now have moved 4->2.

So

Bob's last move was to strike out two bars on the fourth line.