Problem

Source: Israel National Olympiad 2019 Q2

Tags: combinatorics, square grid



We are given a 5x5 square grid, divided to 1x1 tiles. Two tiles are called linked if they lie in the same row or column, and the distance between their centers is 2 or 3. For example, in the picture the gray tiles are the ones linked to the red tile. Sammy wants to mark as many tiles in the grid as possible, such that no two of them are linked. What is the maximal number of tiles he can mark?