Problem

Source: 2017 ELMO #3

Tags: combinatorics, ELMO 2017, Elmo



nic$\kappa$y is drawing kappas in the cells of a square grid. However, he does not want to draw kappas in three consecutive cells (horizontally, vertically, or diagonally). Find all real numbers $d>0$ such that for every positive integer $n,$ nic$\kappa$y can label at least $dn^2$ cells of an $n\times n$ square. Proposed by Mihir Singhal and Michael Kural