A crossword is a grid of black and white cells such that every white cell belongs to some 2×2 square of white cells. A word in the crossword is a contiguous sequence of two or more white cells in the same row or column, delimited on each side by either a black cell or the boundary of the grid.
Show that the total number of words in an n×n crossword cannot exceed (n+1)2/2.Proposed by Nikolai Beluhov, Bulgaria combinatoricsGrid problemkomal