Minimum number of fountains to spray each square
Source: Vietnamese TST 2012 Problem 2
May 9, 2012
floor functioncombinatorics unsolvedcombinatorics
Problem Statement
Consider a rectangular grid with rows and columns. There are water fountains on some of the squares. A water fountain can spray water onto any of it's adjacent squares, or a square in the same column such that there is exactly one square between them. Find the minimum number of fountains such that each square can be sprayed in the case that
a) ;
b) .