MathDB
Coloring Cells of Graphs

Source: All Russian Olympiad 2015 11.8

December 11, 2015
combinatorics

Problem Statement

Given natural numbers aa and bb, such that a<b<2aa<b<2a. Some cells on a graph are colored such that in every rectangle with dimensions A×BA \times B or B×AB \times A, at least one cell is colored. For which greatest α\alpha can you say that for every natural number NN you can find a square N×NN \times N in which at least α⋅N2\alpha \cdot N^2 cells are colored?
Back to ProblemsView on AoPS