Problem

Source: EGMO 2016 Day 2 Problem 5

Tags: combinatorics, EGMO, Tiling, EGMO 2016, Hi



Let k and n be integers such that k2 and kn2k1. Place rectangular tiles, each of size 1×k, or k×1 on a n×n chessboard so that each tile covers exactly k cells and no two tiles overlap. Do this until no further tile can be placed in this way. For each such k and n, determine the minimum number of tiles that such an arrangement may contain.