Problem

Source: 2020 Dutch IMO TST 3.4

Tags: combinatorics, tiles, Tiling



Given are two positive integers k and n with kn2k1. Julian has a large stack of rectangular k×1 tiles. Merlin calls a positive integer m and receives m tiles from Julian to place on an n×n board. Julian first writes on every tile whether it should be a horizontal or a vertical tile. Tiles may be used the board should not overlap or protrude. What is the largest number m that Merlin can call if he wants to make sure that he has all tiles according to the rule of Julian can put on the plate?