Board with marked squares
Source: IBEROAMERICAN 2004, Problem 1
September 22, 2004
geometryrectanglecombinatorics unsolvedcombinatorics
Problem Statement
It is given a 1001*1001 board divided in 1*1 squares. We want to amrk m squares in such a way that:
1: if 2 squares are adjacent then one of them is marked.
2: if 6 squares lie consecutively in a row or column then two adjacent squares from them are marked.
Find the minimun number of squares we most mark.