Problem

Source: Romania TST 2019 Day 5 P3, based on Rioplatense 2010 Level 2

Tags: combinatorics, grid, colouring



Given an integer $n\geq 2,$ colour red exactly $n$ cells of an infinite sheet of grid paper. A rectangular grid array is called special if it contains at least two red opposite corner cells; single red cells and 1-row or 1-column grid arrays whose end-cells are both red are special. Given a configuration of exactly $n$ red cells, let $N$ be the largest number of red cells a special rectangular grid array may contain. Determine the least value $N$ may take over all possible configurations of exactly $n$ red cells