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?
Problem
Source: Israel National Olympiad 2019 Q2
Tags: combinatorics, square grid
VicKmath7
08.08.2019 20:30
It's easy to check that in a row of 5 squares there are maximum 2 non-linked marked squares.Therefore the maximum is 10. It can be realised in the following example where 1 means marked and 0 means not marked. 00011 00110 01100 11000 10001
Cuubic
09.08.2019 14:33
There is a more interesting version of the question is with a 101x101 square, and using distances 50,51 instead of 2,3 for the definition of being linked.
VicKmath7
09.08.2019 15:25
For 2k+1×2k+1 table and distances k, k+1 just prove by induction that the maximum marked on a row are k, therefore the answer is (2k+1)×k.
VicKmath7
09.08.2019 19:00
Example for every k>2: Cover k consecutive squares moving to left with 1 square (as in the example for k=2 before) in every of the first k+2 rows and then in the next k-2rows mark k/2 or k-1/2 in the two ends of the row. Finally colour the k rightmost squares in the last row. It's easy to check that the example works and we are done.