MathDB
Another impossible Beluhov problem: words upper bound in crossword

Source: KoMaL A. 865

December 12, 2023
combinatoricsGrid problemkomal

Problem Statement

A crossword is a grid of black and white cells such that every white cell belongs to some 2×22\times 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×nn\times n crossword cannot exceed (n+1)2/2(n+1)^2/2.
Proposed by Nikolai Beluhov, Bulgaria
Back to ProblemsView on AoPS