MathDB
Frog jumping

Source: Baltic Way 2000 Problem 9

February 13, 2009
combinatorics unsolvedcombinatorics

Problem Statement

There is a frog jumping on a 2k×2k 2k \times 2k chessboard, composed of unit squares. The frog's jumps are \sqrt{1 \plus{} k^2} long and they carry the frog from the center of a square to the center of another square. Some m m squares of the board are marked with an × \times, and all the squares into which the frog can jump from an × \times'd square (whether they carry an × \times or not) are marked with an ∘ \circ. There are n n ∘ \circ'd squares. Prove that n≥m n \ge m.
Back to ProblemsView on AoPS