Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2006 Indonesia MO Problems/Problem 4

Revision as of 12:56, 16 December 2019 by Rockmanex3 (talk | contribs) (Solution to Problem 4 -- two-player strategy game!)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Problem

A black pawn and a white pawn are placed on the first square and the last square of a $1\times n$ chessboard, respectively. Wiwit and Siti move alternatingly. Wiwit has the white pawn, and Siti has the black pawn. The white pawn moves first. In every move, the player moves her pawn one or two squares to the right or to the left, without passing the opponent's pawn. The player who cannot move anymore loses the game. Which player has the winning strategy? Explain the strategy.

Solution

First, we can try out the game with smaller values of $n$. If $n = 2$, then black wins (since white can't move). If $n = 3$, then white wins (since white can move forward one space to corner black). Similarly, if $n = 4$, then white wins (since white can move forward two spaces to corner black).


Additionally, note that if the first player decides to move backwards $i$ spaces, then the second player can move forwards $i$ spaces to maintain the number of spaces between the first player and the second player. Same goes for if the second player moves backwards. Thus, if the two pieces are adjacent to each other and it is the first player's turn, then the first player would lose because the second player can force the first player back to the end of the playing area (same for the second player).


With this in mind, if $n = 5$, then black would win because moving one space forward would put white in black's position in $n = 4$ and moving two spaces would put white in black's position in $n = 3$. Additionally, if $n = 6$, then white would win because by moving one, white would force black in white's position in $n = 5$, and if $n = 7$, then white would win by moving two.


Thus, we can suspect that black would win if $n \equiv 2 \pmod{3}$ and white would in otherwise, and we can prove by induction. We already have the base case covered in the above paragraphs. For the inductive step, assume that black would win if $n = 3n+2$ and white would win in $n = 3n+3$ or $n = 3n+4$. Since white moves first, we can note that the second player moving would win if $n = 3n+2$ and the first player would win otherwise. For $n = 3n+5$, white moving forward one space means that black can move two spaces forward to put white at $n = 3n+2$, and white moving forward two spaces means that black can move one space forward to put white at $n = 3n+2$, so black (or the second player) would win. However, for $n = 3n+6$, white can move forward 1 to force black in white's position in $n = 3n+5$, and for $n = 3n+7$, white can move forward 2 to force black in white's position in $n = 3n+5$, so white would win in both scenarios.


Since white and black can copy the opponent moving backward, moving backwards would not affect the results. Thus, by induction, black would win if $n \equiv 2 \pmod{3}$ by moving forward 1 if white moves forward 2 and moving forward 2 if white moves forward 1, and white would win otherwise by moving forward 1 if $n \equiv 0 \pmod{3}$ or by moving forward 2 if $n \equiv 1 \pmod{3}$ and then moving forward 1 if black moves forward 2 and moving forward 2 if black moves forward 1.

See Also

2006 Indonesia MO (Problems)
Preceded by
Problem 3 		1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 Followed by
Problem 5
All Indonesia MO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_Indonesia_MO_Problems/Problem_4&oldid=112945"