MathDB
infinite chessboard with moves

Source:

March 5, 2009
combinatorics

Problem Statement

A frog is placed on each cell of a n×nn \times n square inside an infinite chessboard (so initially there are a total of n×nn \times n frogs). Each move consists of a frog AA jumping over a frog BB adjacent to it with AA landing in the next cell and BB disappearing (adjacent means two cells sharing a side). Prove that at least [n23] \left[\frac{n^2}{3}\right] moves are needed to reach a configuration where no more moves are possible.
Back to ProblemsView on AoPS