← Problem 663

An infinite game

Problem 665 →

An infinite game

Problem 664

Peter is playing a solitaire game on an infinite checkerboard, each square of which can hold an unlimited number of tokens.
Each move of the game consists of the following steps:
  • Choose one token to move. This may be any token on the board, as long as not all of its four adjacent squares are empty.
  • Select and discard one token from a square adjacent to that of .
  • Move to any one of its four adjacent squares (even if that square is already occupied).
    • Allowed moves
    The board is marked with a line called the dividing line. Initially, every square to the left of the dividing line contains a token, and every square to the right of the dividing line is empty:
    Initial setup
    Peter's goal is to get a token as far as possible to the right in a finite number of moves. However, he quickly finds out that, even with his infinite supply of tokens, he cannot move a token more than four squares beyond the dividing line.
    Peter then considers starting configurations with larger supplies of tokens: each square in the th column to the left of the dividing line starts with tokens instead of 1. This is illustrated below for :
    Initial setup n=1
    Let be the maximum number of squares Peter can move a token beyond the dividing line. For example, .You are also given that , , , and .
    Find .