9
$\begingroup$

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.

enter image description here

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.

enter image description here

What was Bob's last move?

$\endgroup$
  • 1
    $\begingroup$ We are told that Alice and Bob are "rational". What is that meant to cash out as, in terms of gameplay? Can we assume that if either has a winning move then they'll take it? Or just that they won't make illegal moves? Or what? $\endgroup$ – Gareth McCaughan Oct 23 '18 at 14:10
  • 1
    $\begingroup$ There are two bars crossed out on line 4. It looks as if they have been done in a single action. It doesn't look as if either of them has been crossed out twice. Are we supposed to be able to assume that they were removed by a single move? $\endgroup$ – Gareth McCaughan Oct 23 '18 at 14:14
  • 1
    $\begingroup$ Yeah, rational meaning that both want to win and will play a winning move if they spot one. The double stroke is supposed to have been a single move. $\endgroup$ – jafe Oct 23 '18 at 14:55
  • $\begingroup$ Actually, if you assume each player will play a winning move if there is one then you can deduce that the double stroke is a single move :-). $\endgroup$ – Gareth McCaughan Oct 23 '18 at 15:06
  • 1
    $\begingroup$ This puzzle is as of yet my favourite in the challenge. $\endgroup$ – Bass Oct 23 '18 at 17:58
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is correct. Nice work! $\endgroup$ – jafe Oct 24 '18 at 11:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.