Related blue squares in 4m by 4m board
Source: EGMO 2016 Day 1 Problem 3
April 12, 2016
combinatoricsEGMOEGMO 2016ColoringExtremal combinatorics
Problem Statement
Let be a positive integer. Consider a array of square unit cells. Two different cells are related to each other if they are in either the same row or in the same column. No cell is related to itself. Some cells are colored blue, such that every cell is related to at least two blue cells. Determine the minimum number of blue cells.